一个排序算法是一种能将一串数据依照特定排序方式进行排列的一种算法.最常用到的排序方式是数值顺序以及字典顺序.有效的排序算法在一些算法中是重要的,如此这些算法才能得到正确解答.排序算法也用在处理文字数据以及产生人类可读的输出结果.基本上,排序算法的输出必须遵守下列两个原则:
- 输出结果为递增序列(递增是针对所需的排序顺序而言)
- 输出结果是原输入的一种排列,或是重组
常见的排序和复杂度如下:
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | - | O(1) | 交换 | 稳定 |
| 选择排序 | O(n^2) | - | O(1) | 选择 | 不稳定 |
| 插入排序 | O(n^2) | - | O(1) | 插入 | 稳定 |
| 希尔排序 | O(nlog(n)) | O(n^2) | O(1) | 插入 | 不稳定 |
| 归并排序 | O(nlog(n)) | - | O(n) | 合并 | 稳定 |
| 快速排序 | O(nlog(n)) | O(n^2) | O(log(n)) | 交换 | 不稳定 |
| 堆排序 | O(nlog(n)) | - | O(1) | 选择 | 不稳定 |
| 计数排序 | O(n+k) | - | O(k) | 稳定 | |
| 基数排序 | O(n*k) | - | O(n+k) | 稳定 | |
| 桶排序 | O(n+k) | - | O(k) | 稳定 |
- 均按从小到大排列
- k 代表数据个数
- n 代表数据规模
这个算法的名字由来是因为越小的元素会经由交换慢慢浮到数列的顶端.
步骤为:
- 比较相邻的元素.如果第一个比第二个大,就交换他们两个.
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.这步做完后,最后的元素会是最大的数.
- 针对所有的元素重复以上的步骤,除了最后一个.
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较.
bubbleSort(A)
for i := 1 to length(A) - 1 do
for j := 0 to length(A)- 1 - i do
if (A[j] > A[j+1]) then
swap(A[j],A[j+1])
快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists).
步骤为:
- 从数列中挑出一个元素,称为基准(pivot),
- 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边).在这个分割结束之后,该基准就处于数列的中间位置.这个称为分割(partition)操作.
- 递归(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序.
quickSort(A, lo, hi)
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p - 1)
quicksort(A, p + 1, hi)
partition(A, lo, hi)
pivot := A[hi]
i := lo
for j := lo to hi - 1 do
if A[j] < pivot then
swap(A[i],A[j])
i := i + 1
swap(A[i],A[hi])
return i
插入排序是一种简单直观的排序算法.它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.插入排序在实现上,通常采用in-place排序(即只需用到 O(1) 的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间.
步骤为:
- 从第一个元素开始,该元素可以认为已经被排序
- 取出下一个元素,在已经排序的元素序列中从后向前扫描
- 如果该元素(已排序)大于新元素,将该元素移到下一位置
- 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
insertionSort(A)
for i := 1 to length(A) - 1 do
j := i - 1
while j >= 0 and A[j] > A[i] do
A[j+1] := A[j]
j := j - 1
A[j+1] := A[i]
希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本.但希尔排序是非稳定排序算法.
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
- 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
- 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位
希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录"基本有序"时,再对全体记录进行依次直接插入排序.
步骤为:
- 选择一个增量序列
t1,t2,...,tk,其中ti > tj,tk = 1 - 按增量序列个数 k,对序列进行 k 趟排序
- 每趟排序,根据对应的增量
ti,将待排序列分割成若干长度为m的子序列,分别对各子表进行直接插入排序.仅增量因子为1时,整个序列作为一个表来处理,表长度即为整个序列的长度.
步长的选择是希尔排序的重要部分.只要最终步长为1任何步长序列都可以工作.算法最开始以一定的步长进行排序.然后会继续以一定步长进行排序,最终算法以步长为1进行排序.当步长为1时,算法变为普通插入排序,这就保证了数据一定会被排序.
一般常用的步长为 n / (2 ^ i),已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,...),该序列的项来自 9 * 4 ^ i - 9 * 2 ^ i +1 和 2 ^ i + 2 * ( 2 ^ (i + 2) - 3 ) + 1
选择排序是一种简单直观的排序算法.它的工作原理如下.首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕.
insertionSort(A)
for i := 0 to length(A) - 1 do
min := i;
for j := i + 1 to length(A)- 1 - i do
if (A[min] > A[j]) then
min := j
swap(A[j],A[j+1])
堆排序是指利用堆这种数据结构所设计的一种排序算法,堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于它的父节点.
在堆的数据结构中,堆中的最大值总是位于根节点堆中定义以下几种操作:
- 最大堆调整: 将堆的末端子节点作调整,使得子节点永远小于父节点
- 创建最大堆: 将堆中的所有数据重新排序
- 堆排序: 移除位在第一个数据的根节点,并做最大堆调整的递归运算
归并排序是创建在归并操作上的一种有效的排序算法该算法是采用分治法的一个非常典型的应用,且各层分治递归可以同时进行(并行计算).
归并算法步骤为:
- 申请两块空间,分别用来存放两个已经排序序列
- 设定两个指针,最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素,选择相对小的元素放入到原始空间对应位置,并移动指针到下一位置
- 重复步骤3直到某一指针到达序列尾
- 将另一序列剩下的所有元素直接复制到原始空间序列尾
mergeSort(A,li,hi)
if li < hi then
mid := (li + hi) / 2
merge(mergeSort(A, li, mid),mergeSort(A, mid + 1, hi))
下面讲到的三种特殊的排序方式是在某些特殊情况下实现的线性排序:
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中.作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数.
通过一次遍历记录每个数字出现的次数,然后通过遍历{键-次数}数据对输出排序结果.
基数排序也是利用了桶的概念: 将整数按每个位上的数字分组,然后再进行排序,排序完成后再按照更高位进行分组.
桶排序或所谓的箱排序是一个排序算法,工作的原理是将数组分到有限数量的桶里.每个桶再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)
步骤为:
- 设置一个定量的数组当作空桶
- 寻访序列,并且把项目一个一个放到对应的桶
- 对每个不是空的桶进行排序
- 从不是空的桶里把项目再放回原来的序列中