各种排序算法总结和比较

    排序算法可以说是一项基本功,解决实际问题中经常遇到,针对实际数据的特点选择合适的排序 算法可以使程序获得更高的效率,有时候排序的稳定性还是实际问题中必须考虑的,这篇博客对常见 的排序算法进行整理,包括:插入排序、选择排序、冒泡排序、快速排序、堆排序、归并排序、希尔 排序、二叉树排序、计数排序、桶排序、基数排序。

   比较排序和非比较排序

   常见的排序算法都是比较排序,非比较排序包括计数排序、桶排序和基数排序,非比较排序对数据有要求,因为数据本身包含了定位特征,所有才能不通过比较来确定元素的位置。    比较排序的时间复杂度通常为O(n2)或者O(nlogn),比较排序的时间复杂度下界就是O(nlogn),而非比较排序的时间复杂度可以达到O(n),但是都需要额外的空间开销。

   比较排序时间复杂度为O(nlogn)的证明:

   a1,a2,a3……an序列的所有排序有n!种,所以满足要求的排序a1',a2',a3'……an'(其中a1' <=a2'<=a3'……<=an')的概率为1/n!。基于输入元素的比较排序,每一次比较的返回不是0就是1,这恰 好可以作为决策树的一个决策将一个事件分成两个分支。比如冒泡排序时通过比较a1和a2两个数的大 小可以把序列分成a1,a2……an与a2,a1……an(气泡a2上升一个身位)两种不同的结果,因此比较排序也 可以构造决策树。根节点代表原始序列a1,a2,a3……an,所有叶子节点都是这个序列的重排(共有n!个 ,其中有一个就是我们排序的结果a1',a2',a3'……an')。如果每次比较的结果都是等概率的话(恰好 划分为概率空间相等的两个事件),那么二叉树就是高度平衡的,深度至少是log(n!)。
   又因为 1. n! < nn ,两边取对数就得到log(n!)<nlog(n),所以log(n!) = O(nlogn).
  2. n!=n(n-1)(n-2)(n-3)…1 > (n/2)^(n/2) 两边取对数得到 log(n!) < (n/2)log(n/2) = Ω(nlogn),所以 log(n!) = Ω(nlogn)。

排序的稳定性和复杂度

不稳定:

选择排序(selection sort)— O(n2)
快速排序(quicksort)— O(nlogn) 平均时间, O(n2) 最坏情况; 对于大的、乱序串列一般认为是最快的已知排序
堆排序 (heapsort)— O(nlogn)
希尔排序 (shell sort)— O(nlogn)
基数排序(radix sort)— O(n·k); 需要 O(n) 额外存储空间 (K为特征个数)

稳定:

插入排序(insertion sort)— O(n2)
冒泡排序(bubble sort) — O(n2)
归并排序 (merge sort)— O(n log n); 需要 O(n) 额外存储空间
二叉树排序(Binary tree sort) — O(nlogn); 需要 O(n) 额外存储空间
计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外存储空间,k为序列中Max-Min+1
桶排序 (bucket sort)— O(n); 需要 O(k) 额外存储空间

代码连接:https://www.cnblogs.com/maluning/p/7944809.html https://blog.csdn.net/hellozhxy/article/details/79911867

Copyright © zs0813.com 2020 all right reserved,powered by Gitbook该文件修订时间: 2020-10-09 10:41:12

results matching ""

    No results matching ""