十大排序算法
2021-05-20 18:01:15 0 举报AI智能生成
10大排序算法
作者其他创作
大纲/内容
冒泡排序（Bubble Sort）
概括
重复走访要排序的数列，通过两两比较相邻记录的排序码。
排序过程中每次从后往前冒一个最小值，且每次能确定一个数在序列中的最终位置。
排序过程中每次从后往前冒一个最小值，且每次能确定一个数在序列中的最终位置。
1. 基本思想
冒泡排序是一种交换排序，核心是冒泡，把数组中最小的那个往上冒，冒的过程就是和他相邻的元素交换。
2. 实现逻辑
通过两层循环控制：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
通过两层循环控制：
- 第一个循环（外循环），负责把需要冒泡的那个数字排除在外；
- 第二个循环（内循环），负责两两比较交换。
3. 动图演示
4. 性能分析
- 平均时间复杂度：O(N^2)
- 最佳时间复杂度：O(N)
- 最差时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 排序方式：In-place
- 稳定性：稳定
冒泡排序涉及相邻两两数据的比较，故需要嵌套两层 for 循环来控制;
外层循环 n 次，内层最多时循环 n – 1次、最少循环 0 次，平均循环(n-1)/2;
所以循环体内总的比较交换次数为：n*(n-1) / 2 = (n^2-n)/2 ;
按照计算时间复杂度的规则，去掉常数、去掉最高项系数，其复杂度为O(N^2) ;
外层循环 n 次，内层最多时循环 n – 1次、最少循环 0 次，平均循环(n-1)/2;
所以循环体内总的比较交换次数为：n*(n-1) / 2 = (n^2-n)/2 ;
按照计算时间复杂度的规则，去掉常数、去掉最高项系数，其复杂度为O(N^2) ;
5. 优化改进
改进方法①
场景一：
在某次遍历中如果没有数据交换，说明整个数组已经有序。若初始序列就是排序好的，如果用基础的冒泡排序方法，仍然还要比较O(N^2)次，但无交换次数。
改进思路：
通过设置标志位来记录此次遍历有无数据交换，进而可以判断是否要继续循环，设置一个flag标记，当在一趟序列中没有发生交换，则该序列已排序好，但优化后排序的时间复杂度没有发生量级的改变。
在某次遍历中如果没有数据交换，说明整个数组已经有序。若初始序列就是排序好的，如果用基础的冒泡排序方法，仍然还要比较O(N^2)次，但无交换次数。
改进思路：
通过设置标志位来记录此次遍历有无数据交换，进而可以判断是否要继续循环，设置一个flag标记，当在一趟序列中没有发生交换，则该序列已排序好，但优化后排序的时间复杂度没有发生量级的改变。
改进方法②
场景二：
如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了。
改进思路：
记录某次遍历时最后发生数据交换的位置pos，这个位置之后的数据显然已经有序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。
6. 代码实现
子主题
冒泡排序毕竟是一种效率低下的排序方法，在数据规模很小时，可以采用。数据规模比较大时，建议采用其它排序方法。
插入排序（Insertion Sort）
概括
插入排序操作类似于摸牌并将其从大到小排列。每次摸到一张牌后，根据其点数插入到确切位置。
1. 基本思想
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
2. 实现逻辑
① 从第一个元素开始，该元素可以认为已经被排序
② 取出下一个元素，在已经排序的元素序列中从后向前扫描
③如果该元素（已排序）大于新元素，将该元素移到下一位置
④ 重复步骤③，直到找到已排序的元素小于或者等于新元素的位置
⑤将新元素插入到该位置后
⑥ 重复步骤②~⑤
3. 动图演示
4. 性能分析
- 平均时间复杂度：O(N^2)
- 最差时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 排序方式：In-place
- 稳定性：稳定
最差时间情况: 降序数组
对于比较次数, 第一次比较0次, 第2次比较1次, 第n次比较n-1次. 所以平均比较次数=[0+1+2+....+(n-1)]/n=[(n-1)*n/2]/n=(n-1)/2
故最差负杂度=O(n * (n-1)/2)=O(n^2 - n/2)=O(n^2)
对于比较次数, 第一次比较0次, 第2次比较1次, 第n次比较n-1次. 所以平均比较次数=[0+1+2+....+(n-1)]/n=[(n-1)*n/2]/n=(n-1)/2
故最差负杂度=O(n * (n-1)/2)=O(n^2 - n/2)=O(n^2)
最优的空间复杂度为开始元素已排序，则空间复杂度为 0；
最差的空间复杂度为开始元素为逆排序，则空间复杂度最坏时为 O(N);
平均的空间复杂度为O(1)
最差的空间复杂度为开始元素为逆排序，则空间复杂度最坏时为 O(N);
平均的空间复杂度为O(1)
5. 算法优化改进
改进方法①
直接插入排序每次往前插入时，是按顺序依次往前查找，数据量较大时，必然比较耗时，效率低。
改进思路： 在往前找合适的插入位置时采用二分查找的方式，即折半插入。
改进思路： 在往前找合适的插入位置时采用二分查找的方式，即折半插入。
6. 代码实现
插入排序不适合对于数据量比较大的排序应用。
但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。
尤其当数据基本有序时，采用插入排序可以明显减少数据交换和数据移动次数，进而提升排序效率。
在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序。
但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。
尤其当数据基本有序时，采用插入排序可以明显减少数据交换和数据移动次数，进而提升排序效率。
在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序。
希尔排序（Shell Sort）
概括
递减gap分组插入排序
1. 基本思想
a. 设定gap<n, 将整个待排元素序列分割成gap个子序列, 分别对每个子序列进行插入排序
b. 依次缩减gap, 重复进行a步骤, 直至gap<0
因为插入排序在元素基本有序的情况下效率是很高的, 因此在最后一次插入排序前, 使序列基本有序就很有必要
b. 依次缩减gap, 重复进行a步骤, 直至gap<0
因为插入排序在元素基本有序的情况下效率是很高的, 因此在最后一次插入排序前, 使序列基本有序就很有必要
2. 实现逻辑
① 先取一个小于n的整数gap, 把数组逻辑分成gap个小数组
② 所有距离为gap的倍数的元素放在同一个小数组中，在各数组内进行插入排序
③ 递减gap, 重复步骤2, 直至gap<0
② 所有距离为gap的倍数的元素放在同一个小数组中，在各数组内进行插入排序
③ 递减gap, 重复步骤2, 直至gap<0
3. 具体说明
4. 性能分析
希尔算法是非稳定的排序算法
最优时间复杂度：O(n*log(n))
最坏时间复杂度：O(n^2)，间隔序列取得很糟糕；O(n*(log(n))^2)，间隔序列取得已知条件下比较好
平均时间复杂度：取决于间隔序列如何取
最坏空间复杂度：总共O(n)，辅助O(n)
-----------------
希尔排序的效率取决于增量值gap的选取，时间复杂度并不是一个定值。
开始时，gap取值较大，子序列中的元素较少，排序速度快，克服了直接插入排序的缺点；其次，gap值逐渐变小后，虽然子序列的元素逐渐变多，但大多元素已基本有序，所以继承了直接插入排序的优点，能以近线性的速度排好序。
最优的空间复杂度为开始元素已排序，则空间复杂度为 0；最差的空间复杂度为开始元素为逆排序，则空间复杂度为 O(N);平均的空间复杂度为O(1)希尔排序并不只是相邻元素的比较，有许多跳跃式的比较，难免会出现相同元素之间的相对位置发生变化。比如上面的例子中希尔排序中相等数据5就交换了位置，所以希尔排序是不稳定的算法。
最优时间复杂度：O(n*log(n))
最坏时间复杂度：O(n^2)，间隔序列取得很糟糕；O(n*(log(n))^2)，间隔序列取得已知条件下比较好
平均时间复杂度：取决于间隔序列如何取
最坏空间复杂度：总共O(n)，辅助O(n)
-----------------
希尔排序的效率取决于增量值gap的选取，时间复杂度并不是一个定值。
开始时，gap取值较大，子序列中的元素较少，排序速度快，克服了直接插入排序的缺点；其次，gap值逐渐变小后，虽然子序列的元素逐渐变多，但大多元素已基本有序，所以继承了直接插入排序的优点，能以近线性的速度排好序。
最优的空间复杂度为开始元素已排序，则空间复杂度为 0；最差的空间复杂度为开始元素为逆排序，则空间复杂度为 O(N);平均的空间复杂度为O(1)希尔排序并不只是相邻元素的比较，有许多跳跃式的比较，难免会出现相同元素之间的相对位置发生变化。比如上面的例子中希尔排序中相等数据5就交换了位置，所以希尔排序是不稳定的算法。
5. 实现
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能，交换不相邻的元素以对数组的局部进行排序，最终用插入排序将局部有序的数组排序。
选择排序（Selection Sort）
概括
在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
重复步骤1，直到所有元素均排序完毕
1. 基本思想
选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面，或者将最大值放在最后面。
但是过程不同，冒泡排序是通过相邻的比较和交换。
而选择排序是通过对整体的选择，每一趟从前往后查找出无序区最小值，将最小值交换至无序区最前面的位置。
但是过程不同，冒泡排序是通过相邻的比较和交换。
而选择排序是通过对整体的选择，每一趟从前往后查找出无序区最小值，将最小值交换至无序区最前面的位置。
2. 实现逻辑
① 第一轮从下标为 1 到下标为 n-1 的元素中选取最小值，若小于第一个数，则交换
② 第二轮从下标为 2 到下标为 n-1 的元素中选取最小值，若小于第二个数，则交换
③ 依次类推下去……
3. 动图演示
注：红色表示当前最小值，黄色表示已排序序列，绿色表示当前位置。
4. 复杂度分析
平均时间复杂度：O(N^2)
最佳时间复杂度：O(N^2)
最差时间复杂度：O(N^2)
空间复杂度：O(1)
排序方式：In-place
稳定性：不稳定
----------
选择排序的交换操作介于和(n-1)次之间。选择排序的比较操作为n(n-1)/2次之间。选择排序的赋值操作介于0和3(n-1)次之间。
比较次数O(n^2)，比较次数与关键字的初始状态无关，总的比较次数N = (n-1) + (n-2) +…+ 1 = n x (n-1)/2。交换次数O(n)，最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。
最佳时间复杂度：O(N^2)
最差时间复杂度：O(N^2)
空间复杂度：O(1)
排序方式：In-place
稳定性：不稳定
----------
选择排序的交换操作介于和(n-1)次之间。选择排序的比较操作为n(n-1)/2次之间。选择排序的赋值操作介于0和3(n-1)次之间。
比较次数O(n^2)，比较次数与关键字的初始状态无关，总的比较次数N = (n-1) + (n-2) +…+ 1 = n x (n-1)/2。交换次数O(n)，最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。
5. 优化改进
①二元选择排序
改进思路：
简单选择排序，每趟循环只能确定一个元素排序后的定位。
根据之前冒泡排序的经验，我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。
改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。
简单选择排序，每趟循环只能确定一个元素排序后的定位。
根据之前冒泡排序的经验，我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。
改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。
②堆排序
堆排序是一种树形选择排序，是对直接选择排序的有效改进。
6. 代码实现
·
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
快速排序（Quick Sort)
概括
基准比较交换 + 分治法
1.基本思想
通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
2. 实现逻辑
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
1. 从数列中挑出一个元素，称为 “基准”（pivot），
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
3. 动图演示
4. 复杂度
平均时间复杂度：O(NlogN)
最佳时间复杂度：O(NlogN)
最差时间复杂度：O(N^2)
空间复杂度：根据实现方式的不同而不同
5. 代码实现
6. 优化改进
场景分析： 递归是一种使用相同的方法，通过解决问题的子集以达到解决整个问题的方法，是一种使用有限代码解决“无限”计算的方法。在C/C++语言中递归表现在函数对自身的直接/间接的调用上，在实现上，递归依赖于语言的运行时调用堆栈，使用堆栈来保存每一次递归调用返回时所需要的条件。递归通常具有简洁的编码和清晰的思路，但这种简洁是有代价的。一方面，是函数调用的负担；另一方面，是堆栈占用的负担（堆栈的大小是有限的）。
改进思路：递归转化为迭代。迭代的思想主要在于，在同一栈帧中不断使用现有数据计算出新的数据，然后使用新的数据来替换原有数据。
快速排序在排序算法中具有排序速度快，而且是就地排序等优点，使得在许多编程语言的内部元素排序实现中采用的就是快速排序，很多面试题中也经常遇到。对于其算法的改进，除了刚刚上文中提到的意外，根据实际场景还有诸多改进方法，包括对小序列采用插入排序替代，三平均划分，三分区划分等改进方法
归并排序（Merge Sort）
概括
归并排序，是创建在归并操作上的一种有效的排序算法。
算法是采用分治法（Divide and Conquer）
归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。
1. 基本思想
归并排序是用分治思想，分治模式在每一层递归上有三个步骤：
- 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
- 解决（Conquer）：用合并排序法对两个子序列递归的排序。
- 合并（Combine）：合并两个已排序的子序列已得到排序结果。
2. 实现逻辑
① 将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素
② 将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
③ 重复步骤②，直到所有元素排序完毕
3. 动图演示
上图中首先把一个未排序的序列从中间分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一个一个的数据，
再把这些数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列。
上图中首先把一个未排序的序列从中间分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一个一个的数据，
再把这些数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列。
4. 复杂度分析
- 平均时间复杂度：O(nlogn)
- 最佳时间复杂度：O(nlogn)
- 最差时间复杂度：O(nlogn)
- 空间复杂度：O(n)
- 排序方式：In-place
- 稳定性：稳定
不管元素在什么情况下都要做这些步骤，所以花销的时间是不变的，所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都是一样的为：O( nlogn )
归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为: O(n)。
归并排序算法中，归并最后到底都是相邻元素之间的比较交换，并不会发生相同元素的相对位置发生变化，故是稳定性算法。
归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为: O(n)。
归并排序算法中，归并最后到底都是相邻元素之间的比较交换，并不会发生相同元素的相对位置发生变化，故是稳定性算法。
堆排序（Heap Sort）
概括
利用大(小)堆顶的根节点最大(小)特性, 进行排序
堆的相关概念
堆一般指的是二叉堆，顾名思义，二叉堆是完全二叉树或者近似完全二叉树
堆的性质
① 是一棵完全二叉树
② 每个节点的值都大于或等于其子节点的值，为最大堆；反之为最小堆。
堆的存储
一般用数组来表示堆，下标为 i 的结点的父结点下标为(i-1)/2；其左右子结点分别为 (2i + 1)、(2i + 2)
堆的操作
在堆的数据结构中，堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作：
① 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
② 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
③ 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
① 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
② 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
③ 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
1. 基本思想
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。
① 将待排序的序列构造成一个最大堆，此时序列的最大值为根节点
② 依次将根节点与待排序序列的最后一个元素交换
③ 再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列
① 将待排序的序列构造成一个最大堆，此时序列的最大值为根节点
② 依次将根节点与待排序序列的最后一个元素交换
③ 再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列
2. 实现逻辑
① 先将初始的R[0…n-1]建立成最大堆，而堆顶是最大元素。
② 再将堆顶R[0]和无序区的最后一个记录R[n-1]交换，由此得到新的无序区R[0…n-2]和有序区R[n-1]
③ 循环步骤1和步骤2
④ 直到无序区只有一个元素为止。
② 再将堆顶R[0]和无序区的最后一个记录R[n-1]交换，由此得到新的无序区R[0…n-2]和有序区R[n-1]
③ 循环步骤1和步骤2
④ 直到无序区只有一个元素为止。
3. 动图演示
4. 复杂度分析
- 平均时间复杂度：O(nlogn)
- 最佳时间复杂度：O(nlogn)
- 最差时间复杂度：O(nlogn)
- 稳定性：不稳定
堆排序其实也是一种选择排序，是一种树形选择排序。只不过直接选择排序中，为了从R[1…n]中选择最大记录，需比较n-1次，然后从R[1…n-2]中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过，而树形选择排序恰好利用树形的特点保存了部分前面的比较结果，因此可以减少比较次数。对于n个关键字序列，最坏情况下每个节点需比较log2(n)次，因此其最坏情况下时间复杂度为nlogn。堆排序为不稳定排序，不适合记录较少的排序。
5. 实现堆排序
假设给定一个组无序数列{100,5,3,11,6,8,7}，带着问题，我们对其进行堆排序操作进行分步操作说明。
1、如何由一个无序序列建成一个最大堆？
1. 利用堆特性:
- 下标为 i 的结点的父结点下标为(i-1)/2
- 其左右子结点分别为 (2i + 1)、(2i + 2)
①首先我们将数组我们将数组从上至下按顺序排列，转换成二叉树：一个无序堆。
每一个三角关系都是一个堆，上面是父节点，下面两个分叉是子节点，两个子节点俗称左孩子、右孩子；
每一个三角关系都是一个堆，上面是父节点，下面两个分叉是子节点，两个子节点俗称左孩子、右孩子；
②转换成无序堆之后，我们要努力让这个无序堆变成最大堆(或是最小堆)，即每个堆里都实现父节点的值都大于任何一个子节点的值。
③从最后一个堆开始，即 数据最后一个节点 + 其兄弟节点 + 父节点 组成的堆开始；
首先对比左右孩子，最大孩子的值比父节点的值大 -> 父节点与最大孩子节点交换
如果发生交换，要检测子节点是否为其他堆的父节点，如果是，递归进行同样的操作。
首先对比左右孩子，最大孩子的值比父节点的值大 -> 父节点与最大孩子节点交换
如果发生交换，要检测子节点是否为其他堆的父节点，如果是，递归进行同样的操作。
④循环n次
2、如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？
①首先将堆顶元素 与 最底部位置旳元素交换, n-1
②将数组[0,....,n-1]重新进行最大堆处理
③重复步骤1, 步骤2, 直至数组元素个数为1
6. 代码实现
计数排序（Counting Sort）
计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。
1. 基本思想
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），然后进行分配、收集处理：
① 分配。扫描一遍原始数组，以当前值-minValue作为下标，将该下标的计数器增1。
② 收集。扫描一遍计数器数组，按顺序把值收集起来。
用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），然后进行分配、收集处理：
① 分配。扫描一遍原始数组，以当前值-minValue作为下标，将该下标的计数器增1。
② 收集。扫描一遍计数器数组，按顺序把值收集起来。
2. 实现逻辑
① 找出待排序的数组中最大和最小的元素
② 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
③ 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
④ 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
3. 动图演示
举个例子，假设有无序数列nums=[2, 1, 3, 1, 5], 首先扫描一遍获取最小值和最大值，maxValue=5, minValue=1，于是开一个长度为5的计数器数组counter
- (1) 分配
- (2) 收集
4. 复杂度分析
计数排序需要两个额外的数组用来对元素进行计数和保存排序的输出结果，所以空间复杂度为O(k+n)。
计数排序的一个重要性质是它是稳定的：具有相同值的元素在输出数组中的相对次序与它们在输入数组中的相对次序是相同的。也就是说，对两个相同的数来说，在输入数组中先出现的数，在输出数组中也位于前面。
计数排序的稳定性很重要的一个原因是：计数排序经常会被用于基数排序算法的一个子过程。我们将在后面文章中介绍，为了使基数排序能够正确运行，计数排序必须是稳定的。
- 平均时间复杂度：O(n + k)
- 最佳时间复杂度：O(n + k)
- 最差时间复杂度：O(n + k)
- 空间复杂度：O(n + k)
计数排序需要两个额外的数组用来对元素进行计数和保存排序的输出结果，所以空间复杂度为O(k+n)。
计数排序的一个重要性质是它是稳定的：具有相同值的元素在输出数组中的相对次序与它们在输入数组中的相对次序是相同的。也就是说，对两个相同的数来说，在输入数组中先出现的数，在输出数组中也位于前面。
计数排序的稳定性很重要的一个原因是：计数排序经常会被用于基数排序算法的一个子过程。我们将在后面文章中介绍，为了使基数排序能够正确运行，计数排序必须是稳定的。
5. 代码实现
桶排序（Bucket Sort）
桶排序（Bucket sort）的工作的原理是将数组分到有限数量的桶里。
每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来得到有序序列。
每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来得到有序序列。
1. 基本思想
桶排序的思想近乎彻底的分治思想。
- 桶排序假设待排序的一组数均匀独立的分布在一个范围中，并将这一范围划分成几个子范围（桶）。
- 然后基于某种映射函数f ，将待排序列的关键字 k 映射到第i个桶中 (即桶数组B 的下标i) ，那么该关键字k 就作为 B[i]中的元素 (每个桶B[i]都是一组大小为N/M 的序列 )。
- 接着将各个桶中的数据有序的合并起来 : 对每个桶B[i] 中的所有元素进行比较排序 (可以使用快排)。然后依次枚举输出 B[0]….B[M] 中的全部内容即是一个有序序列
2. 实现逻辑
- 设置一个定量的数组当作空桶子。
- 寻访序列，并且把项目一个一个放到对应的桶子去。
- 对每个不是空的桶子进行排序。
- 从不是空的桶子里把项目再放回原来的序列中。
3. 动图演示
4. 复杂度分析
平均时间复杂度：O(n + k)
最佳时间复杂度：O(n + k)
最差时间复杂度：O(n ^ 2)
空间复杂度：O(n * k)
稳定性：稳定
桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
最佳时间复杂度：O(n + k)
最差时间复杂度：O(n ^ 2)
空间复杂度：O(n * k)
稳定性：稳定
桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
5. 代码实现
关键在于如何将序列散列分布到桶中, 且需要有序
桶排序是计数排序的变种，它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。把计数排序中相邻的m个”小桶”放到一个”大桶”中，在分完桶后，对每个桶进行排序（一般用快排），然后合并成最后的结果。
基数排序（Radix Sort）
基数排序（Radix sort）是一种非比较型整数排序算法。
1. 基本思想
原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
- MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序
- LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序
2. 实现逻辑
① 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
② 从最低位开始，依次进行一次排序。
③ 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
3. 动图演示
在上图中，首先将所有待比较数字统一为统一位数长度，接着从最低位开始，依次进行排序。
- 按照个位数进行排序。
- 按照十位数进行排序。
- 按照百位数进行排序。
- 排序后，数列就变成了一个有序序列。
4. 复杂度分析
时间复杂度：O(k*N)
空间复杂度：O(k + N)
稳定性：稳定
设待排序的数组R[1..n]，数组中最大的数是d位数，基数为r（如基数为10，即10进制，最大有10种可能，即最多需要10个桶来映射数组元素）。
处理一位数，需要将数组元素映射到r个桶中，映射完成后还需要收集，相当于遍历数组一遍，最多元素数为n，则时间复杂度为O(n+r)。所以，总的时间复杂度为O(d*(n+r))。
基数排序过程中，用到一个计数器数组，长度为r，还用到一个rn的二位数组来做为桶，所以空间复杂度为O(rn)。
基数排序基于分别排序，分别收集，所以是稳定的。
空间复杂度：O(k + N)
稳定性：稳定
设待排序的数组R[1..n]，数组中最大的数是d位数，基数为r（如基数为10，即10进制，最大有10种可能，即最多需要10个桶来映射数组元素）。
处理一位数，需要将数组元素映射到r个桶中，映射完成后还需要收集，相当于遍历数组一遍，最多元素数为n，则时间复杂度为O(n+r)。所以，总的时间复杂度为O(d*(n+r))。
基数排序过程中，用到一个计数器数组，长度为r，还用到一个rn的二位数组来做为桶，所以空间复杂度为O(rn)。
基数排序基于分别排序，分别收集，所以是稳定的。
基数排序与计数排序、桶排序这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；
基数排序不是直接根据元素整体的大小进行元素比较，而是将原始列表元素分成多个部分，对每一部分按一定的规则进行排序，进而形成最终的有序列表。
算法性能评估术语言
稳定：如果a原本在b前面，而a=b时，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b时，排序之后a可能出现在b的后面。
内排序：所有排序操作都在内存中完成。
外排序：通常是由于数据太大，不能同时存放在内存中，根据排序过程的需要而在外存与内存之间 数据传输才能进行。
时间复杂度：时间频度，一个算法执行所耗费的时间。算法中通常用数据比较次数与数据移动次数 进行衡量。
空间复杂度：算法执行所需要的内存大小。
排序算法性能
O(n^2)
冒泡排序 - 迭代左右交换
选择排序 - 迭代选最大
插入排序 - 迭代扑克插入
希尔排序 - gap分组递减插入
O(nlogn)
归并排序 - 分治+合并
堆排序 - 堆化
快速排序 - 递归基准交换
O(n+k)
基数排序 - 拆分整数+分区间排序
计数排序
桶排序 - 分区间排序
0 条评论
下一页
