常见排序算法及对应的时间复杂度和空间复杂度

  • 时间:
  • 浏览:0
  • 来源:uu快3新平台_uu快3诀窍_讨论群

内排序有还能够分为以下几类:

  (1)、插入排序:直接插入排序、二分法插入排序、希尔排序。

  (2)、选者排序:直接选者排序、堆排序。

  (3)、交换排序:冒泡排序、快速排序。

  (4)、归并排序

  (5)、基数排序

image.png

[TOC]

1、插入排序

1.1直接插入排序(从后向前找到最少位置后插入)

1.2 二分法插入排序

1.3 希尔排序

2、选者排序

2.1 直接选者排序

2.2 堆排序

3、交换排序

3.1 冒泡排序

3.2快速排序

4、 归并排序

5、基数排序

排序大的分类还能够分为有一种:内排序和外排序。在排序过程中,完全记录存放满内存,则称为内排序,将会排序过程中能够 使用外存,则称为外排序。下面讲的排序就有属于内排序。

java实现

image.png

image.png

堆的定义下:具有n个元素的序列 (h1,h2,…,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1) (i=1,2,…,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义还能够看出,堆顶元素(即第六个元素)必为最大项(大顶堆)。完全二叉树还能够很直观地表示堆的内部。堆顶为根,其它为左子树、右子树。

image.png

交换,从堆中踢出最大数:

基本思想:

堆排序是有一种树形选者排序,是对直接选者排序的有效改进。

基本思想:在要排序的一组数中,对当前还未排好序的范围内的完全数,自上而下对相邻的六个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

实例

思想:初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储序,使之成为六个堆,这时堆的根节点的数最大。有些 将根节点与堆的最后六个节点交换。有些 对前面(n-1)个数重新调整使之成为堆。依此类推,直到只六个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。从算法描述来看,堆排序能够 六个过程,一是建立堆,二是堆顶与堆的最后六个元素交换位置。就说 有堆排序六个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。

基本思想:每步将六个待排序的记录,按其顺序码大小插入到前面将会排序的字序列的最少位置(从后向前找到最少位置后),直到完全插入排序完为止。

实例

基本思想:在要排序的一组数中,选出最小的六个数与第六个位置的数交换;有些 在剩下的数当中再找最小的与第六个位置的数交换,这么循环到倒数第六个数和最后六个数比较为止。

实例:

基本思想:选者六个基准元素,通常选者第六个元素将会最后六个元素,通过一趟扫描,将待排序列分成两每项,一每项比基准元素小,一每项大于等于基准元素,此时基准元素在其排好序后的正确位置,有些 再用同样的方法 递归地排序划分的两每项。

实例:

image.png

image.png

基本思想:归并(Merge)排序法是将六个(或六个以上)有序表合并成六个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。有些 再把有序子序列合并为整体有序序列。

实例

图片

java实现

文章参考:https://blog.csdn.net/gane_cheng/article/details/52652705

image.png

实例

image.png

排序算法经过了很长时间的演变,产生了就说 有种不同的方法 。对于初学者来说,对它们进行分发便于理解记忆显得有点硬要。每项算法就有它特定的使用场合,不能自己通用。有些 ,大家 很有必要对所有常见的排序算法进行归纳。

初始序列:46,79,56,38,40,84

建堆:

基本思想:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。有些 ,从最低位开使英语 ,依次进行一次排序。那我从最低位排序总是到最高位排序完成时候,数列就变成六个有序序列。

实例

:

image.png

:

:

基本思想:二分法插入排序的思想和直接插入一样,就说 找最少的插入位置的方法 不同,这里是按二分法找到最少的位置,还能够减少比较的次数。

实例:

image.png

基本思想:先取六个小于n的整数d1作为第六个增量,把文件的完全记录分成d六个组。所有距离为d1的倍数的记录放满同六个组中。先在各组内进行直接插入排序;有些 ,取第六个增量d2

java代码: