参考书籍是:《数据结构与算法分析-c语言描述，weiss著》
下图是排序算法时间复杂度等特性的一个总结：
下面详细总结一下各个算法，总结的方面包括：
- 每个算法的思想是什么？
- 每个算法的稳定性怎样？时间复杂度如何？
- 在什么情况下，算法出现最好情况 or 最坏情况？
- 每种算法的具体实现又是怎样的？
##各个排序算法的空间复杂度
大家往往只关心时间复杂度，而忽略了空间复杂度，所以这里讲空间复杂度提到前面来讲
冒泡排序，简单选择排序，堆排序，直接插入排序，希尔排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置，(另外遍历序列时自然少不了用一个变量来做索引)
快速排序空间复杂度为log2n(因为递归调用了)；归并排序空间复杂是O(n)，需要一个大小为n的临时数组.
这里的一个问题是，归并排序也递归了，为什么时间复杂度不是log2n?
答：
归并排序每次递归都要用到一个辅助表，长度与待排序的表长度相同，虽然递归次数是O(log2n)，但每次递归都会释放掉所占的辅助空间，所以下次递归的栈空间和辅助空间与这部分释放的空间就不相关了，因而空间复杂度还是O（n）。
快速排序空间复杂度只是在通常情况下才为O(log2n)，如果是最坏情况的话，很显然就要O(n)的空间了。当然，可以通过随机化选择pivot来将空间复杂度降低到O(log2n)。
##冒泡排序
###基本思想
通过无序区中相邻记录关键字间的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。
###时间复杂度
最好情况下：正序有序，则只需要比较n次。故，为O(n)
最坏情况下：逆序有序，则需要比较(n-1)+(n-2)+……+1，故为O(n*n)
###稳定性
排序过程中只交换相邻两个元素的位置。因此，当两个数相等时，是没必要交换两个数的位置的。所以，它们的相对位置并没有改变，冒泡排序算法是稳定的！
##代码
#define elementtype int
void bubble_sort(elementtype *array, int n) {
elementtype tmp;
int i = 0, j = 0;
for(; i < n - 1; i++) {
for(j = n -1; j > i; j--) {
if(array[j] < array[j - 1]) {
swap(array[j], array[j-1]);
}
}
}
}
##选择排序
###思想
首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。具体做法是：选择最小的元素与未排序部分的首部交换，使得序列的前面为有序。
选择排序是和冒泡排序差不多的一种排序。和冒泡排序交换相连数据不一样
的是，选择排序只有在确定了最小的数据之后，才会发生交换
###时间复杂度
最好情况：交换0次，但是每次都要找到最小的元素，因此大约必须遍历N*N次，因此为O(N*N)。减少了交换次数！
最坏情况：平均情况下：O(N*N)
###稳定性
由于每次都是选取未排序序列A中的最小元素x与A中的第一个元素交换，因此跨距离了，很可能破坏了元素间的相对位置，因此选择排序是不稳定的！
例如数组为5,5,3，第一次就会将第一个5和3交换
###代码
void select_sort(elementtype *array, int n) {
elementtype tmp;
int i, j, index;
if(array == NULL && n < 0)
exit(-1);
for(i = 0; i < n - 1; i++) {
index = i;
for(j = i + 1; j < n; j ++) {
if(array[j] < array[index])
index = j;
}
if(index != i) {
swap(array[i], array[index]);
}
}
}
##插入排序
###思想
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法—-插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
###时间复杂度
最好的情况：正序有序(从小到大)，这样只需要比较n次，不需要移动。因此时间复杂度为O(n)
最坏的情况：逆序有序,这样每一个元素就需要比较n次，共有n个元素，因此实际复杂度为O(n2)
平均情况：O(n2)
###稳定性
理解性记忆比死记硬背要好。因此，我们来分析下。稳定性，就是有两个相同的元素，排序先后的相对位置是否变化，主要用在排序时有多个排序规则的情况下。在插入排序中，K1是已排序部分中的元素，当K2和K1比较时，直接插到K1的后面(没有必要插到K1的前面，这样做还需要移动！！)，因此，插入排序是稳定的。
###代码
void insert_sort(elementtype *array, int n) {
elementtype tmp;
int p, j;
for(p = 1; p < n; p++) {
tmp = array[p];
for(j = p; j > 0 && array[j - 1] > tmp; j--) {
array[j]= array[j - 1];
}
array[j] = tmp;
}
}
##shell排序
###思想
Shell排序是DL. Shell于1959年针对直接插入排序算法改进提出的，属于插入排序的范畴，是对直接插入排序算法的改进。直接插入排序在基本有序时效率较高，并且在序列规模不是很大时效率也很高，Shell排序就是针对这两点进行改进。核心思想是：待排序列有n个元素，先取一个小于n的整数h1作为第一个增量，把待排序列以间隔h1分成若干子序列，子序列内使用插入排序；然后取第二个增量h2(< h1)，重复上述的划分和排序，
直至所取的增量hl = 1 (h1 > h2 > … > hl)。
这样不管序列多么庞大，在先前较大步长分组下每个子序列规模都不是很大，用直接插入效率很高；后面步长变小，子序列变大，但由于整体有序性越来越明显，排序效率依然很高，大大提高了时间效率。
###时间复杂度
最好情况：由于希尔排序的好坏和步长d的选择有很多关系，因此，目前还没有得出最好的步长如何选择(现在有些比较好的选择了，但不确定是否是最好的)。所以，不知道最好的情况下的算法时间复杂度。
最坏情况：O(N*logN)，最坏的情况下和平均情况下差不多。
平均情况：O(N*logN)
###稳定性
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
有个猜测，方便记忆：一般来说，若存在不相邻元素间交换，则很可能是不稳定的排序。
###代码
void shell_sort(elementtype *array, int n) {
elementtype tmp;
int increment, i, j;
for(increment = n/2; increment > 0; increment /= 2) {
for(i = increment; i < n; i++) {
tmp = array[i];
for(j = i; j >= increment && array[j - increment] > tmp; j -= increment)
array[j] = array[j - increment];
array[j] = tmp;
}
}
}
##堆排序
###思想
利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大(或者最小)的记录。也就是说，以最小堆为例，根节点为最小元素，较大的节点偏向于分布在堆底附近。
###时间复杂度
最坏情况下，接近于最差情况下：O(N*logN)，因此它是一种效果不错的排序算法
###稳定性
堆排序需要不断地调整堆，因此堆排序是一种不稳定的排序！
###代码
#define LeftChild(i) (2 * (i) + 1)
void perc_down(int *a, int i, int size)
{
int child;
int tmp = a[i];
for(; LeftChild(i) < size ; i = child)
{
child = LeftChild(i);
if(child != size - 1 && a[child] < a[child + 1])
child ++;
/***************************
* 提升儿子到父结点，
* 儿子结点的位置上存在空穴，
* 需要继续比较
**************************/
if(a[child] > tmp)
a[i] = a[child];
else/*不需要提升*/
break;
}
/*保存结点的位置找到*/
a[i] = tmp;
}
void build_maxheap(int *a, int size)
{
int step = 0;
/***************************************
* (size-1)/2实质是找到a[size-1]的父结点，
* 也就是倒数第二层，堆的创建过程是一个
* 由低层到高层逐渐创建的过程
**************************************/
for(step = (size - 1) / 2 ; step >= 0; -- step)
perc_down(a, step, size);
}
void heap_sort(int *a, int size)
{
int i = 0;
/*创建堆*/
build_maxheap(a,size);
for(; i < size; i++)
printf("%d ", a[i]);
printf("\n");
for(i = size - 1; i > 0; --i)
{
swap(a[i],a[0])；
/*更新堆的结构*/
perc_down(a,0,i);
}
}
##归并排序
###思想
多次将两个或两个以上的有序表合并成一个新的有序表。
###时间复杂度
最好的情况：一趟归并需要n次，总共需要logN次，因此为O(N*logN)
最坏的情况： 接近于平均情况，为O(N*logN)
说明：对长度为n的文件，需进行logN 趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
###稳定性
归并排序最大的特色就是它是一种稳定的排序算法。归并过程中是不会改变元素的相对位置的。
缺点是，它需要O(n)的额外空间。但是很适合于多链表排序。
###代码
/*left_start is the start of the left half, right_start is the start of the
right half*/
void merge(int *array, int *tmp_array, int left_start, int right_start, int right_end)
{
int left_end = right_start-1;
int length = right_end-left_start+1;
int tmp_pos = left_start;
while(left_start <= left_end && right_start <= right_end) {
if(array[left_start] <= array[right_start])
tmp_array[tmp_pos++] = array[left_start++];
else
tmp_array[tmp_pos++] = array[right_start++];
}
/*main loop*/
while(left_start <= left_end)
tmp_array[tmp_pos++] = array[left_start++];
while(right_start <= right_end)
tmp_array[tmp_pos++] = array[right_start++];
/*copy tmp_array back
注意这里必须使用right_end作为数组下标，不能用tmp_pos，因为此时的
tmp_pos已经越界了，上面多了一次++*/
int i;
for(i = 0; i < length; i++, right_end--)
array[right_end] = tmp_array[right_end];
}
void m_sort(int *array, int *tmp_array, int left, int right)
{
int mid;
if(left < right) {
mid = (left + right)/2;
m_sort(array, tmp_array, left, mid);
m_sort(array, tmp_array, mid+1, right);
merge(array, tmp_array, left, mid+1, right);
}
}
void merge_sort(int *array, int n)
{
if(array == NULL || n <= 0)
exit(-1);
int *tmp_array = (int *)malloc(n * sizeof(int));
if(tmp_array != NULL) {
m_sort(array, tmp_array, 0, n-1);
free(tmp_array);
}
else
exit(-1);
}
merge例程是精妙的。如果对merge的每个递归调用均局部声明一个临时数组，那么在任一时刻就可能有logN个临时数组处在活动期，这对于小内存的机器则是致命的。另一方面，如果merge例程动态分配并释放最小量临时内存，那么由malloc占用的时间会很多。严格测试指出，由于merge位于m_sort的最后一行，因此在任一时刻只需要一个临时数组活动，而且可以使用该临时数组的任意部分；我们将使用与输入数组array相同的部分。
#快速排序
###思想
它是由冒泡排序改进而来的。在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录放入适当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间(称为该记录归位),这个过程称作一趟快速排序。
###时间复杂度
最好的情况：因为每次都将序列分为两个部分(一般二分都复杂度都和logN相关)，故为 O(N*logN)
最坏的情况：序列基本有序，选取的枢轴元素为最大值或最小值时，退化为冒泡排序，几乎要比较N*N/2次，故为O(N*N)
如何避免最坏情况：为改进快速排序算法，随机选取界点或最左、最右、中间三个元素中的值处于中间的作为界点，通常可以避免原始序列有序的最坏情况。
###稳定性
由于每次都需要和中轴元素交换，因此原来的顺序就可能被打乱。如序列为 5 3 3 4 3 8 9 10 11会将3的顺序打乱。所以说，快速排序是不稳定的！
###代码
/*数据交换*/
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
int choose_pivot(int i,int j )
{
return((i+j) /2);
}
/*递归和分治*/
void quick_sort(int list[],int left,int right)
{
int key,i,j,k;
if(left < right)
{
k = (left + right) / 2;
swap(&list[left],&list[k]);
key = list[left];
i = left+1;
j = right;
while(1)
{
while((i < right) && (list[i] < key))
i++;
while((j > left) && (list[j] > key))
j--;
if( i < j) {
swap(&list[i],&list[j]);
//仅仅是为了防止死循环，见P183
if(list[i] == list[j] && list[i] == key) {
i++; //j--;
}
}
else
break;
}
// 交换两个元素的位置
swap(&list[left],&list[j]);
// 递归地对较小的数据序列进行排序
quick_sort(list,left,j-1);
quick_sort(list,j+1,right);
}
}
快排在数据少的时候是不占优势的，所以一般是在数据少的时候用插入排序，数据多的时候用快排。上面的快排程序对书上的程序作了修改，防止了死循环，但并不是一个好程序。比较好的快排实现可以看这里