排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
---|---|---|---|---|---|---|
冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 内部排序 | 稳定 |
选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 内部排序 | 不稳定 |
插入排序 | O(n2) | O(n) | O(n2) | O(1) | 内部排序 | 稳定 |
希尔排序 | O(nlogn) | O(nlog2n) | O(nlog2n) | O(1) | 内部排序 | 不稳定 |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 外部排序 | 稳定 |
快速排序 | O(nlogn) | O(nlogn) | O(n2) | O(logn) | 内部排序 | 不稳定 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 内部排序 | 不稳定 |
计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | 外部排序 | 稳定 |
桶排序 | O(n+k) | O(n+k) | O(n2) | O(n+k) | 外部排序 | 稳定 |
基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 外部排序 | 稳定 |
稳定性:在原序列中,r[i]=r[j]
,且r[i]
在r[j]
之前,而在排序后的序列中,r[i]
仍在r[j]
之前,则称这种排序算法是稳定的。
排序方式:
- 内部排序:指待排序列完全存放在内存中所进行的排序过程。
- 外部排序:指待排序记录存储在外存储器上,无法一次全部放入内存,期间需要内存与外存储器进行多次数据交换,最终完成的排序过程。
实现
设待排序序列长度为N
冒泡排序|Bubble Sort
基础算法
思想
- 比较相邻两个元素,如果前面的元素大于后面的元素,就将这两个元素交换。
- 对数组的第
0
个元素到N-1
个元素进行一次遍历后,最大的一个元素就移动到数组第N-1
个位置。N=N-1
,如果N
不为0
就重复前面二步,否则排序完成。
实现
|
|
优化算法
思想
基于基础算法,若有一次遍历中未发生数据交换,则排序已经完成。
实现
|
|
选择排序|Selection Sort
思想
- 对数组进行一次遍历,找到最小元素,并与待排序序列首个元素交换。
N=N-1
,若N>0
,重复第一步,若N=0
,排序完成。
实现
|
|
插入排序|Insertion Sort
思想
- 在待排序序列中取出一个元素,遍历已排序序列,将元素插入到合适位置。
N=N-1
,若N>0
,重复第一步,若N=0
,排序完成。
实现
|
|
希尔排序|Shell Sort
思想
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
实现
|
|
归并排序|Marge Sort
思想
分治法:
- 分割:递归地把当前序列平均分割成两半。
- 集成:在保持元素顺序的同时将上一步得到的子序列集成到一起(归并)。
实现
- 递归版
|
|
- 迭代版
|
|
快速排序|Quick Sort
思想
分治法:
- 挑选基准值:从数列中挑出一个元素,称为“基准”。
- 分割:重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(与基准值相等的数可以到任何一边)。
- 递归排序子序列:递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
实现
|
|
堆排序|Heap Sort
思想
- 建立一个堆
H[0...n-1]
。- 把堆首(最大值)和堆尾互换。
- 把堆的尺寸缩小
1
,把新的数组顶端数据调整到相应位置。- 重复步骤
2
,直到堆的尺寸为1
。
实现
|
|
计数排序|Count Sort
思想
- 找出待排序数组中最大和最小的元素。
- 统计数组中每个值为
i
的元素出现的次数,存入计数数组C
的第i-minValue
项。- 对所有的计数累加。
- 反向填充数组:将每个元素
i
放在新数组的第C[i]
项,每放一个元素就将C[i]
减去1
。
实现
|
|
桶排序|Bucket Sort
思想
- 设置一个定量的数组当作空桶。
- 遍历序列,并把元素放到对应的桶去。
- 对每一个非空桶进行排序。
- 再将非空桶中元素放回原队列。
实现
|
|
基数排序|Radix Sort
思想
- 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。
- 从最低位开始,依次进行一次排序。
- 排序完成以后,数列就变成一个有序序列。
实现
|
|