决定快速排序性能的关键点是每次单趟排序后key对数组的分割，若每次选key都基本二分居中，而不是只选第一个值为key，那么排序所花的时间也会变得很少。我们可以用随机选key的方式来解决这些问题，如：key=rand()%(right-left+1)+left
三路划分算法解析：当面对大量跟key相同的值的时候，三路划分就有关键的优势了，它的思想有点类似于hoare的左右指针和lomuto前后指针的结合。步骤如下：（1）选取key；（2）left指向区间最左边，right指向区间最右边，cur 指向left+1的位置（3）当cur遇到比key小的值的时候该数据和left交换，left++,cur++;（4）当cur遇到比key大的值的时候跟right位置的数据交换，right--，由于不知道right原先的数据的大小，所以我们的cur不要动！(5)cur遇到跟key 相等的值的时候cur++；（6）直到cur>right时结束
最终代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include <ctype.h>
#include<stdbool.h>
#include<stddef.h>//NULL
#include<time.h>
//交换函数
void Swap(int* a, int* b)
{int c = *a;*a = *b;*b = c;
}
//快速排序-三路划分
void QuickSort(int* a, int left, int right)
{if (left >= right){return;}int begin = left;int end = right;int randi = left + rand() % (right - left + 1);//相当于随机选keySwap(&a[left], &a[randi]);int key = a[left];int cur = left + 1;while (cur <= right){if (a[cur] < key){Swap(&a[cur], &a[left]);++left;++cur;}else if (a[cur] > key){Swap(&a[cur], &a[right]);right--;}else{cur++;}}//划分成三路：[begin,left-1] [left,right][right+1,end]//其中中间一路都是与key相等的值QuickSort(a, begin, left - 1);QuickSort(a, right + 1, end);
}
int main()
{int a[] = { 9,5,2,3,4,1,0,7,8,6 };printf("排序之前: ");int n = sizeof(a) / sizeof(a[0]);for (int i = 0; i < n; i++){printf("%d ", a[i]);}QuickSort(a, 0, n - 1);printf("\n排序之后： ");for (int i = 0; i < n; i++){printf("%d ", a[i]);}return 0;
}最终代码无误。
恭喜你又学会一种排序算法！
