Quick Sort快排 (nLogn)

主要思想为：

  1. 确定分界点
    1. 取左边界
    2. 取中间值
    3. 取右边界
    4. 或随机
  2. 划分区间 （最重要，最难的部分，有很多种实现方法）
    1. 让一个区间都 <=x
    2. 让另一个区间都 >=x
  3. 递归
    1. 递归地给左右或那俩区间排序
  4. 拼接
    1. 将排好序的左右俩边合并一起
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 = 1e6 + 10;

int n;
int q[N];

void quick_sort(int q[], int l , int r)
{
    if (l >= r)
        return;
    int x = q[l + r >> 1], i = l - 1, j = r + 1; // define x, 俩指针
    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);
}

int main()
{
    scanf("%d", &n); // scanf作为读取一般来讲更快, scanf(data, storage memory location)
    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;
}

归并排序 (nLogn)

主要思想：

  1. 以中间点为中界线， mid = (l + r) / 2
  2. 递归排序俩边
  3. 合并排列好的俩边 （重点&难点）

涉及到双指针算法

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
44
45
46
47
48
#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n;
int q[N], tmp[N];

void merge_sort(int q[], int l, int r)
{
    if (l >= r)
        return;

    int mid = l + r >> 1;

    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j])
            tmp[k++] = q[i++];
        else
            tmp[k++] = q[j++];
    }
    while (i <= mid)
        tmp[k++] = q[i++];
    while (j <= r)
        tmp[k++] = q[j++];

    for (i = l, j = 0; i <= r; i++, j++)
        q[i] = tmp[j];
}

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

    merge_sort(q, 0, n - 1);

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

    return 0;
}

拓展习题

求第K个数（快排）

题目：

给定一个长度为n的整数数列，以及一个整数k，用快速选择求出数列从小到大排序后的第k个数。

输入：第一行n和k。第二行包含n个整数（1~1e9），表示整数列

输出：输出一个整数，表示数列的第k小的数。

主要思想：

若用快排，为nlogn，用快速选择，为n

  1. 找到分界点x: q[(l + r) / 2]，让左边的<=x, 让右边的>=x
  2. 判断左边个数S_l <= k，则继续递归左边，否则递归右边，k -= S_l
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 = 1e5 + 10;
int n, k;
int q[N];

int quick_sort(int l, int r, int k)
{
    if (l >= r)
        return q[l];

    int x = q[l + r >> 1], i = l - 1, j = 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]);
    }
    int sl = j - l + 1;
    if (k <= sl)
        return quick_sort(l, j, k);
    else
        return quick_sort(j + 1, r, k - sl);
}

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

    cout << quick_sort(0, n - 1, k) << endl;

    return 0;
}

逆序对的数量

给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。逆序对的定义如下：对于数列的第i个和第j个元素，如果满足 i<j，则其为一个逆序对；否则不是。

输入：

第一行包含整数n，表示数列的长度。第二行包含n个整数，表示整个数列。

输出：

输出一个整数，表示逆序对的个数。

归并排序：

  1. 将整个区间一分为二：[l, mid], [mid + 1, r]
  2. 递归排序俩个子区间
  3. 归并，将左右俩边有序序列，合并为一个有序序列

主要思想：

  1. 共三类逆序对：
    1. 逆序对的俩个数都在左半边：merge_sort(l, mid)
    2. 一个在左边，一个在右边：这个就得在有序数列中比较然后获取分界点
    3. 都在右半边: merge_sort(mid + 1， r)
  2. 用普通的merge_sort同时，在合并的时候判断俩边数的大小来找到i 
    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
    44
    #include <iostream>

    using namespace std;

    typedef long long LL;

    const int N = 1e5 + 10;

    int a[N], tmp[N];

    LL merge_sort(int q[], int l, int r)
    {
        if (l >= r) return 0;

        int mid = l + r >> 1;

        LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);

        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r)
            if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
            else
            {
                res += mid - i + 1;
                tmp[k ++ ] = q[j ++ ];
            }
        while (i <= mid) tmp[k ++ ] = q[i ++ ];
        while (j <= r) tmp[k ++ ] = q[j ++ ];

        for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];

        return res;
    }

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

        cout << merge_sort(a, 0, n - 1) << endl;

        return 0;
    }