几种基本的排序方式，很容易混淆，每次过一段时间后又忘了，所以这次一次性将这些排序
方式集中整理了一下。首先是下面的分析表：
| 排序方式 | 英文缩写 | 算法思想 | 时间复杂度 | 稳定性 |
| 冒泡排序 | bubble_sort | 相邻比较，大数往后排 | N^2 | 稳定 |
| 交换排序 | exchange_sort | 前面的某个数逐个与后面的比较，小数往前移 | N^2 | 不稳定 |
| 插入排序 | insert_sort | 无序的数往有序中插入 | N^2 | 稳定 |
| 希尔排序 | shell_sort | 步长不为一的插入排序 | 介于NlgN和N^2之间 | 不稳定 |
| 快速排序 | quick_sort | 先分成大小两部分，再递归 | NlgN | 不稳定 |
| 归并排序 | merge_sort | 先分解成一个个数据，再递归合并 | NlgN | 稳定 |
| 堆排序 | heap_sort | 先建立大根堆，然后再将依次第一个数放到“最后”，下滤 | NlgN | 不稳定 |
然后我将列出他们的代码：
1.冒泡排序：
#include <stdio.h>
void swap(int *a, int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void bubble(int *array, int len)
{
int i,j;
for(i = 0; i < len; i++)
{
for(j = 0; j < len - i - 1;j++)
{
if(array[j] > array[j + 1])
swap(&array[j], &array[j + 1]);
}
}
}
这应该是最简单的排序方式，每次排序后，最大的那个值会放到最后，然后
将排序的长度缩短一个。
2.交换排序：
void select(int *array, int len)
{
int i,j;
for(i = 0; i < len; i++)
{
for(j = i; j < len; j++)
{
if(array[j] < array[i])
swap(&array[j], &array[i]);
}
}
}
交换排序和冒泡排序正好相反，每次将一个最小的数，排到前面，我任何交换排序
和选择排序基本没有区别，因为他们都是将小数往前拍，只不过，选择排序设置了一个
对比，而不是每次去互换
3.插入排序：
void insert(int *array, int len)
{
int i,j,key;
for(i = 1; i < len; i++)
{
key = array[i];
j = i;
while(j > 0 && array[j - 1] > key)
{
array[j] = array[j - 1];
j--;
}
array[j] = key;
}
}
插入排序的思想就是，前面的数据已经排好了，然后没有排好的数据，逐个插入进去，找到合适的位置。
4.希尔排序：
void shell(int *array, int len)
{
int i,j,tmp,increment;
for(increment = len / 2; increment > 0; increment /= 2)
{
for(i = increment; i < len; i++)
{
tmp = array[i];
for(j = i; j >= increment;j -= increment)
{
if(tmp < array[j - increment])
array[j] = array[j - increment];
else
break;
}
array[j] = tmp;
}
}
}
希尔排序可以说和插入排序思想基本一致，只是他不是去逐个比较，而是设定了步长。
效率要比前面三种都高很多，另外他的时间复杂度也和步长有关，计算起来很麻烦
5.快速排序：
void quick_sort(int *array, int left, int right)
{
if(left >= right - 1)
{
if((right == (left + 1)) && array[left] > array[right])
swap(&array[left], &array[right]);
return;
}
int i,j,cmp;
cmp = array[right];
i = left;
j = right - 1;
while(i < j)
{
while(array[i] < cmp && i < right)
i++;
while(array[j] > cmp && j > left)
j--;
if(i < j)
swap(&array[i], &array[j]);
}
swap(&array[i], &array[right]);
quick_sort(array, left, i - 1);
quick_sort(array, i + 1, right);
}
快速排序利用的是分治的思想，快速排序有很多可以改进的地方，例如参考元的选择，当需要排序的数据个数
很少时，可以采用其他方式等等。在这段代码中，需要注意的是：cmp = array[right]，而不是left，另外
if((right == (left + 1)) && array[left] > array[right])这个条件判断也很重要
6.归并排序：
void merge(int *array, int left, int mid, int right)
{
int tmp[right - left + 1];
int i = 0, save_left = left;
int center = mid;
while(left < mid && center <= right )
{
if(array[left] <= array[center])
tmp[i++] = array[left++];
else
tmp[i++] = array[center++];
}
while(left < mid)
tmp[i++] = array[left++];
while(center <= right)
tmp[i++] = array[center++];
i = 0;
while(save_left <= right)
array[save_left++] = tmp[i++];
}
void merge_sort(int *array, int left, int right)
{
if(left >= right - 1)
{
if(left == right - 1 && array[left] > array[right])
swap(&array[left], &array[right]);
return;
}
int mid = (left + right) / 2;
merge_sort(array, left, mid - 1);
merge_sort(array, mid, right);
merge(array, left, mid, right);
}
归并排序我觉得和快速排序的思想正好相反，一个是先分后合，一个是先合后分。
需要注意的是代码中的
merge_sort(array, left, mid - 1);
merge_sort(array, mid, right);
merge(array, left, mid, right);这三句是容易出问题的，
如果没有 if(left == right - 1 && array[left] > array[right])
swap(&array[left], &array[right]);这个判断，
那么就必须分解为： merge_sort(array, left, mid);
merge_sort(array, mid + 1, right);
merge(array, left, mid + 1, right);
这是因为： mid = （left + right） ／ 2
left <= mid < right
分解成：
merge_sort(array, left, mid - 1);
merge_sort(array, mid, right);
例如当left = 2，right = 3时，会导致死循环。
7.堆排序：
void down(int *arr, int i, int size)
{
int child;
int tmp;
for(tmp = arr[i]; leftchild(i) < size; i = child)
{
child = leftchild(i);
if(child != size - 1 && arr[child + 1] > arr[child])
child++;
if(tmp < arr[child])
arr[i] = arr[child];
else
break;
}
arr[i] = tmp;
}
void heap_sort(int *array, int len)
{
int i;
//建堆
for(i = len / 2; i >= 0; i--)
{
down(array, i, len);
}
i = len - 1;
//让最大值从堆中去掉，然后下滤
while(i > 0)
{
swap(&array[0], &array[i]);
down(array, 0, i);
i--;
}
}
需要注意的是，如果是升序排列，建的是大根堆，另外上面的程序可以避免额外的空间消耗，
因为他每次将最大值放到最后只有，堆的大小，减掉了一个。