C/C++实现三路快速排序算法原理

算法概述

三路快速排序算法是一种优化版本的快速排序算法，能够处理含有大量重复元素的数组，避免了快速排序中大量递归处理相等元素的繁琐工作。

三路快速排序的原理是采用三个指针将数组分成小于、等于和大于三个部分，递归地向下快速排序，最终将整个数组排序。

实现步骤

1. 首先选取数组中的一个元素作为标志物，通常是数组的第一个元素。
2. 定义三个指针，分别指向数组的最左端、最右端和标志物的位置。
3. 将数组分成三个部分，小于标志物、等于标志物和大于标志物。
4. 递归处理小于和大于标志物的部分。
5. 重复步骤2到4，直到数组已经排好序。

例子说明

示例1

假设有一个数组：[5, 4, 8, 4, 3, 9, 1, 3, 2, 7]，现在需要对它进行三路快速排序。

1. 选取5作为标志物。
2. 定义三个指针，分别指向数组的最左端、最右端和标志物位置。指针分别是：left = 0，right = 9，mid = 0。
3. 从第二个元素开始扫描直到右端，将小于5的元素移到数组左侧，大于5的元素移到数组右侧，相等的元素留在中间。完成后数组变成：[4, 4, 3, 1, 3, 2, 5, 8, 9, 7]。此时指针mid指向最后一个小于5的元素位置，即3的位置。
4. 分别递归处理左半部分和右半部分，即[4, 4, 3, 1, 3, 2]和[8, 9, 7]。对左半部分重复步骤2到4，对右半部分同样重复处理，直到数组已经排好序。

示例2

再来看一个稍微复杂一点的例子：[9, 10, 51, 1, 13, 51, 43, 13, 10]。

1. 选取9作为标志物。
2. 定义三个指针，分别指向数组的最左端、最右端和标志物位置。指针分别是：left = 0，right = 8，mid = 0。
3. 从第二个元素开始扫描直到右端，将小于9的元素移到数组左侧，大于9的元素移到数组右侧，相等的元素留在中间。完成后数组变成：[1, 9, 13, 43, 51, 51, 13, 10, 10]。此时指针mid指向最后一个小于9的元素位置，即1的位置。
4. 分别递归处理左半部分和右半部分，即[1, 9, 13, 43]和[51, 51, 13, 10, 10]。对左半部分重复步骤2到4，对右半部分同样重复处理，直到数组已经排好序。

实现代码

C语言实现代码：

void quickSort(int* nums, int left, int right){
    if (left>=right) return;
    int i=left+1, lt=left, gt=right;
    int temp=nums[left];
    while (i<=gt){
        if (nums[i]<temp)
            swap(nums[i++], nums[lt++]);
        else if (nums[i]>temp)
            swap(nums[i], nums[gt--]);
        else
            i++;
    }
    quickSort(nums, left, lt-1);
    quickSort(nums, gt+1, right);
}

C++实现代码：

void quickSort(vector<int>& nums, int left, int right){
    if (left>=right) return;
    int i=left+1, lt=left, gt=right;
    int temp=nums[left];
    while (i<=gt){
        if (nums[i]<temp)
            swap(nums[i++], nums[lt++]);
        else if (nums[i]>temp)
            swap(nums[i], nums[gt--]);
        else
            i++;
    }
    quickSort(nums, left, lt-1);
    quickSort(nums, gt+1, right);
}