分析:
快排的主要思想基于分治,用递归来实现。
- 在数据加强后,为了不产生边界问题。取序列的中间值作为我们的分界点,记为 $x$。
- 调整区间,根据 $x$ 使得左半区间的元素都满足 $≤x$,右边区间所有元素的都满足 $≥x$。
- 递归对左右两边进行排序,当左右两边都排好序后,整个序列也就排好了顺序。因为左半区间最大值恒小于等于右边区间最小值。
如何使区间一分为二,使得 $≤x$ 的在左边,$≥x$ 的在右边是快排的关键。
一个简单(暴力)的方法是,开两个额外的空间记为 $a[ ]$,$b[ ]$,扫描原序列 $q[l,r]$,当 $q[i]≥x$ 时,将 $q[i]$ 插入到 $a$ 中;当 $q[i]<x$ 时,插入到 $b$ 中。再将 $a$、$b$ 分别插入 $q$ 中。从时间复杂度来看,是 $O(n)$。但需要两个额外的空间,因此空间消耗过多。
另一种方法则不需要开辟额外的空间。设置两个指针 $i,j$ 指向序列的左右两端,首先让 $i$ 向右边扫去,直到遇到 $≥x$ 的元素为止。接着让 $j$ 向左边扫去,直到遇到 $≤x$ 的元素为止。此时 $i,j$ 指向的元素分别都站错了位置。此时交换一下两数的位置即可。交换完毕后,$i$ 指向的元素满足 $≤x$,$j$ 指向的元素满足 $≥x$,可以接着扫描下去了~根据我们刚刚的扫描规则,当 $i,j$ 相遇时,$i$ 左边的数都满足 $≤x$,$j$ 右边的数都满足 $≥x$,也就把整个区间一分为二了。
(2023-07-17补充):当呈现出整个区间一分为二(左区间小于等于 $x$,右区间大于等于 $x$)时,进行递归快排(先递归左再递归右)。当递归子区间时出现了l==r
的情形,说明当前区间长度为 $1$,自然有序。符合最终目标序列的相应位置,即可退出该调用。
下面以序列 1 2 3 4 5 为例来说明整个快排的递归步骤,体会分治的思想,直至不能再分为止。没错,这里使用的是一个已经有序的序列,这样减轻交换元素的负担,专注于下标变化以及递归的步骤。
代码(C++) $O(nlogn)$
while(i < j)的循环里为什么不能q[i]<=x?
想象一个情况q[l,r]全为相同的元素,若是<=,i指针将会一直向右扫去...
也就(Memory Limit Exceeded)了,q[j]的情况同理
#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
void quick_sort(int a[], int l, int r)
{
// 递归边界:区间长度为 1 时,已有序
// 所有大区间殊途同归,最终都会执行一次该判断
// 会执行总元素数 n 次
if (l >= r) return;
// 确定pivot: x 为整个序列的中间值
int i = l - 1, j = r + 1, x = a[l + r >> 1];
// 将整个区间分为两部分
// 使得左半区间所有的数都小于等于 x,右半区间所有的数都大于等于 x
while (i < j)
{
// 双指针不断向中间扫描,不符合条件时停止扫描
do i ++; while (a[i] < x);
do j --; while (a[j] > x);
if (i < j) swap(a[i], a[j]); // 将不符合条件的两个数交换
}
// 递归处理左右两段
quick_sort(a, l, j), quick_sort(a, j + 1, r);
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i ++) cin >> a[i];
quick_sort(a, 0, n - 1);
for (int i = 0; i < n; i ++) cout << a[i] << ' ';
}
代码 (Java)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i ++) {
a[i] = scanner.nextInt();
}
quick_sort(a, 0, n - 1);
for (int i = 0; i < n; i ++) {
System.out.printf("%d ", a[i]);
}
}
public static void quick_sort(int[] a, int l, int r) {
if (l >= r) return ;
int i = l - 1, j = r + 1, x = a[l + r >> 1];
while (i < j) {
do i ++; while (a[i] < x);
do j --; while (a[j] > x);
if (i < j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
quick_sort(a, l, j);
quick_sort(a, j + 1, r);
}
}
第一次写题解,希望能得到大佬们的指导~