P1177. 模板题_排序

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 805 阅读时长 ≈ 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
#include <bits/stdc++.h>

using namespace std;

const int LEN = 1e5 + 10;

void quick_sort(int arr[], int len)
{
    if (len <= 1)
        return;
    int i = 0, j = 0, k = len;
    int pivot = arr[rand() % len];
    while (i < k)
    {
        if (arr[i] < pivot)
            swap(arr[i++], arr[j++]);
        else if (arr[i] > pivot)
            swap(arr[i], arr[--k]);
        else
            ++i;
    }
    quick_sort(arr, j);
    quick_sort(arr + k, len - k);
}

int main()
{
    int n, arr[LEN];
    memset(arr, 0, sizeof(arr));
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    quick_sort(arr, n);
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    return 0;
}

思路

部分模板来源于OIWiki

普通快排

普通快排的迭代版模板如下，来源于上述的OIWiki

其中对区间的分治操作需要熟练掌握，未来会经常用到

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
struct Range
{
    int start, end;
    Range(int s = 0, int e = 0) { start = s, end = e; }
};

template <typename T>
void quick_sort(T arr[], const int len)
{
    if (len <= 0)
        return;
    Range r[len];
    int p = 0;
    r[p++] = Range(0, len - 1);
    while (p)
    {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        T mid = arr[range.end];
        int left = range.start, right = range.end - 1;
        while (left < right)
        {
            while (arr[left] < mid && left < right)
                left++;
            while (arr[right] >= mid && left < right)
                right--;
            std::swap(arr[left], arr[right]);
        }
        if (arr[left] >= arr[range.end])
            std::swap(arr[left], arr[range.end]);
        else
            left++;
        r[p++] = Range(range.start, left - 1);
        r[p++] = Range(left + 1, range.end);
    }
}

当然也可以将其改造为递归，就变成广为流传的样子

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
#include <bits/stdc++.h>

using namespace std;

const int LEN = 1e5 + 10;

int N, arr[LEN];

void quick_sort(int bg, int ed)
{
    if (bg >= ed)
        return;
    int l = bg, r = ed - 1, pivot = arr[ed];
    while (l < r)
    {
        while (arr[l] < pivot && l < r)
            ++l;
        while (arr[r] >= pivot && l < r)
            --r;
        swap(arr[l], arr[r]);
    }
    if (arr[l] >= arr[ed])
        swap(arr[l], arr[ed]);
    else
        ++l;
    quick_sort(bg, l - 1);
    quick_sort(l + 1, ed);
}

int main()
{
    cin >> N;
    for (int i = 0; i < N; ++i)
        cin >> arr[i];
    quick_sort(0, N - 1);
    for (int i = 0; i < N; ++i)
        cout << arr[i] << " ";
    return 0;
}

三路快速排序

普通快排效率并不高，上面的代码本题就会超时，就需要用到三路快排；模板同样来自OIWiki

顺带提一嘴，rand函数的用法可以简单记为a + rand() % b；即从a开始（包括a）共b个连续整数的生成范围

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
// 模板的 T 参数表示元素的类型，此类型需要定义小于（<）运算
template <typename T>
// arr 为需要被排序的数组，len 为数组长度
void quick_sort(T arr[], const int len)
{
    if (len <= 1)
        return;
    // 随机选择基准（pivot）
    const T pivot = arr[rand() % len];
    // i：当前操作的元素下标
    // arr[0, j)：存储小于 pivot 的元素
    // arr[k, len)：存储大于 pivot 的元素
    int i = 0, j = 0, k = len;
    // 完成一趟三路快排，将序列分为：
    // 小于 pivot 的元素 | 等于 pivot 的元素 | 大于 pivot 的元素
    while (i < k)
    {
        if (arr[i] < pivot)
            swap(arr[i++], arr[j++]);
        else if (pivot < arr[i])
            swap(arr[i], arr[--k]);
        else
            i++;
    }
    // 递归完成对于两个子序列的快速排序
    quick_sort(arr, j);
    quick_sort(arr + k, len - k);
}

归并排序

直接上图~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 50;
int n, a[maxn], t[maxn];

void merge(int l, int r) {
  if (l == r) return;
  int i = l, j = l, mid = (l + r) / 2, k = mid + 1;
  merge(l, mid), merge(mid + 1, r);
  while (j <= mid && k <= r) t[i++] = a[j] <= a[k] ? a[j++] : a[k++];
  while (j <= mid) t[i++] = a[j++];
  while (k <= r) t[i++] = a[k++];
  for (i = l; i <= r; ++i) a[i] = t[i];
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  merge(1, n);
  for (int i = 1; i <= n; ++i) cout << a[i] << " ";
  return 0;
}