## 排序
本章先简单介绍了插入排序，然后着重讲述快速排序。
**插入排序**
~~~
// 版本1
void InsertSort(int a[], int n) {
for(int i=1; i<n; ++i)
for(int j=i; j>0 && a[j-1]>a[j]; --j)
swap(a[j-1], a[j]);
}
// 版本2
void InsertSort1(int a[], int n) {
for(int i=1; i<n; ++i) {
int t = a[i];
int j = i;
for(; j>0 && a[j-1]>t; --j)
a[j] = a[j-1];
a[j] = t;
}
}
~~~
**快速排序**
> > 我们在这里规定：小于等于pivot的元素移到左边，大于pivot的元素移到右边。
**实现1：单向移动版本**
这个版本的关键是设置一快一慢两个指针，慢指针左侧都是小于等于pivot(包含慢指针所在位置)， 慢指针到快指针之间的值是大于pivot，快指针右侧的值是还未比较过的。示意图如下：
~~~
小于等于pivot ｜ 大于pivot ｜ ？
slow fast
~~~
快指针一次一步向前走，遇到大于pivot什么也不做继续向前走。遇到小于等于pivot的元素， 则慢指针slow向前走一步，然后交换快慢指针指向的元素。一次划分结束后， 再递归对左右两侧的元素进行快排。代码如下：
~~~
// 数组快排
void QSort(int a[], int head, int end) {
if(a==NULL || head==end) return;
int slow = head, fast = head + 1;
int pivot = a[head];
while(fast != end) {
if(a[fast] <= pivot)
swap(a[++slow], a[fast]);
++fast;
}
swap(a[head], a[slow]);
QSort(a, head, slow);
QSort(a, slow+1, end);
}
~~~
排序数组a只需要调用QSort(a, 0, n)即可。该思路同样可以很容易地在链表上实现：
~~~
// 单链表快排
void qsort(Node *head, Node *end){
if(head==NULL || head==end) return;
Node *slow = head, *fast = head->next;
int pivot = head->data;
while(fast != end){
if(fast->data <= pivot){
slow = slow->next;
swap(slow->data, fast->data);
}
fast = fast->next;
}
swap(head->data, slow->data);
qsort(head, slow);
qsort(slow->next, end);
}
~~~
排序头指针为head的单链表只需调用qsort(head, NULL)即可。
**实现2：双向移动版本**
版本1能能够快速完成对随机整数数组的排序，但如果数组有序， 或是数组中元素相同，快排的时间复杂度会退化成O(n2 )，性能变得非常差。
一种缓解方案是使用双向移动版本的快排，它每次划分也是使用两个指针， 不过一个是从左向右移动，一个是从右向左移动，示意图如下：
~~~
小于等于pivot ｜ ？ ｜ 大于pivot
i j
~~~
指针j不断向左移动，直到遇到小于等于pivot，就交换指针i和j所指元素 (指针i一开始指向pivot)；指针i不断向右移动，直到遇到大于pivot的， 就交换指针i和j所指元素。pivot在这个过程中，不断地换来换去， 最终会停在分界线上，分界线左边都是小于等于它的元素，右边都是大于它的元素。 这样就避免了最后还要交换一次pivot的操作，代码也变得美观许多。
~~~
int partition(int a[], int low, int high){
int pivot = a[low], i=low, j=high;
while(i < j){
while(i<j && a[j]>pivot) --j;
if(i < j) swap(a[i], a[j]);
while(i<j && a[i]<=pivot) ++i;
if(i < j) swap(a[i], a[j]);
}
return i;
}
void quicksort(int a[], int first, int last){
if(first<last){
int k = partition(a, first, last);
quicksort(a, first, k-1);
quicksort(a, k+1, last);
}
}
~~~
当然，如果对于partition函数，你如果觉得大循环内的两个swap还是做了些无用功的话， 也可以把pivot的赋值放到最后一步，而不是在这个过程中swap来swap去的。代码如下：
~~~
int partition(int a[], int low, int high){
int pivot = a[low], i=low, j=high;
while(i<j){
while(i<j && a[j]>pivot) --j;
if(i<j) a[i++] = a[j];
while(i<j && a[i]<=pivot) ++i;
if(i<j) a[j--] = a[i];
}
a[i] = pivot;
return i;
}
~~~
如果数组基本有序，那随机选择pivot(而不像上面那样选择第一个做为pivot) 会得到更好的性能。在partition函数里，我们只需要在数组中随机选一个元素， 然后将它和数组中第一个元素交换，后面的划分代码无需改变， 就可以达到随机选择pivot的效果。
**进一步优化**
对于小数组，用插入排序之类的简单方法来排序反而会更快，因此在快排中， 当数组长度小于某个值时，我们就什么也不做。对应到代码中， 就是修改quicksort中的if条件：
~~~
if(first < last) 改为 if(last-first > cutoff)
~~~
其中cutoff是一个小整数。程序结束时，数组并不是有序的， 而是被组合成一块一块随机排列的值，并且满足这样的条件： 某一块中的元素小于它右边任何块中的元素。我们必须通过另一种排序算法对块内进行排序。 由于数组是几乎有序的，因此插入排序比较适用。
这种方法结合了快排和插入排序，让它们去做各自擅长的事情，往往比单纯用快排要快。
深入阅读：Don Knuth的《The Art of Computer Programming, Volume 3: Sorting and Searching》；Robert Sedgewick的《Algorithms》； 《Algorithms in C》,《Algorithms in C++》,《Algorithms in Java》。
