前情提要，本系列写于大二上学期的寒假，想要效仿前人实现一下数据结构教材上所列出的算法，从排序开始一点一点实现，，此章涉及到快速排序，希尔排序，归并排序，堆排序，基数排序。

快速排序

首先我们应该懂得快速排序的原理，这样才能根据原理写出对应的算法。 快速排序使用函数递归来进行排序，在无序序列中选择一个元素X作为基准数，将数组S分为三个部分，Sa是小于X的集合，Sb是大于X的集合，再分别对Sa与Sb进行快速排序。 在这里不深究快速排序的诸多改进方法，只求实现最基本的快排。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

void quickSort(int *a,int start,int end){
    int flag,turn=1;
    int l = start,r=end;
    if(end-start <= 0)return;
    flag = a[l];
    while(l < r){
        if(turn == 1){
            if(a[r] >= flag){
                r--;
            }
            else{
                turn = 0;
                a[l] = a[r];
	              l++;
            }
        }
        else{
            if(a[l] <= flag){
                l++;
            }
            else{
                turn = 1;
                a[r] = a[l];
                r--;
            }
        }
    }
    a[l] = flag;
    quickSort(a,start,l-start);//l-start是左边的长度
    quickSort(a,l+1,end - l);//end-l是右边的长度
}

上面的代码是我根据原理自己写出来的，算不上简洁。在数组内元素与基准数比较大小时加入了一个标记量，判断下一次与基准数比较的元素位置，想着或许可以改进一下，不需要标记就能完成程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void quickSort(int *a,int start,int end){
	int l = start,r=end,flag = a[l];
	if(end-start <= 0) return;
	while(l < r){
	    while(l < r && a[r] >= flag){
	        r--;
	    }
	    if(l < r){
	        a[l++] = a[r];
	    }
	    while(l < r && a[l] <= flag){
	        l++;
	    }
	    if(l < r){
	        a[r--] = a[l];
	    }
	}
	a[l] = flag;
	quickSort(a,start,l-start);//l-start是左边的长度
	quickSort(a,l+1,end - l);//len - (l-start) - 1 是右边的长度
}

到网上看了看别人的代码之后，发现可以用两个while来完成快排。原本最外面的while的功能被其中的两个while分担，这种思想与用栈深度优先遍历二叉树时向前进到左子树末尾的思想比较相似。

小结

首先快排是不稳定的，排序算法的不稳定性并不是排序过后序列还不是严格非递增或者非递减，而是在数组中有相同元素时，这个相同的元素可能会发生交换，比如序列 533^ 每次选择序列的第一个元素作为基准数，在排序后就变为了 3^35 。 然后对快排进行分析，很明显空间复杂度为O(1),当序列为逆序时，543

希尔排序

希尔排序是直接插入排序的一种改进，将无序序列以一定的增量划分为多个子序列，再对排好一趟的序列以更小的增量划分为子序列（要求这些增量之间是互质的，不然肯定会发生重复对有序序列排序的情况）在增量已经取得较小时，进行一次直接插入排序，就完成了希尔排序的全过程。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void shellSort(int *a,int start,int end,int i){//i为增量
    int f;
    for (int q = 0; q<i; q++) {
        for (int j=start+i+q; j<=end; j+=i) {
            if(j>=start+i && a[j]<a[j-i]){
                f = a[j];
                int k = j;
                while (k>=start+i && f<a[k-i]) {
                    a[k] = a[k-i];
                    k-=i;
                }
                a[k] = f;
            }
        }
    }
}

上面根据原理我自己写出的代码，实际就是插入排序的变体，因为无法确定增量的选择，所以将增量单独列出。这样在调用时只好调用多次，每次都写上不同的增量。 关于希尔排序增量序列，就不在此文的研究范围内了，会在之后的补充中逐步加入

小结

希尔排序也是不稳定的，533^6 按增量为2排序 排序后为 3^356 这时候两个3的位置已经交换了，说明希尔排序并不稳定。

未完待续…