排序可能是接触最早而又直到现在仍然感觉魅力无穷的算法了，总结了一下十几种排序算法(都以升序为例)。参考了很多大大写的文章，大都是百度算法搜索出来的，感谢@百度
步骤:
将数列从第1位开始遍历至第N-1位，每次比较当前位与后一位大小并排好序。
这样1遍之后,数列中最大的数已移至最后一位（像冒泡泡一样）
对于移除数列中最后一位元素的新数列，继续上述操作，直至新数列长为1停止，则排序完成
伪代码：
Bubble_sort(sequence)
{
for i from 1 to length(sequence)
//不考虑最后一位，构造新数列
for j from 1 to length(sequence)-1-i
if compare_num(j,j+1)>0
swap(j,j+1)
} 复杂度:
一般情况下，需要进行n-1 趟排序，且每趟排序比较n-i 次关键字。时间复杂度即为
\[ f(n) = {n \cdot(n-i) \over 2 } =n^2 + \cdots =O(n^2)\]
步骤
伪代码
Selection_sort(sequence)
{
for i from 1 to length(sequence)
min_index=i
min_val=sequence[i]
for j from i to length(sequence)
if compare_num(j,val)<0
//如果第j个元素比标记元素小，则将标记元素置为第j个元素
//标记元素与第i个元素交换
}复杂度
第1次循环比较N-1次，第2次是N-2次，.......，最后一次循环比较1次。所以比较的次数为
\[f(n)=(n-1)+(n-2)+...+1=\frac{(n-1+1) \cdot n}{2} = O(n^2)\]
虽然选择排序和冒泡排序时间复杂度一样，但是实际上交换的次数很少，最多交换n-1次，而冒泡排序最坏情况下要交换\(n^2/2\)次。所以前者性能更优。
i 个数，依次与前面第i-1,i-2 ...个数j 比较，直到j<i 为止，期间如果不满足条件则将第j个数移到j+1 的位置上。i 个数放到第j 个位置上i从第1位到第N-1位 ，则排序完成。Insertion_sort(A)
for j from 2 to length(A)
key=A[j]
//将A[j]插入已排好序的数列A[1..j-1]中
i=j-1
while i>0 and A[i]>key
A[i+1]=A[i]
i = i-1
A[i+1]=key复杂度
$ f(n)=a \cdot n^2 +b \cdot n + c = O(n^2)$
步骤
定义增量序列\(D_M > D_{M-1} > \ldots > D_1=1\)
对于每个\(D_k\) 进行“\(D_k\) —间隔”排序（k=M,M-1,...1）
"\(D_k\) —间隔"排序指将原数列中第\(1, 1+D_k ,1+ 2 \cdot D_k , 1+ m \cdot D_k, \ldots\)个数组成的新数列排序。
结论：“\(D_k\) —间隔”有序的序列，在执行“\(D_{k-1}\)—间隔”排序后，仍然是“\(D_k\) —间隔”有序的。
插入排序实际上是增量为1的排序（比较的两数间隔），而希尔排序是一种分组插入排序，依次比较相隔\(D_k（k=M,M-1\ldots 1）\) 的两元素。
伪代码
Shell_sort(A)
{
//希尔增量序列
for (D=length(A)/2; D>0; D/=2)
{
//插入排序
for (P= D ; P<length(A); P++ )
{
temp=A[P];
for (i=P;i>=D and A[i- D]>temp; i-=D)
A[i]=A[i-D];
A[i]=temp;
}
}
}复杂度
最坏情况下\[f(n)=n^2\] ,但其复杂度还与增量序列的选取有关。例如，
Hibbard增量序列
Sedgewick增量序列
步骤
伪代码
Quick_sort(A,left,right)
{
base=A[left]
if left>=right
return
i,j=left,right
while i<j
{
while A[j]>=base and i<j
j--;
while A[i]<=base and i<j
i++;
if i<j
swap(A[i],A[j])
}
A[left],A[j]=A[j],base
Quick_sort(A,left,i-1);
Quick_sort(A,i+1,right);
}复杂度
最坏情况下，可以认为每次数列分成的两个区间各包含n-1和1个元素，则
\(f(n)=\theta(n^2)\)
平均情况下，\(f(n)=O(n\log(n))\)
步骤
分解：将n 个元素分成各含n/2 个元素的子序列；
解决：用合并排序法对两个子序列递归地排序；（子序列长度为1时递归停止，即单个元素视为已排好序）
合并：合并两个已排序的子序列以得到排序结果。
伪代码
Merge(A,p,q,r)
{
x,y=q-p+1,r-q
将A[p..q]复制到B[1..x], 将A[q+1..r]复制到C[1..y]
i,j,k=1,1,p
while i<=x and j<=y do
if B[i]<=C[j]
then
A[k]=B[i]
i=i+1
else
A[k]=C[j]
j=j+1
k=k+1
if i>x then 将C[j..y]复制到A[k..r]
else 将B[i..x]复制到A[k..r]
}
Merge_sort(A,p,r)
{
if p<r
then q=floor((p+r)/2)
Merge_sort(A,p,q)
Merge(A,p,q,r)
}复杂度
\(f(n)=O(n\log(n))\)
步骤
地精排序又称侏儒排序，取名源自一种荷兰的花园精灵。思想也很简单，
从首位开始，与相邻下一位比较，若小于下一位，则继续向后走；若大于下一位，交换两数位置，并回退到上一位，继续比较。到末位停止，排序完成。
伪代码
Gnome_sort(A)
{
i=0;
while i<length(A)
if i==0 or A[i-1] <= A[i]
i++;
else
{
swap(A[i],A[i-1]);
i--;
}
}复杂度
在最好情况下，也就是数列已经排好的情况下，只要遍历一遍数列,\(f(n)=O(n)\) ;
但在最坏情况下，数列是反序时，每前进一步都要回退数步，此时\(f(n)=O(n^2)\) ,与冒泡排序相同。
步骤
鸡尾酒排序的排序效果像是“左右摇摆”，因为它每次循环是执行两次冒泡排序，将最大数移至数列末位，最小数移至数列首位。然后去掉首末位，在新数列继续两次排序......
伪代码
Cocktail_sort(A,left,right)
{
while left <right
bubblesort(A,left,right);//冒泡排序找到其中最大的
right--;
bubblesort(A,left,right);//冒泡排序找到其中最小的
left++;
}复杂度
它是对冒泡排序的改进，减少了遍历次数，一次循环便能找到两个数的正确位置；性能略优于冒泡排序；
但面对大数据量时，其复杂度与冒泡排序相同。\(f(n)=O(n^2)\)
步骤
相对于冒泡排序是串行算法，奇偶排序可用于并行计算。即奇数列排一次序，偶数列排一次序，再反复，直至不再需要交换数据，则排序完成。
伪代码
Odd_even_sort(A)
{
change_flag,odd_flag=1,1;
while change_flag
{
change_flag=0;
for(i=1-odd_flag;i+1<length(A);i+=2)
{
if A[i]>A[i+1]
swap(A[i],A[i+1])
change_flag=1;
}
odd_flag=1-odd_flag;
}
}复杂度
它的复杂度是\(O(n^2)\) ,但由于是并行计算，在多核的情况下，可以达到\({n^2}\over{m/2}\) ,m为排序分段 个数。
步骤
堆：一颗顺序存储的完全二叉树。当结点元素都不大于子结点元素时，称为小根堆；当结点元素都不小于子结点元素时，称为大根堆。
首先构造一个大根堆（此时根结点为最大值）
交换第一个和最后一个元素，将最后一个元素出列。
将剩下元素重新调整为大根堆。
不断重复上述2，3，直至堆中只剩最后一个元素，元素出列。则所有出列的元素已排好序。
关于如何构造一个大根堆，这里有一个线性时间复杂度的调整算法。
? 当一个堆以数组形式顺序存储时，记父节点为i ，则子节点为2i和2i+1 。反之，可得到已知子节点的情形下，根节点的位置。
伪代码
Build_Heap(A,i,N)
{
/*
* i->起点； N->数列长度
*/
//j表示当前位置
for(int j=i+N-1;j>i;j--)
{
//由于计算机中是以0为起点
if(j为奇数)
parent=j/2;
else
parent=(j-1)/2;
if A[parent]<A[j]
swap(A[parent],A[j]);
}
}
Heap_sort(A)
{
N=length(A)；
Build_Heap(A,0,N)；
for(int i=N-1；i>0；i--)
{
swap(A[0],A[i])；
Build_Heap(A,0,i);
}
}复杂度
构造最大堆为\(O(n)\) ,堆排序的时间复杂度为\(O(n\log(n))\)
步骤
梳排序改良自冒泡排序和快速排序，旨在消除数尾部的小数值。冒泡排序中，只比较相邻两项，间距为1，而梳排序中的间距是在循环中以固定比率递减，通常递减率设为1.3 ，起始间距为数列长度，且间距递减至1，则排序已大致排好序，最后用冒泡排序修正。
伪代码
Comb_sort(A)
{
for(int step=length(A); step >0; step/=1.3)
{
//开始冒泡排序
for( int i=0; i+step<N; i++)
{
if(A[i]>A[i+step])
{
swap(A[i],A[i+step]);
}
}
}
}复杂度
梳排序效率比冒泡排序高得多，\(f(n)=O({n^2 \over 2^p} )\) ,p为递减率
步骤
圈排序是遍历n个数，并且每次在形成一个完整的圈时停止。某元素应在的位置是数列中所有比它小的元素个数。例，
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 56 | 42 | 12 | 31 | 26 | 73 | 原始数列 |
| null | 42 | 12 | 31 | 56 | 73 | 从第1个数开始，比56小的数有4个，将它移到位置4;关键字为26 |
| null | 26 | 12 | 31 | 56 | 73 | 比26小的数有1个，将它移到位置1；关键字为42 |
| null | 26 | 12 | 42 | 56 | 73 | 比42小的数有3个，将它移到位置3；关键字31 |
| null | 26 | 31 | 42 | 56 | 73 | 比31小的数有2个，将它移到位置2；关键字12 |
| 12 | 26 | 31 | 42 | 56 | 73 | 比12小的数有0个，将它移至位置0；此处为空，第一个圈完成。 |
| 12 | 26 | 31 | 42 | 56 | 73 | 第2个数26，就在位置1处，该圈完成 |
| ... | ... | ... | ... | ... | ... | 第i 个数 ...,该圈完成 |
| 12 | 26 | 31 | 42 | 56 | 73 | 排序完成 |
伪代码
Cycle_sort(A)
{
for i from 0 to length(A)-1
{
//标记圈的起点
item=A[i];
pos=i;
//统计比当前item小的元素个数count
//将A[i]移至位置count处，并且新的item=A[count],pos=count
while pos!=i
{
//统计比当前item小的元素个数count
//将A[i]移至位置count处，并且新的item=A[count],pos=count
}
}
}复杂度
任何情况下，\(f(n)=O(n^2)\) 它的实际效率比冒泡还低。
步骤
基数排序是按位比较的，取最大数有n位,有2种思路，LSD从低位开始排，MSD从高位开始排。
LSD首先按照最低位排升序，然后按次低位排序，按次次低位排序.....按最高位排序。
最终数列以升序排列。
伪代码
Radix_sort(A)
{
val=Get_max(A);
digits=Get_digits(val);
for(int i=0; i<digits;i++)
{
B=Get_num(A,i);//获取数列中每个元素的第i位数字
sort(A,B);//将B按照取值依次放入r个分类里，并按照B中的顺序放置A
}
}复杂度
设待排数列长度为n ,比较关键字有k个，则有k趟循环，分配时间复杂度为\(O(n)\) ,收集放置的复杂度为\(O(r)\) ,则基数排序\(f(n)=O(k(n+r))\)
步骤
伪代码
复杂度
原文：https://www.cnblogs.com/zhangs7/p/10435772.html