【数据结构】三路快速排序

1. 简介

传统快速排序用的是双路快速排序，即将大于基准值的部分放到基准值右侧，小于基准值的部分放到基准值左侧，但是这种算法面对过多的重复数据的数组，时间复杂度会增多，于是就有了三路快速排序的思想，其想法是将数组分为三个区间，假设选择数组的首元素作基准值e，则小于基准值e的数组放到基准值的左侧，等于基准值e的放到中间，大于基准值e的放到右边，即下图所示。

2. 思路

我们用i做循环遍历，遍历整个数组，我们选择数组的第一个元素做基准值e，如下图

left指针代表当前搜索区间的开始下标；
right指针代表当前搜索区间的结束下标；
lt(less than)指针代表小于e的区间的结束下标；
gt(greater than)代表大于e的区间的开始下标；
i指针指向当前待处理的元素；

记数组为nums，我们分三种情况讨论该算法，设当前nums[i]为x
（1）x和基准值e相等：
i直接向后移动1位，当前元素自动划分到等于e的区间

（2）x小于基准值e：
nums[lt+1]和nums[i]互换，并且lt和i都向前移动一位，此次互换，之前的数组都已经排好，左侧的都遍历过了，小于e的区间的元素都严格小于e，，而nums[lt+1]在交换前，是等于e区间的，所以和nums[i]互换后，nums[i]就是e，所以直接i自增1移动，因为交换后的nums[i]已经是等于e，所以向后移动，此时交换后，nums[lt+1]一定是严格小于e，所以小于e的区间的结束下标lt指针也得向后移动1个位置。

（3）x大于基准值e：
nums[gt-1]和nums[i]互换，gt向前移动1位，此时i不向前移动，因为交换过来的到底是大于基准值还是小于基准值还需要等待下次循环再判断，但是交换后nums[gt-1]已经是大于基准值e且gt是大于e的区间的开始指针，所以gt要减1来向前移动1位，这样也保证了遍历到最后，nums[i]如果还是大于e，最后nums[i]与首元素交换的时候就不合理了。

最后(i == gt的时候跳出循环），i会在等于e的区间的最后，我们要把nums[i]与nums[left]互换，使得等于e的区间里的元素全是重复的e，情况（3）中已经保证nums[i]不会大于e，情况（1）也保证nums[i]不会等于e
经过一趟三路快速排序的划分后，和传统的双路快速排序类似，我们要分别在小于e和大于e的区间上继续进行三路快速排序的划分

3. 代码实现（C语言）

思路在注释中

//生成从x到y的整数随机数
int getIntRandom(int x, int y)
{
// 传入时间戳，生成伪随机数
srand((unsigned int)time(NULL));
return (int)(x + (rand() % (y - x + 1)));
}
//三路快速排序，返回lt（小于e的区间的结束下标）和gt（大于e的区间的开始下标）
//以长度为2的数组的形式返回lt和gt
void divide3(int* nums, int left, int right)
{
//left超过right，递归结束
if (left >= right) 
{
return;
}
//随机选择一个下标做基准值的元素的下标（不做随机化处理，不能过长度很长的测试用例）
int rand_index = getIntRandom(left, right);
printf("%d
", rand_index);
//基准值
int pivot = nums[rand_index];
//交换元素用的临时遍历
int temp = 0;
//交换nums[rand_index]与nums[left]，为了方便下面的交换
//这样交换后还是等价于首元素做基准值
temp = nums[rand_index];
nums[rand_index] = nums[left];
nums[left] = temp;
//注意到，如果选择首元素做基准值，那么lt最开始就是left+1（对应首元素下标）
//因为lt(less than)指针代表小于e的区间的结束下标
int lt = left;
//gt默认从最右侧+1开始，因为假设最开始大于e的区间是无限大
//gt无需担心越界，因为我们遇到nums[i]大于e的情况，交换的是nums[i]与nums[gt-1]
int gt = right + 1;
//i从left + 1开始，因为首元素是基准值，遍历首元素后面的元素
int i = left + 1;
//循环结束的条件是i和gt指向同一个元素，此时i左侧最近的区间是等于e的区间，右侧是大于e的区间，完成了一轮三路快速排序
while(i < gt)
{
//如果当前元素和基准值相等，i自增1
if(nums[i] == pivot)
{
i++;
}
//如果当前元素小于基准值
else if(nums[i] < pivot)
{
//nums[lt+1]和nums[i]互换
temp = nums[i];
nums[i] = nums[lt+1];
nums[lt+1] = temp;
//lt和i都自增1
lt++;
i++;
}
//如果当前元素大于基准值
else
{
//nums[gt-1]和nums[i]互换
temp = nums[i];
nums[i] = nums[gt-1];
nums[gt-1] = temp;
//i无需自增1，留着判断换过来的数
//gt自减1，因为多了一个大于e的数，要向左扩大大于e的数组区间
gt--;
}
}
//交换nums[lt]与nums[left]
temp = nums[lt];
nums[lt] = nums[left];
nums[left] = temp;
//递归小于e和大于e的区间
divide3(nums, left, lt-1);
divide3(nums, gt, right);
}
int* sortArray(int* nums, int numsSize, int* returnSize) {
divide3(nums, 0, numsSize - 1);
*returnSize = numsSize;
return nums;
}

提交结果：