will的个人博客

排序

1.快速排序

前后法

h版

思路

首先确定排序结束条件，然后设置左右指针和基准值，开始一趟排序使得以基准值为中心，左小右大，最后对左右分区继续进行排序。

快速排序的核心在于一趟排序该怎么写。左指针去找左边大于基准值的元素，右指针去找右边小于基准值的元素，然后交换左右指针的值。当左右指针相遇时，一趟循环就结束了，此时交换基准值和指针相遇处的元素。

启动顺序

主打一个反着启动！

注意！左右指针的启动顺序取决于基准值的选取。基准值如果从第一个元素中取出，那么右指针要先启动去找比基准值小的元素，以便最后右指针等待左指针靠近时，右指针一定指向小于基准值的元素。

启动的顺序选的不对的话，排序就会出错。。。以基准值为第一个元素为例，如果是左指针先启动，那么左指针就会在相遇之前找到大于基准值的元素，就变成左指针在此处等待右指针来找它，显然这是一个错误的位置，因为最后基准值会放置在这个位置，这个比基准值大的数就会被错误地放置到基准值左侧地区间中。

反之，如果基准值是从右边取出来的，左指针要先启动，以便最后左指针等待右指针的到来，左指针一定指向大于基准值的元素。

为什么左指针一定会指向大于基准值的元素呢？因为左指针它先启动去查找左边大于基准值的元素，遇到小于等于基准值的元素时直接++跳过了。左指针到达预定位置时，右指针还差几位才到达，虽然右指针会都跳过右边大于等于基准值的元素后，但是它难逃相遇的条件，相遇时指针就不再动了。（指针移动时i<j原来是使指针停下来的，两个指针是一定会相遇的，不会出现一个指针超过一个指针的情况）

c++代码

//hoare版
void quickSort(vector<int>& v,int start,int end){
    //长度小于2，说明排序完成
    if (start>=end)
    {
        return; 
    }
    //设置左右指针和基准值
    int i = start, j = end , key = end;
    //一趟排序
    while (i<j)//左右指针相遇处为比基准值大的数
    {
        //left和right相遇前，left先找到大于基准值的位置，等待right的靠近
        //首先,从左开始找比基准大的数，等号！！！
        while(i<j && v[i]<=v[key]){i++;};
        //从右开始找比基准小的数
        while(i<j && v[j]>=v[key]){j--;};
        //交换左右指针的元素
        swap(v[i],v[j]);
        //交换后下一次循环一定会移动指针，因为此处交换保证了左指针指向小数，右指针指向大数
    }
    //放置基准值，更新基准值指针到右指针处
    swap(v[key],v[j]);
    key=j;
    //左右区间分别排序
    quickSort(v,start,key-1);
    quickSort(v,key+1,end);
}

刨坑法