快速排序三路划分

C

以下是C语言实现的快速排序的三路划分版本的代码：

#include <stdio.h>

// 交换两个元素的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 快速排序的三路划分
void quickSort(int* nums, int left, int right) {
    if (left >= right) return;

    int pivot = nums[left]; // 选取第一个元素作为基准值
    int lt = left;          // lt 表示小于基准值的区间右边界
    int gt = right + 1;     // gt 表示大于基准值的区间左边界
    int i = left + 1;       // i 表示当前元素的位置

    while (i < gt) {
        if (nums[i] < pivot) {  // 如果当前元素小于基准值
            swap(&nums[i], &nums[lt + 1]);  // 将当前元素与小于区间的下一个位置交换
            lt++;  // 更新小于区间的右边界
            i++;   // 继续考察下一个元素
        } else if (nums[i] > pivot) {  // 如果当前元素大于基准值
            swap(&nums[i], &nums[gt - 1]);  // 将当前元素与大于区间的前一个位置交换
            gt--;  // 更新大于区间的左边界
        } else {  // 如果当前元素等于基准值
            i++;  // 继续考察下一个元素
        }
    }

    swap(&nums[left], &nums[lt]);  // 将基准值交换到合适的位置

    // 递归处理小于基准值和大于基准值的两部分
    quickSort(nums, left, lt - 1);
    quickSort(nums, gt, right);
}

// 快速排序的接口函数
void sort(int* nums, int numsSize) {
    quickSort(nums, 0, numsSize - 1);
}

int main() {
    int nums[] = {3, 1, 5, 2, 4};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    sort(nums, numsSize);
    for (int i = 0; i < numsSize; ++i) {
        printf("%d ", nums[i]);
    }
    printf("\n");
    return 0;
}

这段代码是C语言实现的快速排序的三路划分版本，也使用了双指针的方法来对数组进行划分。

C++

下面是C++中快速排序的三路划分的代码：

#include <vector>
using namespace std;

// 交换两个元素的值
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// 快速排序的三路划分
void quickSort(vector<int>& nums, int left, int right) {
    if (left >= right) return;

    int pivot = nums[left]; // 选取第一个元素作为基准值
    int lt = left;          // lt 表示小于基准值的区间右边界
    int gt = right + 1;     // gt 表示大于基准值的区间左边界
    int i = left + 1;       // i 表示当前元素的位置

    while (i < gt) {
        if (nums[i] < pivot) {  // 如果当前元素小于基准值
            swap(nums[i], nums[lt + 1]);  // 将当前元素与小于区间的下一个位置交换
            lt++;  // 更新小于区间的右边界
            i++;   // 继续考察下一个元素
        } else if (nums[i] > pivot) {  // 如果当前元素大于基准值
            swap(nums[i], nums[gt - 1]);  // 将当前元素与大于区间的前一个位置交换
            gt--;  // 更新大于区间的左边界
        } else {  // 如果当前元素等于基准值
            i++;  // 继续考察下一个元素
        }
    }

    swap(nums[left], nums[lt]);  // 将基准值交换到合适的位置

    // 递归处理小于基准值和大于基准值的两部分
    quickSort(nums, left, lt - 1);
    quickSort(nums, gt, right);
}

// 快速排序的接口函数
void quickSort(vector<int>& nums) {
    quickSort(nums, 0, nums.size() - 1);
}

int main() {
    vector<int> nums = {3, 1, 5, 2, 4};
    quickSort(nums);
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

这段代码实现了快速排序的三路划分版本，使用了双指针的方法来对数组进行划分，使得快速排序在处理存在大量重复元素的情况下效率更高。