数据结构【九】排序

部分转载:

数据结构与算法系列–十大排序(附动态图解)

数据结构 —— 排序算法总结

数据结构常见的八大排序算法(详细整理)

总体概述

  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;
  • 不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;
  • 内排序:所有排序操作都在内存中完成;
  • 外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;
  • 时间复杂度: 一个算法执行所耗费的时间。
  • 空间复杂度:运行完一个程序所需内存的大小。

五类排序

1、插入排序

(1)直接插入排序

方法:将数组中的所有元素依次跟前面已经排好的元素相比较,如果选择的元素比已排序的元素小,则交换,直到全部元素都比较过。

img

  • 时间性能:平均情况下排序的时间复杂度为 O(n2)
    • 最好:O(n)——已经是正序的,比较 n-1 次,没有移动
      • n-1次是对因为从低2个元素到底n个元素都是比较1次,求和为n-1
    • 最坏:最坏的情况:O(n^2)——正好是逆序的,比较(n+2)(n-1)/2次,移动n(n-1)/2次
      • 比较(n+2)(n-1)/2次,是因为从第2个元素开始,每个元素都是比较i次(i从2到n)的,使用等差数列求和。而比较的移动次数比比较次数少1,即从第2个元素开始每个元素比较i-1次,同样等差数列求和
  • 空间性能: O(1),仅需一个记录的辅助空间
  • 稳定性:稳定
  • 一次排序后元素不能确定其最终位置

(2)折半插入排序

核心思想:分治法

方法:设元素序列 V[0], V[1], …, V[n-1],其中, V[0], V[1], …, V[i-1] 是已经排好序的元素,在插入V[i] 时, 利用折半查找寻找V[i] 的插入位置,从该位置到V[i-1]的元素依次向后移动,最后将V[i]插入

其实和直接插入本质区别就在于,根据插入排序的特点,前部分的数据是已经有序的,所以在前面查找插入位置可以使用二分查找法,提高查找效率

  • 时间性能: 平均情况下排序的时间复杂度为 O(n2)
    • 最好情况:排序前元素已按排序码从小到大有序,但是总排序码比较次数多于直接插入排序。没有移动。
    • 最坏情况:最坏情况,排序前元素逆序, 总排序码比较次数为nlog2n优于直接插入排序的(n+2)(n-1)/2次,移动n(n-1)/2次
  • 空间性能:O(1),仅需一个记录的辅助空间
  • 稳定性:稳定
  • 一次排序后元素不能确定其最终位置

直接插入和折半插入的区别: 差距只在比较次数上,其他均相同。最好情况(全部有序)比较次数,折半插入反而比直接插入多,但是不会多很多,毕竟是nlog2n级,而最坏情况(逆序)比较次数折半插入nlog2n比直接插入的(n+2)(n-1)/2次要少的多。而移动次数、空间复杂度、稳定性不变,所以我们说折半插入排序的平均性能比直接插入排序要快

(3)希尔排序

推荐阅读:排序:希尔排序(算法)

希尔排序实际上是对插入排序的一种改进,但是提高了效率的同时也变得不稳定

方法:将**待排序数组按照步长gap进行分组,然后将每组的元素利用直接插入排序的方法进行排序;每次将gap折半减小,循环上述操作;当gap=1时,利用直接插入,完成排序。**

不难发现一点,那么就是gap是几那么本次的排序组数就是几

实现:第一层循环:将gap依次折半,对序列进行分组,直到gap=1,第二、三层循环:也即直接插入排序所需要的两次循环。

  • 时间性能:平均情况下排序的时间复杂度为 O(n1.3)

  • 空间性能:O(1),仅需一个记录的辅助空间

  • 稳定性:稳定

  • 一趟结束后元素不能确定其最终位置

  • 关于gap 的数值:

图象转自:图解排序算法(二)之希尔排序

2、选择排序

选择排序核心思想:每一趟都选出一个最大或最小的元素,并放在合适的位置。

(1)直接选择排序

①在一组元素 V[i]~V[n-1] 中选择具有最小排序码的元素

②若它不是这组元素中的第一个元素, 则将它与这组元素中的第一个元素对调

③在这组元素中剔除这个具有最小排序码的元素。在剩下的元素V[i+1] ~ V[n-1]中重复执行第①、②步, 直到剩余元素只有一个为止。

img

  • 时间性能:平均情况下排序的时间复杂度为 O(n²)

    • 时间性能与初始排序序列顺序无关
  • 空间性能: O(1)

  • 稳定性:不稳定

  • *一趟结束后会有一个元素确定其最终位置 *

(2)锦标赛排序(树型选择排序)

转载:树形选择排序

有n个待排序的元素,把它们两两一组进行比较,取出较小的,然后在这n/2个较小者中再两两一组进行比较,取出较小的,重复上述步骤,直到取出最小元素。 这个过程用一棵满二叉树表示,在选出最小关元素后,将这个元素对应的叶子节点的值置为∞,然后把不为∞的兄弟节点移到父节点的位置。一直重复这个过程就可以了

  • 时间性能:O(nlogn)
  • 空间性能:需要占用大量空间(因为只有叶子节点是我们的数据,其他节点是为了筛选最值而创建)
  • 稳定性:稳定
  • *一趟结束后会有一个元素确定其最终位置 *

(3)堆排序

1、 将待排序序列构造成一棵完全二叉树

2、把这棵完全二叉树改造成堆,则堆顶元素为最小值

3、输出最小值

4、删除根结点,将剩余的二叉树改造成堆,便可获取次小值

5、输出次小值

6、重复改造,直至输出所有结点,得到一个有序序列

*堆的构造和POP根节点请查看数据结构:堆 *

  • 时间性能:为O(nlog2n)

  • 空间性能:O(1)

  • 稳定性:不稳定

  • *一趟结束后会有一个元素确定其最终位置 *

3、交换排序

(1)冒泡排序

方法:设待排序元素序列中的元素个数为 n。最多作 n-1 趟,i = 1, 2, ……, n-1。在第 i 趟中从后向前,j = n-1, n-2, ……, i,顺次两两比较V[j-1].key和V[j].key。如果发生逆序,则交换V[j-1]和V[j]。

img

图片转自:https://zhuanlan.zhihu.com/p/52884590

值得注意的是冒泡排序有很多个版本,若第二个循环为例如:

int j = 0; j < array.length - 1 - i; j++

即从前往后来,则每一轮排序都有一个数根据排序规则放到第array.length - 1 - i个位置上固定,即不断将数冒到后面依次从后往前有序化

若为:

for(int j=array.length-1;j>=i;j--)

即从后往前来,则每一轮都有一个数根据排序规则找到固定位置低i个元素上,即不断将数冒到前面从前往后有序化

一般情况下,更倾向于第二种写法

改进版:通过添加一个标记,如果某轮排序没触发交换动作,则说明已经有序,此时停止即可,这样可以提高效率

  • 时间性能:平均情况下排序的时间复杂度为 O(n2)
  • 空间性能: O(1)
  • 稳定性:稳定
  • *一趟结束后会有一个元素确定其最终位置 *

(2)快速排序

方法:

①以首元素作为基准元素( 枢轴),从前、后双向扫描序列,通过交换,实现大值记录后移,小值记录前移,最终将基准元素安置在一个适当的位置。(小值记录在前、大值记录在后)

②基准元素将原序列分割成两部分,依次对前后两部分重新设定轴记录,继而分别再进行快速排序。

③直至整个序列有序。

为什么我们要从右向左找小于基准元素的值,然后交换,再从左向右找大于基准元素的值再交换呢?

因为这样可以很巧妙的一次遍历且只用一个交换存储空间就能达到我们的目的。就如同本例:基准元素为38,第一次交换后38后的数据由于我们从后向左比较,已经确定都是大于38的了,此时从左向右找大于基准元素的再交换,同理这样38左侧就一定都是小于38的了,这样知道low=high,遍历完毕,比基准元素小的都在左侧了,比基准元素大的也就都在右侧了。然后再对左侧序列和右侧序列进行快速排序,直到结束

分析过程我们得到:它是一个递归程序(但是有非递归实现)

  • 时间性能:均情况下排序的O(nlog2n)由于是枢轴分割的思想,每趟都是一分为二,故快速排序需进行 log2n 趟。每趟的排序由于都是前、后同时进行,且一遍扫描就完成,可知每趟的时间复杂度为 O(n),所以时间复杂度为 O(nlog2n)

    • 最坏情况:O(n2) 当输入序列基本有序时快速排序退化为冒泡排序
    • 最好的情况:O(nlog2n)
  • 空间性能:需栈空间以实现递归

    • 最坏情况:S(n)=O(n)
    • 一般情况:S(n)=O(log2n)
  • 稳定性:不稳定

  • *一趟结束后会有一个元素确定其最终位置,就是每次的枢轴量最终位置 *

4、归并排序

基本思想: 假设初始序列含有 n 个记录,则可以看成是 n 个有序的子序列,每个子序列的长度为 1,然后两两归并,得到 x (一个不小于 n/2 的整数)个长度为 21 的有序子序列,再两两归并,……,如此重复,直至的代一个长度为 n 的有序序列为止;

由于是折半分割的思想,归并排序需进行 log2n 趟。每趟的归并都需扫描全部记录,且一遍即可完成,由算法 可知时间复杂度为 O(n)。2-路归并排序算法的时间复杂度为 O(nlog2n)

  • 时间性能:O(nlog2n)
  • 空间性能:占用的附加存储空间较多, 需要一个与原待排序元素数组同样大小的辅助数组O(n)
  • 稳定性:稳定
  • *一趟结束不能确定一个元素的最终位置 *

这里我们使用的是二路归并排序:归并时,需要两个移动下标,从左向右比较两个序列的值,小的添入新序列,然后将原指向该数的下标+1再次比较,直到结束。多路归并同理,只是比较时是比较多个序列中的最值

## 5、基数排序

(1)LSD基数排序

LSD基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。

有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。

例如:

设有 n 个待排序元素,每个元素的排序码有 d 位,
每个排序码的取值范围为 radix
每1趟分配需要扫描n 个元素,时间为O(n)
每1趟收集需要对radix队列进行,时间为O(radix)
整个排序需要进行d 趟
LSD基数排序的时间复杂度为:O( d(n+radix) )
基数排序是稳定的排序方法。

注意这里分析是链式,所以是n+radix

  • 时间性能:O( d(n+radix) )

  • 空间性能:O (radix*d )

  • 稳定性:稳定

  • *一趟结束不能确定一个元素的最终位置 *

(2)MSD基数排序

LSD从低位开始排到高位,每排一位都是把各个桶合并,再按下一位排序;
MSD从高位开始排到低位,排完一位后不合并桶,相同的高位划分子桶继续分配,最后再合并

详细了解MSD基数排序查看:

基数排序:LSD 与 MSD

排序算法分析

一次排序能够缺点一个元素位置的算法:*各种选择排序+冒泡排序 *

(1)平均时间性能快速排序最佳,但最坏情况下的时间性能O(n2)不如堆排序和归并排序O(nlogn).
(2)简单排序以“直接插入排序”最简单,当序列“基本有序”或n较小时,它是最佳排序方法,通常用它与“先进的排序方法”结合使用.
(3)基数排序最适合n很大而关键字较小的序列
(4)从稳定性看,归并排序,基数排序和“简单排序法”是稳定的;而快速排序,堆排序和SHELL排序,直接选择排序是不稳定的.
(5)稳定性由方法本身决定,不稳定的方法总能举出使其不稳定的实例.

-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~