快速排序—基于分治

基本思想

    l                    x                     r
    |------------------------------------------|

  1. 确定分界点：q[l],q[(l+r)/2],q[r],随机

  2. 调整区间：

    1
2
3

                       ≤x            ≥x
       l                    x                      r
       |--------------------|----------------------|

  3. 递归处理左右两段

实现方法一(暴力做法)

1
2
3
4
5
6
7
8

step1. a[], b[]

step2. q[l~r]
	if q[i] <= x, q[i]->a[]

	else q[i]-> b[]

step3. a[],b[]-------->q[]        |-----a------|-----b--------|

实现方法二（优美做法）

1
2
3

l                   x                  r
|-------------------|------------------|
i                                      j

i,j两个指针分别向中间走。

i先向中间走，如果i所指向的值小于x的话，i就向中间走一步，直到i大于等于x，此时i就停下来（因为i应该放到x右边）。

j开始向中间走，如果j所指向的值大于x的话，j就向中间走一步，直到i小于x，此时j就停下来（因为j应该放到x左边）。

交换i j所指向的值，然后两个指针都向中间移动一位。

重复上述步骤，直到i和j相遇为止。这样就可以将整个区间一分为二了。

时间复杂度O(nlogn)–平均时间复杂度。

算法模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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);
}

示例运用

给定你一个长度为 n 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围 1≤n≤100000

输入样例：

1
2

5
3 1 2 4 5

输出样例：

1

1 2 3 4 5

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include<iostream>

using namespace std;

const int N = 10e6 + 10;

int n;
int q[N];

void quick_sort(int q[], int l, int r)
{
	// 为空或者一个元素则直接返回
	if(l >= r) return;

	// 做减一和加一操作，方便后面使用do ... while();
	int  i = l - 1, j = r + 1, x = q[(l + r) / 2];

	// 快速排序算法的核心思想
	while (i < j)
	{
		do i++; while (x > q[i]);
		do j--; while (x < q[j]);
		if (i < j) swap(q[i], q[j]);
	}

	//递归操作
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);
}



int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &q[i]);

	quick_sort(q, 0, n - 1);

	for (int i = 0; i < n; i++) printf("%d ", q[i]);
    
	return 0;
}