本文主要是介绍一分钟快速排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个 quick_sort 函数是一个实现快速排序（Quicksort）算法的递归函数。快速排序是一种高效的排序算法，通常用于对大规模数据集进行排序。以下是对该函数的详细解释：
函数签名
void quick_sort(int q[], int l, int r)
q[]：要排序的数组。l：数组的左边界索引。r：数组的右边界索引。
基本思想
快速排序的基本思想是通过选择一个"基准"元素，将数组划分为两个子数组，使得左子数组中的所有元素都小于基准元素，右子数组中的所有元素都大于基准元素。然后递归地对两个子数组进行排序。
函数具体步骤
-
终止条件：
if (l >= r) return;如果左边界大于或等于右边界，说明子数组的长度为0或1，此时已经是有序的，直接返回。
-
初始化指针和基准元素：
int i = l - 1, j = r + 1, x = q[l + r >> 1];i和j分别初始化为左边界的前一个位置和右边界的后一个位置。x是基准元素，通常选择中间位置的元素（这里使用(l + r) >> 1计算中间位置并作为基准）。
-
划分过程：
while (i < j) {do i ++ ; while (q[i] < x);do j -- ; while (q[j] > x);if (i < j) swap(q[i], q[j]); }i向右移动，直到找到一个不小于基准元素的元素。j向左移动，直到找到一个不大于基准元素的元素。- 如果
i小于j，则交换q[i]和q[j]。
-
递归调用：
quick_sort(q, l, j), quick_sort(q, j + 1, r);- 对左子数组
q[l..j]进行递归排序。 - 对右子数组
q[j + 1..r]进行递归排序。
- 对左子数组
代码解释
void quick_sort(int q[], int l, int r)
{if (l >= r) return;int i = l - 1, j = r + 1, x = q[l + r >> 1];while (i < j){do i ++ ; while (q[i] < x);do j -- ; while (q[j] > x);if (i < j) swap(q[i], q[j]);}quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
if (l >= r) return;：递归终止条件。如果子数组长度为0或1，直接返回。int i = l - 1, j = r + 1, x = q[l + r >> 1];：初始化左右指针和基准元素。while (i < j)：进入划分循环。do i ++ ; while (q[i] < x);：i向右移动，直到找到一个不小于x的元素。do j -- ; while (q[j] > x);：j向左移动，直到找到一个不大于x的元素。if (i < j) swap(q[i], q[j]);：如果i小于j，交换q[i]和q[j]。
quick_sort(q, l, j), quick_sort(q, j + 1, r);：递归排序左、右子数组。
示例
假设输入数组为 [3, 6, 8, 10, 1, 2, 1]，调用 quick_sort(q, 0, 6)：
- 初始基准元素为中间值
8，通过划分将数组变为[3, 6, 1, 1, 2, 8, 10]，8左边是小于8的元素，右边是大于8的元素。 - 递归对左子数组
[3, 6, 1, 1, 2]和右子数组[10]进行排序。 - 最终得到排序后的数组
[1, 1, 2, 3, 6, 8, 10]。
快速排序是一种高效的排序算法，平均时间复杂度为 O(n log n)，但在最坏情况下（如输入已经有序时）时间复杂度为 O(n^2)。通过合理选择基准元素，可以在很大程度上避免最坏情况。
测试代码
#include <iostream>
#include <algorithm>
using namespace std;void quick_sort(int q[], int l, int r)
{if (l >= r)return;int i = l - 1, j = r + 1, x = q[l + r >> 1];while (i < j){doi++;while (q[i] < x);doj--;while (q[j] > x);if (i < j)swap(q[i], q[j]);}quick_sort(q, l, j), quick_sort(q, j + 1, r);
}int main()
{int q[] = {3, 6, 2, 1, 7, 4, 5};quick_sort(q, 0, 6);for (int i = 0; i < 7; i++)cout << q[i] << ' ';return 0;
}这篇关于一分钟快速排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
