交换排序——快速排序

        交换排序的基本思路：把序列中的两个元素进行比较，根据需求对两个元素进行交换。特点是较大的元素向序列的尾部移动，较小的元素向序列的前部移动。

        hoare法

        在序列中任取一个元素作为基准值，一趟排序完成之后，以基准值为分割点，左边的元素都小于基准值，右边的元素都大于基准值。

        一般选最左边的值作为基准值。定义左右两个指针，left和right。right找小于基准元素的值，left找大于基准值的元素。找到之后，把left和right的值交换，就是把小的元素往前换，大的元素往后换。注意，基准值在左边，一定让右边先走。如果基准值在右边，一定让左边先走。

           

         最后把keyi和相遇点的下标交换一下。以该keyi为界，左边的值都小于基准值，右边的值都大于基准值。之后对函数递归调用就好了。

        现在有两个问题：

        1、为什么基准值在左边，一定让右边先走？

      

        如果左边先走，left和right相遇时，不能保证相遇点的值比基准值小。

        2、为什么基准值在左边，一定让右边先走，最后相遇点的值一定比基准值小？

        相遇有两种情况。（1）在一次完成交换后，right找小，一直找到与left相遇。而这时left所指向的值是和原来的right交换来的，该值一定比基准值小。（2）right找到小，left找大一直找到与right相遇，该值也比基准值要小。

//交换两个值
void Swap(int* p, int* q)
{int tmp = *p;*p = *q;*q = tmp;
}

//hoare法
int PartSort1(int* a, int left, int right)
{int keyi = left;//一般选第一个为基准值while (left < right){//这里也要控制left<right，有可能序列已经有序，right会一直减到小于0，造成越界访问//right找小while (left < right && a[right] >= a[keyi]){right--;}//left找大while (left < right && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);//交换left和right最终指向的值}Swap(&a[keyi], &a[left]);//交换基准值和相遇点的值Swap(&keyi, &left);return keyi;
}void QuickSort(int* a, int left, int right)
{if (left >= right)//区间只有一个值或者区间不存在，直接返回{return;}int begin = left;//记录区间第一个元素的下标int end = right;//记录区间最后一个元素的下标int keyi = PartSort1(a, left, right);//一趟排序//序列被划分为三个部分//[begin,keyi-1] keyi [keyi+1,end]QuickSort(a, begin, keyi - 1);//对左区间排序QuickSort(a, keyi + 1, end);//对右区间排序
}