C++快速排序的分析与优化详解

前言

快速排序是一种高效的排序算法，它的时间复杂度为 $O(nlogn)$，但是在某些情况下，快排的时间复杂度会退化，导致排序时间变长。本文将对快速排序的原理、实现、优化等方面进行详细分析，帮助读者更好地理解和实现快速排序算法。

原理

快速排序的原理是基于分治法。首先从数列当中挑出一个元素，称为基准（pivot）。接着将数列中小于基准的元素移动到基准的左侧，大于基准的元素移动到基准的右侧，这样就将数列分成了两个部分。然后对左右两个部分递归地进行快速排序，直到整个数列有序为止。

实现

以下是使用 C++ 实现的快速排序的代码：

void quick_sort(vector<int>& nums, int left, int right) {
    if (left < right) {
        int i = left, j = right, x = nums[left];
        while (i < j) {
            while (i < j && nums[j] > x) j--;
            if (i < j) nums[i++] = nums[j];
            while (i < j && nums[i] < x) i++;
            if (i < j) nums[j--] = nums[i];
        }
        nums[i] = x;
        quick_sort(nums, left, i - 1);
        quick_sort(nums, i + 1, right);
    }
}

函数的参数包括一个整数数组和需要排序的区间范围。算法的主要流程是对基准元素进行一次划分，然后递归地对左右两侧继续执行快速排序。

优化

优化1 - 随机化选择基准

快速排序的效率取决于基准的选择，最理想的情况是每次选择的基准元素都能将数列分成两个部分，但是如果每次选择的基准都是数列的最大或最小值，那么快速排序的时间复杂度将会退化到 $O(n^2)$。因此可以提出一个优化方案，即在每次排序前随机选择一个数作为基准元素，这样可以降低最坏情况的出现概率。

以下是优化后的代码：

void quick_sort(vector<int>& nums, int left, int right) {
    if (left < right) {
        int i = left, j = right;
        // 随机选择一个数作为基准元素
        int idx = rand() % (right - left + 1) + left;
        swap(nums[idx], nums[left]);
        int x = nums[left];
        while (i < j) {
            while (i < j && nums[j] > x) j--;
            if (i < j) nums[i++] = nums[j];
            while (i < j && nums[i] < x) i++;
            if (i < j) nums[j--] = nums[i];
        }
        nums[i] = x;
        quick_sort(nums, left, i - 1);
        quick_sort(nums, i + 1, right);
    }
}

优化2 - 三数中值分割法

选择基准元素时，如果每次都选择左侧第一个元素，那么可能会出现最坏情况。为了避免这种情况，可以使用三数中值分割法，在排序区间的左、右、中三个位置分别取一个数，选取其中的中值作为基准元素。

int mid = (left + right) / 2;
if (nums[mid] > nums[right])
    swap(nums[mid], nums[right]);
if (nums[left] > nums[right])
    swap(nums[left], nums[right]);
if (nums[mid] > nums[left])
    swap(nums[mid], nums[left]);
int x = nums[left];

优化后的排序代码：

void quick_sort(vector<int>& nums, int left, int right) {
    if (left < right) {
        int i = left, j = right;
        // 三数中值分割法选择基准元素
        int mid = (left + right) / 2;
        if (nums[mid] > nums[right])
            swap(nums[mid], nums[right]);
        if (nums[left] > nums[right])
            swap(nums[left], nums[right]);
        if (nums[mid] > nums[left])
            swap(nums[mid], nums[left]);
        int x = nums[left];
        while (i < j) {
            while (i < j && nums[j] > x) j--;
            if (i < j) nums[i++] = nums[j];
            while (i < j && nums[i] < x) i++;
            if (i < j) nums[j--] = nums[i];
        }
        nums[i] = x;
        quick_sort(nums, left, i - 1);
        quick_sort(nums, i + 1, right);
    }
}

示例

示例1 - 普通快速排序

vector<int> nums = { 5, 3, 6, 4, 1, 2 };
int n = nums.size();
quick_sort(nums, 0, n - 1);
for (int i = 0; i < n; i++) {
    cout << nums[i] << " ";
}

输出结果：

1 2 3 4 5 6

示例2 - 随机化快速排序

vector<int> nums = { 5, 3, 6, 4, 1, 2 };
int n = nums.size();
srand(time(NULL));
quick_sort(nums, 0, n - 1);
for (int i = 0; i < n; i++) {
    cout << nums[i] << " ";
}

输出结果：

1 2 3 4 5 6

总结

本文主要介绍了快速排序的原理、实现和优化方案，并给出了两个示例。快速排序是一种高效的排序算法，但是在实际应用中需要注意最坏情况的出现，可以通过随机化选择基准和使用三数中值分割法来降低出现最坏情况的概率，从而提高算法的性能。