我們在排序（1）中說到選擇排序的代碼：

void SelectSort(int* a,int n)
{int begin=0,end=n-1;int mini=begin,max=begin;for(int i=begin+1;i<=end;i++){if(a[i]>a[max]){maxi=i;}if(a[i]<a[mini]){mini=i;}++begin;--end;}Swap(&a[beign],&a[mini]);Swap(&a[end],&a[maxi]);
}

那么當我們解決下面這個問題的時候：當開始時，begin=0，end=7，mini=begin=0，maxi=begin=0。i=1，1小于0，所以mini=1。a[mini]=1，++begin，begin=1，--end，end=6。此時最大值是9（begin），最小值是1（i）。

i=2，begin=1,end=6。

當begin和max重合，就會出現

4 3 5 6?

正確的代碼應該是這樣的：

void SelectSort(int* a,int n)
{int begin=0,end=n-1;int mini=begin,maxi=begin;for(int i=begin+1;i<=end;i++){if(a[i]>a[max]){maxi=i;}if(a[i]<a[mini]){mini=i;}}Swap(&a[begin],&a[mini]);if(maxi==begin){maxi=mini;}Swap(&a[end],&a[maxi]);++begin;--end;
}

快速排序

把小的換到左邊，把大的換到右邊。

動圖鏈接地址如下：

https://gitee.com/bithange/113-issues/raw/master/24%E5%B9%B4-05%E6%9C%8827%E6%97%A5--%E6%8E%92%E5%BA%8F/%E5%8A%A8%E5%9B%BE/hoare.gif?單趟快排代碼如下：

void QuickSort(int* a,int left,int right)
{int key=a[left];int begin=left,end=right;while(begin<end){//右邊找小while(begin<end&&a[end]>=key)//加等號，相等的值放左邊或者右邊都無所謂{--end;}//左邊找大while(begin<end&&a[begin]>key){++begin;}Swap(&a[begin],&a[end]);}Swap(key,&a[begin]);
}

這段代碼有一些問題，讓我們逐個解決吧！

首先，記錄值只是復制了一個值，比如
int a = 10;
int b = a;
修改b的值對a的值沒有影響
記錄索引，修改的就是索引對應的值

什么情況下不需要對數組進行分割了呢？一種是這個區間只有一個值，另一只種是這個區間不存在。（結束條件）
?

void QuickSort(int* a,int left,int right)
{int keyi=left;int begin=left,end=right;if(left>right)return;while(begin<end){//右邊找小while(begin<end&&a[end]>=key)//加等號，相等的值放左邊或者右邊都無所謂{--end;}//左邊找大while(begin<end&&a[begin]>key){++begin;}Swap(&a[begin],&a[end]);}Swap(&a[keyi],&a[begin]);keyi=begin;//[left,keyi-1] keyi [keyi+1,right]'QuickSort(a,left,keyi-1);QuickSort(a,keyi+1,right);
}

選key如果每一次都在最前面，那么就不合理，我們期望選擇的key每次都是最中間的值。

1隨機數選key

2三數取中（把選中的數挪到最左邊）

int GetMid(int* a,int left,int right)
{int mid=(left+right)/2;if(a[left]<a[mid]){if(a[mid]<a[right]){return mid;}else if(a[left]<a[right]){return right;}elsereturn left;}else{if(a[mid]>a[right]){return mid;}else if(a[left]<a[right]){return left;}elsereturn right;}
}

但是當需要排序的數字只有幾個時，需要進行的趟數就多了，而且很浪費。所以，在進行判斷時，我們需要加上一個條件。那么在這樣一個數字較少的情況下，我們應該選擇哪種排序呢？希爾排序的優勢就是讓大的數更快跳到后面，小的數更快跳到前面。

int GetMid(int* a,int left,int right)
{if(right-left+1<10)//小區間優化,不再遞歸分割排序，減少遞歸次數{InsertSort(a+left,right-left+1);}else{int mid=(left+right)/2;if(a[left]<a[mid]){if(a[mid]<a[right]){return mid;}else if(a[left]<a[right]){return right;}elsereturn left;}else{if(a[mid]>a[right]){return mid;}else if(a[left]<a[right]){return left;}elsereturn right;}}
}

結論：左邊做key，右邊先走，可以保證相遇位置的值比key要小。
相遇的場景分析:
L遇R:R先走，停下來，R停下條件是遇到比key小的值，R停的位置一定比key小，L沒有找大的，遇到R停下了
R遇L:R先走，找小，沒有找到比key小的，直接跟L相遇了。L停留的位置是上一輪交換的位置，上一輪交換，把比key小的值，換到L的位置了

相反，讓右邊做key，左邊先走，可以保證相遇位置的值比key要大。