[数据结构与算法]快速排序的两种方法

1.左右指针法

思路:

1.选出一个pivot，一般是最左边或者最右边

2.定义一个start和end，start从左往右走，end从右往左走(需要注意的是：若选择最左边的数据作为pivot，则需要end先走；若选择最右边的数据作为pivot，则需要start先走)

3.在走的过程中，若是end遇到了小于pivot的数，就停下。然后start开始走，若是遇到了大于pivot的数时，这个时候交换start和end的值。如此循环下去直到start和end相遇，然后将相遇点的数和pivot交换即可。(选取最左边的值为pivot)

4.这个时候pivot左边的数都是小于等于pivot的数，pivot右边的数都是大于等于pivot的数。(第3步相遇的数可以和pivot交换的原因是因为end总是比start先走，所以最后相遇的数一定是小于等于pivot的)

5.将pivot的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序

c++代码如下：

void QuikSort(vector<int> &nums,int start,int end)
{
    //只有一个数或者区间不存在
    if(start>=end)
    {
        return;
    }
    int left=start;
    int right=end;
    //选左边为pivot
    int pivot=start;
    while(start<end)
    {
         //右边选小        
         while(start<end&&nums[end]>=nums[pivot])
         {
             --end; 
         } 
         //左边选大
         while(start<end&&nums[start]<=nums[pivot])
         {
             ++start;
         }
         //交换
         swap(nums[start],nums[end]);
    }
    //将相遇点的内容与pivot交换
    swap(nums[end],nums[pivot]);
    //pivot指向end
    pivot=end;
    //递归排序
    QuikSort(nums,left,pivot-1);
    QuikSort(nums,pivot+1,right);
}

2.挖坑法

思路：
挖坑法思路与hoare版本(左右指针法)思路类似
1.选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑
2、还是定义一个L和一个R，L从左向右走，R从右向左走。（若在最左边挖坑，则需要R先走；若在最右边挖坑，则需要L先走）

c++代码如下：

void QuikSort(vector<int> &nums,int start,int end)
{
    //只有一个数或者区间不存在
    if(start>=end)
    {
        return;
    }
    int left=start;
    int right=end;
    //选取左边为key
    int key=nums[start];
    while(start<end)
    {
        //右边选小
        while(start<end&&nums[end]>=key)
        {
            --end;
        }
        //小的放在左边的坑里
        nums[start]=nums[end]
        //左边选大
        while(start<end&&nums[start]<=key)
        {
            ++start;
        }
        //大的放在右边的坑里
        nums[end]=nums[start];
    }
    //把key的值放入相遇的坑位
    nums[begin]=key;
    //相遇的点左右两边继续排序
    int pivot=begin;
    QuikSort(nums,left,pivot-1);
    QuikSort(nums,pivot+1,right);
}