题目描述

给定一个长度为 $n$ 的数组 $a$ 以及两个整数 $l$ 和 $r$，请你编写一个函数，$void\ sort(int\ a[],\ int\ l,\ int\ r)$，将 $a[l]$ ~ $a[r]$ 从小到大排序。

输出排好序的数组 $a$。

注意，这里的数组下标从 $0$ 开始

样例输入

5 2 4
4 5 1 3 2

样例输出

4 5 1 2 3

哎，难度是困难？那当然是用高端解法来操作啦

算法 $1$

堆排序 $O(nlogn)$

构建大根堆，每次将最大的元素放到最后

$C++$ 代码

#include <stdio.h>

int a[1005];

void swap(int i, int j)  // 技巧：手写交换，传入数组下标
{
    if (i ^ j)           // 特判 i = j 的情况，i ^ j 等价于 i != j
    {
        a[i] ^= a[j];    // 交换 a[i], a[j]
        a[j] ^= a[i];
        a[i] ^= a[j];
    }
}

void down(int l, int r, int p) // 将更小的元素
{
    int t = p;
    if ((p << 1) <= r - l && a[t] < a[(p << 1) - l])
        t = (p << 1) - l;
    if ((p << 1) + 1 - l <= r && a[t] < a[(p << 1) + 1 - l])
        t = (p << 1) + 1 - l;
    if (t != p)
    {
        swap(t, p);
        down(l, r, t);
    }
}

void heap_sort(int l, int r)
{
    for (int i = r - l >> 1; i; i -- ) // O(n)建堆
        down(l, r, i);
    while (r ^ l)        // 排序，同样用 r ^ l 代替 r != l
    {
        swap(1, r -- );  // 每次将最大的元素交换至最后，并在堆中删除
        down(l, r, 1);   // 将交换过来的元素向下交换，使剩余元素重构堆
    }
}

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

    heap_sort(l, r + 1);

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

    return 0;
}

算法 $2$

归并排序 $O(nlogn)$

每次将数组划分成两个部分，分别处理

$C++$ 代码

#include <stdio.h>

const int N = 1005;

int a[N];
int t[N];

void merge_sort(int l,int r)
{
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        if (a[i] < a[j]) t[k ++ ] = a[i ++ ];
        else    t[k ++ ] = a[j ++ ];
    while (i <= mid) t[k ++ ] = a[i ++ ];
    while (j <= r) t[k ++ ] = a[j ++ ];
    for (int i = l, j = 0; i <= r; i ++, j ++ )
        a[i] = t[j];
}

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

    merge_sort(l, r);

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

    return 0;
}
// 懒得注释了

算法 $3$

快速排序 $O(nlogn)$

每次将数组划分成两个部分，分别处理

$C++$ 代码

#include <stdio.h>

const int N = 1005;

int a[N];

void swap(int i, int j) // 由于当 i < j 的时候才会 swap，所以不用特判
{
    a[i] ^= a[j];
    a[j] ^= a[i];
    a[i] ^= a[j];
}

void quick_sort(int l,int r)
{
    if (l >= r) return;
    int x = a[l + r >> 1];
    int i = l - 1, j = r + 1;
    while (i < j)
    {
        while (a[ ++ i] < x);
        while (a[ -- j] > x);
        if (i < j) swap(i, j);
    }
    quick_sort(l, j);
    quick_sort(j + 1, r);
}

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

    quick_sort(l, r);

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

    return 0;
}

这就完了？

算法 $4$

三向切分快排 $O(nlogn)$

用 $i$，$j$，$k$ 三个下标将数组切分成四部分。
$a[l, i - 1]$ 表示小于 $x$ 的部分，$a[i, k - 1]$表示等于 $x$ 的部分，$a[j + 1]$ 表示大于 $x$ 的部分，而 $a[k, j]$ 表示未判定的元素（即不知道比 $x$ 大，还是比中轴元素小）。
同时要注意 $a[i]$ 始终位于等于 $x$ 部分的第一个元素，$a[i]$ 的左边是小于 $x$ 的部分。

$C++$ 代码

#include <stdio.h>

const int N = 1005;

int a[N];

void swap(int i, int j)
{
    if (i ^ j)
    {
        a[i] ^= a[j];
        a[j] ^= a[i];
        a[i] ^= a[j];
    }
}

void quick_sort_3way(int l, int r)
{
    if(l >= r) return;
    int x = a[l];
    int i = l, j = r, k = l + 1;
    while(k <= j)
        if(a[k] < x)swap(i ++ , k ++ );
        else if(a[k] == x) k ++ ;
        else
        {
            while(a[j] > x)
                if( -- j < k)break;
            if (j < k) break;
            if(a[j] == x)
                swap(k ++ , j -- );
            else
            {
                swap(i ++ , j);
                swap(j -- , k ++ );
            }
        }
    quick_sort_3way(l, i - 1);
    quick_sort_3way(j + 1, r);
}

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

    quick_sort_3way(l, r);

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

    return 0;
}

算法 $5$

双轴快排 $O(nlogn)$

同样，使用 $i$，$j$，$k$ 三个变量将数组分成四部分
同时，使用两个轴，通常选取最左边的元素作为 $x1$ 和最右边的元素作 $x2$。
首先要比较这两个轴的大小，如果 $x1 > x2$，则交换最左边的元素和最右边的元素，以保证 $x1 <= x2$。

神奇的是y总快排那题的数据把这两种优化过但不取中的快排都卡掉了。。。

$C++$ 代码

#include <stdio.h>

const int N = 1005;

int a[N];

void swap(int i, int j)
{
    if (i ^ j)
    {
        a[i] ^= a[j];
        a[j] ^= a[i];
        a[i] ^= a[j];
    }
}

void quick_sort_2(int l, int r)
{
    if(l >= r) return;
    if(a[l] > a[r]) swap(l, r);
    int x1 = a[l], x2 = a[r];
    int i = l, k = l + 1, j = r;
    while(k < j)
        if(a[k] < x1) swap( ++ i, k ++ );
        else if(a[k] >= x1 && a[k] <= x2) k ++ ;
        else
        {
            while(a[ -- j] > x2)
                if(j <= k) break;
            if (j <= k) break;
            if(a[j] >= x1 && a[j] <= x2)
                swap(k ++ , j);
            else
            {
                swap(j, k);
                swap( ++ i, k ++ );
            }
        }
    swap(l, i),swap(r, j);
    quick_sort_2(l, i - 1);
    quick_sort_2(i + 1, j - 1);
    quick_sort_2(j + 1, r);
}

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

    quick_sort_2(l, r);

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

    return 0;
}