AcWing 785. 快速排序

原题链接：https://www.acwing.com/problem/content/description/787/

快速排序算法最核心的部分是如何根据分界点pivot将数据划分为大于分界点和小于分界点的两部分。假设将划分算法记作partition()，那么partition又分为三种主流的实现。

LUG版

这个版本的缺点在于，对于大部分数据存在重复的情况，这个版本的划分会极不平衡。当数据全部重复时，使用该版本partition()算法的快速排序复杂度在。

这个版本的特点可以总结为：

• 勤于拓展
• 懒于交换

int partition(int nums[], int left, int right) {
    int i = left, j = right - 1;
    int mid = (left + right) >> 1; // 偷懒直接取中点
    swap(nums[i], nums[mid]);
    
    int pivot = nums[i];
    
    while (i < j) {
        while (i < j && pivot <= nums[j]) j--;
        nums[i] = nums[j];
        while (i < j && nums[i] <= pivot) i++;
        nums[j] = nums[i];
    }
    
    nums[i] = pivot;
    
    return i;
}

DUP版

DUP版克服了LUG版的问题，但是增加了交换的次数。

DUP版的特点是：

• 勤于交换
• 懒于拓展

int partition(int nums[], int left, int right) { // 可以应对所有元素全部相等的退化情况
    int i = left, j = right - 1;
    int mid = (left + right) >> 1; // 偷懒直接取中点
    swap(nums[i], nums[mid]);
    
    int pivot = nums[i];
    
    while (i < j) {
        while (i < j && pivot < nums[j]) j--;
        if (i < j) nums[i++] = nums[j];
        while (i < j && nums[i] < pivot) i++;
        if (i < j) nums[j--] = nums[i];
    }
    
    nums[i] = pivot;
    
    return i;
}

LGU版

此版本与LUG版一样，在存在大量元素重复时，也属于最坏情况，复杂度为。

int partitionLGU(int nums[], int left, int right) {
    swap(nums[left], nums[(left + right) >> 1]); // 偷懒直接取中点
    
    int pivot = nums[left];
    int mid = left;
    for (int k = left + 1; k < right; k++) {
        if (nums[k] < pivot)
            swap(nums[++mid], nums[k]);
    }

    swap(nums[left], nums[mid]);

    return mid;
}

quick_sort()

实现了partition算法之后，quick_sort()函数的实现就不难了。

void quick_sort(int nums[], int left, int right) {
    if (right - left <= 1) return;
    int mid = partitionLGU(nums, left, right);
    quick_sort(nums, left, mid);
    quick_sort(nums, mid + 1, right);
}