本文转自 Yikun博客

    1. 概述 

不稳定的排序：稳定性一个形象的比喻，本来有两个并列第三，一排序把原来并列的顺序给变了。 比如：选择排序、快速排序、堆排序、希尔排序； 

    2. 冒泡排序 

每次都把未排序的第一个作为起始点，然后逐渐冒泡上升，之后未排序区越来越少，最终排序完成 

// 冒泡排序 
void bubble_sort(int a[], int n) 
{ 
int i = 0; 
int j = 0; 
for (i=0; i<n-1; i++) 
{ 
// 比较相邻元素，若a[j]比a[j+1]大，则交换 
// a[j]就像一个气泡一样“浮”到合适位置了 
for(j=0; j<n-1-i; j++) 
{ 
if(a[j]>a[j+1]) 
{ 
swap(&a[j], &a[j+1]); 
} 
} 
} 
}

    3. 选择排序 

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 

// 选择排序 
void select_sort(int a[], int n) 
{ 
int i=0,j=0,min=0; 
for (i=0; i < n-1; i++) 
{ 
min = i; 
// 找到最小值 
for (j=i+1; j <= n-1; j++) 
{ 
if (a[min] > a[j]) 
min = j; 
} 
if(min != i) 
{ 
swap(&a[min], &a[i]); 
} 
} 
}

    4. 插入排序 

每次排序从未排序区取一个“牌”，然后往前插入(包括了两步：大的往后移，把牌放到合适位置)。 

// 插入排序 
void insert_sort(int a[], int n) 
{ 
int i=0; 
int j=0; 
int tmp=0; 
for (i = 1; i < n; i++) 
{ 
// 取牌 
tmp = a[i]; 
// 往前插的起始位置 
j = i - 1; 
// 大的a[j]都放后面，寻找出j 
while ((j >= 0) && a[j] > tmp) 
{ 
// 往后放一个 
a[j+1] = a[j]; 
j--; 
} 
// 放到该放的位置 
a[j+1]=tmp; 
} 
}

另外还有种思路，把数据后移的过程换成交换的过程 

// 插入排序，选中的牌冒泡向前插入 
void insert_sort_2(int a[], int n) 
{ 
int i=0; 
int j=0; 
//通过i选牌 
for (i=1; i < n; i++) 
{ 
// 冒泡向前插入(i-1 --> 0) 
for (j=i-1; j>=0 && a[j] > a[j + 1]; j--) 
{ 
swap(&a[j], &a[j+1]); 
} 
} 
print_a(a, n); 
}

    5. 希尔排序 

对插入排序再加一个步长的循环就是希尔排序了，例如 

[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]

按照5步长排序，则相当于按列先进行排序(实际是通过下标实现的) 

13 14 94 33 82 
25 59 94 65 23 
45 27 73 25 39 
10

排序后结果为 

10 14 73 25 23 
13 27 94 33 39 
25 59 94 65 82 
45

多次循环后，只需要最终步长为1即可。 

// 希尔排序 
void shell_sort(int a[], int n) 
{ 
int i=0; 
int j=0; 
int tmp=0; 
int gap=0; 
while (gap <= n) 
{ 
gap = gap*3 + 1; 
} 
while (gap > 0) 
{ 
// 取牌 
for (i = gap; i < n; i++) 
{ 
// 冒泡向前插入(i-gap : gap : 0), 保证每列ok 
for (j = i - gap; (j >= 0) && (a[j] > a[j + gap]); j = j - gap) 
{ 
swap(&a[j], &a[j+gap]); 
} 
} 
gap = (gap-1) / 3; 
} 
}

    6. 快速排序 

每次迭代都选出一个基准，左边放小的，右边放大的，最终迭代完成。 

// 快速排序分区 
static int partition(int a[], int p, int r) 
{ 
int x=0; 
int i=0; 
int j=0; 
// x为基准 
x = a[r]; 
// i为界限,发现小于x的，就i++，再放到i处 
i = p-1; 
for (j=p; j<= r-1; j++) 
{ 
if (a[j]<=x) 
{ 
i++; 
swap(&a[i], &a[j]); 
} 
} 
// 至此，所有小于x的都到i左边了(a[0]~a[i-1])，a[r]是x，因此交换a[i+1]和a[r] 
swap(&a[i+1], &a[r]); 
return i+1; 
} 
// 快速排序 
void quick_sort(int a[], int p, int r) 
{ 
int q=0; 
if (p < r) 
{ 
// 在数据集之中，选择一个元素作为"基准"（pivot） 
// 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边 
q = partition(a, p, r); 
// 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。 
quick_sort(a, p, q-1); 
quick_sort(a, q+1, r); 
} 
}