排序归纳
常用排序算法原理简介及C实现
排序可能是接触最早而又直到现在仍然感觉魅力无穷的算法了，总结了一下十几种排序算法(都以升序为例)。参考了很多大大写的文章，大都是百度算法搜索出来的，感谢@百度
目录
冒泡排序
步骤:
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。将数列从第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)\]
选择排序
步骤
- 从数列中找到最小元素
- 将该元素与数列的第一个元素交换（即选择了最小的元素，归位）
- 排除数列的第一个元素，生成一个新数列，继续1，2，3，直到数列中元素个数为1。
伪代码
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个位置上 - 重复上述1，2，遍历
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增量序列
- \(D_k=2^k-1\) (保证相邻元素为互质)
- 最坏情况下，\(f(n)=O(n^{\frac32})\) (已存在证明)
- 有猜想， \(f_{avg}(n)= O(n^{\frac54})\) (待证明)
Sedgewick增量序列
- {1,5,19,41,109,...},计算公式为\(9 \times 4^i -9 \times 2^i +1\)
- 猜想，\(f_{avg}(n)=O(n^{\frac76}), f_{worst}(n)=O(n^{\frac43})\) ，未证明。
快速排序
步骤
- 选择一个基准数
- 分别设置哨兵甲乙指向数列的首位和末位，哨兵乙不断向前进，并且每次比较当前数与基准数的大小，若小于基准数则停止；哨兵甲不断向后进，并且每次比较当前数与基准数的大小，若大于基准数则停止。
- 交换当前哨兵甲乙指向的数，继续按上述规则令甲乙行进，直到甲乙指向同一位置停止，将基准数与该位置交换；此时能保证基准数左侧的数都不大于基准数，基准数右侧的数都不小于基侧数。
- 将原数列划为两个新数列左侧和右侧，分别重复上述步骤，直到生成的数列只有一个元素，此时排序完成。
伪代码
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;关键字为26null 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)\) 它的实际效率比冒泡还低。
基数排序(LSD)
步骤
基数排序是按位比较的，取最大数有
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))\)
双调排序
步骤
伪代码
复杂度
完整的C语言实现
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <malloc.h>
#include <string.h>
typedef int Element_Type;
void gene_nums(Element_Type *a, int N)
{
srand(time(NULL));
for (int i = 0; i < N; i++)
*(a + i) = rand();
}
void disp_nums(Element_Type *a, int N)
{
for (int i = 0; i < N; i++)
printf("%-7d", *(a + i));
printf("\n");
}
void write2file(char a[], Element_Type A[], int N)
{
FILE *fp = NULL;
fp = fopen(a, "w+");
for (int i = 0; i < N; i++)
fprintf(fp, "%d\n", A[i]);
fclose(fp);
}
//selection sort
void Selection_sort(Element_Type A[], int N)
{
Element_Type min_val;
int min_index;
for (int i = 0; i < N; i++)
{
min_val = A[i];
min_index = i;
for (int j = i; j < N; j++)
{
if (A[j] < min_val)
{
min_val = A[j];
min_index = j;
}
}
A[min_index] = A[i];
A[i] = min_val;
}
}
//insertion sort
void Insertion_sort(Element_Type A[], int N)
{
Element_Type tmp;
int j;
for (int i = 0; i < N; i++)
{
tmp = A[i];
for (j = i; j > 0 && A[j - 1] > tmp; j--)
A[j] = A[j - 1];
A[j] = tmp;
}
}
//quick sort
void Quick_sort(Element_Type A[], int left, int right)
{
int i, j;
Element_Type base, tmp;
base = A[left];
if (left >= right)
return;
i = left;
j = right;
while (i < j)
{
while (A[j] >= base && i < j)
j--;
while (A[i] <= base && i < j)
i++;
if (i < j)
{
tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
}
A[left] = A[j];
A[j] = base;
Quick_sort(A, left, i - 1);
Quick_sort(A, i + 1, right);
}
//merge sort
void merge(Element_Type A[], int left, int mid, int right)
{
int x = mid - left + 1, y = right - mid;
int i = 0, j = 0, k = left;
Element_Type *B = (Element_Type *)malloc(x * sizeof(Element_Type));
Element_Type *C = (Element_Type *)malloc(y * sizeof(Element_Type));
for (; i < x; i++)
B[i] = A[left + i];
for (; j < y; j++)
C[j] = A[mid + j + 1];
i = j = 0;
while (i < x && j < y)
{
if (B[i] <= C[j])
A[k++] = B[i++];
else
A[k++] = C[j++];
}
while (i < x)
A[k++] = B[i++];
while (j < y)
A[k++] = C[j++];
free(B);
free(C);
}
void Merge_sort(Element_Type A[], int left, int right)
{
int mid;
if (left < right)
{
mid = (left + right) / 2;
Merge_sort(A, left, mid);
Merge_sort(A, mid + 1, right);
merge(A, left, mid, right);
}
}
//heap sort
void swap(Element_Type *a, Element_Type *b)
{
Element_Type tmp = *a;
*a = *b;
*b = tmp;
}
void max_heap(Element_Type A[], int i, int N)
{
int parent;
for (int j = i + N - 1; j > i; j--)
{
parent=(j%2)?(j/2):(j-1)/2;
if (A[parent] < A[j])
swap(&A[parent], &A[j]);
}
}
void Heap_sort(Element_Type A[], int N)
{
Element_Type tmp;
int i;
max_heap(A, 0, N);
for (int i = N - 1; i > 0; i--)
{
swap(&A[0], &A[i]);
max_heap(A, 0, i);
}
}
//radix sort(LSD)
Element_Type Get_max(Element_Type A[], int N)
{
Element_Type tmp = A[0];
for (int i = 0; i < N; i++)
if (A[i] > tmp)
tmp = A[i];
return tmp;
}
struct id_val
{
Element_Type a;
int index;
struct id_val *next;
};
int Getmodel(Element_Type val, int n)
{
while (--n)
{
val /= 10;
}
return val % 10;
}
void divide(Element_Type A[], struct id_val *P, int N, int base)
{
struct id_val *curr[10], *node;
int flag;
for (int i = 0; i < 10; i++)
curr[i] = &P[i];
for (int i = 0; i < N; i++)
{
node = (struct id_val *)malloc(sizeof(struct id_val));
node->a = A[i];
node->index = i;
node->next = NULL;
flag = Getmodel(A[i], base);
curr[flag]->next = node;
curr[flag] = node;
}
}
void conquer(Element_Type A[], struct id_val *P)
{
struct id_val *node;
for (int i = 0, j = 0; i < 10; i++)
{
node = &P[i];
while (node->next != NULL)
{
node = node->next;
A[j] = node->a;
j++;
}
}
}
void Radix_sort(Element_Type A[], int N)
{
struct id_val buckets[10];
Element_Type max_val;
int digits = 0, base = 0;
max_val = Get_max(A, N);
while (max_val != 0)
{
digits++;
max_val /= 10;
}
for (int i = 0; i < digits; i++)
{
base += 1;
divide(A, buckets, N, base);
conquer(A, buckets);
}
}
//comb sort
void Comb_sort(Element_Type A[], int N)
{
Element_Type tmp;
for (int step = N / 1.3; step > 0; step /= 1.3)
{
for (int i = 0; i + step < N; i++)
if (A[i] > A[i + step])
{
tmp = A[i];
A[i] = A[i + step];
A[i + step] = tmp;
}
}
}
//shell sort
void Shell_sort(Element_Type A[], int N)
{
Element_Type tmp;
int i, P, D, j;
/*希尔增量序列 1-> Hibbard; 2-> Sedgewick*/
do
{
j++;
D = 9 * (int)(pow(4, j)) - 9 * (int)(pow(2, j)) + 1;
} while (D < N);
for (j--; j >= 0; j--)
{
D = 9 * (int)(pow(4, j)) - 9 * (int)(pow(2, j)) + 1;
for (P = D; P < N; P++) /*插入排序*/
{
tmp = A[P];
for (i = P; i >= D && A[i - D] > tmp; i -= D)
A[i] = A[i - D];
A[i] = tmp;
}
}
}
//bubble sort
void Bubble_sort(Element_Type A[], int N)
{
Element_Type tmp;
for (int i = 0; i < N - 1; i++)
for (int j = 1; j < N-1-i; j++)
if (A[j - 1] > A[j])
{
tmp = A[j - 1];
A[j - 1] = A[j];
A[j] = tmp;
}
}
//cocktail sort
void Cocktail_sort(Element_Type A[], int left, int right)
{
Element_Type tmp;
while (left < right)
{
for (int i = left; i < right; i++)
{
if (A[i] > A[i + 1])
{
tmp = A[i + 1];
A[i + 1] = A[i];
A[i] = tmp;
}
}
right--;
for (int i = right; i > left; i--)
{
if (A[i] < A[i - 1])
{
tmp = A[i];
A[i] = A[i - 1];
A[i - 1] = tmp;
}
}
left++;
}
}
//odd-even sort
void Odd_even_sort(Element_Type A[], int N)
{
int change_flag = 1, odd_flag = 1;
Element_Type tmp;
while (change_flag)
{
change_flag = 0;
for (int i = 1 - odd_flag; i + 1 < N; i += 2)
if (A[i] > A[i + 1])
{
tmp = A[i];
A[i] = A[i + 1];
A[i + 1] = tmp;
change_flag = 1;
}
odd_flag = 1 - odd_flag;
}
}
//gnome sort
void Gnome_sort(Element_Type A[], int N)
{
Element_Type tmp;
int i = 0;
while (i < N)
{
if (i == 0 || A[i - 1] <= A[i])
i++;
else
{
tmp = A[i];
A[i] = A[i - 1];
A[--i] = tmp;
}
}
}
//cycle sort
void Cycle_sort(Element_Type A[], int N)
{
Element_Type item, tmp;
int pos;
for (int i = 0; i < N - 1; i++)
{
item = A[i];
pos = i;
for (int j = i + 1; j < N; j++)
if (A[j] < item)
pos += 1;
if (pos == i)
continue;
while (item == A[pos])
pos += 1;
tmp = A[pos];
A[pos] = item;
item = tmp;
while (pos != i)
{
pos = i;
for (int j = i + 1; j < N; j++)
if (A[j] < item)
pos += 1;
while (item == A[pos])
pos += 1;
tmp = A[pos];
A[pos] = item;
item = tmp;
}
}
}
//bitonic sort
//bogo sort 算了吧
int main(void)
{
int amount = 10000;
clock_t start, end;
Element_Type *A = (Element_Type *)malloc(amount * sizeof(Element_Type));
Element_Type *B = (Element_Type *)malloc(amount * sizeof(Element_Type));
gene_nums(A, amount);
printf("原始数据(%d个)\n\n", amount);
// disp_nums(A,amount);
memcpy(B, A, sizeof(Element_Type) * amount);
start = clock();
Shell_sort(B, amount);
end = clock();
printf("希尔排序耗时 %lf ms\n\n", difftime(end, start));
memcpy(B, A, sizeof(Element_Type) * amount);
start = clock();
Selection_sort(B, amount);
end = clock();
printf("选择排序耗时 %lf ms\n\n", difftime(end, start));
memcpy(B, A, sizeof(Element_Type) * amount);
start = clock();
Insertion_sort(B, amount);
end = clock();
printf("插入排序耗时 %lf ms\n\n", difftime(end, start));
memcpy(B, A, sizeof(Element_Type) * amount);
start = clock();
Quick_sort(B, 0, amount - 1);
end = clock();
printf("快速排序耗时 %lf ms\n\n", difftime(end, start));
memcpy(B, A, sizeof(Element_Type) * amount);
start = clock();
Merge_sort(B, 0, amount - 1);
end = clock();
printf("归并排序耗时 %lf ms\n\n", difftime(end, start));
memcpy(B, A, sizeof(Element_Type) * amount);
start = clock();
Bubble_sort(B, amount);
end = clock();
printf("冒泡排序耗时 %lf ms\n\n", difftime(end, start));
memcpy(B, A, sizeof(Element_Type) * amount);
start = clock();
Gnome_sort(B, amount);
end = clock();
printf("地精排序耗时 %lf ms\n\n", difftime(end, start));
memcpy(B, A, sizeof(Element_Type) * amount);
start = clock();
Cocktail_sort(B, 0, amount - 1);
end = clock();
printf("鸡尾酒排序耗时 %lf ms\n\n", difftime(end, start));
memcpy(B, A, sizeof(Element_Type) * amount);
start = clock();
Heap_sort(B, amount);
end = clock();
// disp_nums(B, amount);
printf("堆排序耗时 %lf ms\n\n", difftime(end, start));
memcpy(B, A, sizeof(Element_Type) * amount);
start = clock();
Comb_sort(B, amount);
end = clock();
printf("梳排序耗时 %lf ms\n\n", difftime(end, start));
memcpy(B, A, sizeof(Element_Type) * amount);
start = clock();
Odd_even_sort(B, amount);
end = clock();
printf("奇偶排序耗时 %lf ms\n\n", difftime(end, start));
memcpy(B, A, sizeof(Element_Type) * amount);
start = clock();
Radix_sort(B, amount);
end = clock();
printf("基数排序(LSD)耗时 %lf ms\n\n", difftime(end, start));
memcpy(B, A, sizeof(Element_Type) * amount);
start = clock();
Cycle_sort(B, amount);
end = clock();
printf("圈排序(LSD)耗时 %lf ms\n\n", difftime(end, start));
// disp_nums(B,amount);
// write2file("d:/2.txt", B, amount);
free(B);
free(A);
return 0;
}
更多精彩
