我们在排序（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;
       }
      else
         return left;
   }
   else
   {
      if(a[mid]>a[right])
      {
         return mid;
      }
      else if(a[left]<a[right])
      {
         return left;
      }
      else
         return 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;
       }
      else
         return left;
   }
   else
   {
      if(a[mid]>a[right])
      {
         return mid;
      }
      else if(a[left]<a[right])
      {
         return left;
      }
      else
         return right;
   }
   }
}
   

结论：左边做key，右边先走，可以保证相遇位置的值比key要小。
相遇的场景分析:
L遇R:R先走，停下来，R停下条件是遇到比key小的值，R停的位置一定比key小，L没有找大的，遇到R停下了
R遇L:R先走，找小，没有找到比key小的，直接跟L相遇了。L停留的位置是上一轮交换的位置，上一轮交换，把比key小的值，换到L的位置了

相反，让右边做key，左边先走，可以保证相遇位置的值比key要大。