HDU-1425-sort（计数排序以及快速排序和堆排序的变种）

计数排序

Accepted

483MS

5276K

997 B

G++

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 5;
const int MIN_NUM = -5e5;
const int MAX_NUM = 5e5;
// MAX_NUM - MIN_NUM 表示输入数字的范围
int num[MAX_NUM - MIN_NUM + 10];
int main() {
    int n, m, k;
    while (~scanf("%d%d", &n, &m)) {
        while (n--) {
            scanf("%d", &k);
            // 因为存在负数而没有负下标，所以将所有输入的数减去MIN_NUM然后再存入对应下标
            num[k - MIN_NUM]++;
        }
        k = MAX_NUM - MIN_NUM;
        while (m--) {
            while (num[k] == 0) {
                k--;
            }
            num[k]--;
            if (m != 0) {
                printf("%d ", k + MIN_NUM);
            } else {
                printf("%d
", k + MIN_NUM);
            }
        }
        // k后面的都已经清空了所以，这里只要清空k前面这段就好了；
        memset(num, 0, sizeof(int) * (k + 1));
    }
    return 0;
}

计数排序适用于排序范围已知且排序数量大，排序范围小的情况。复杂度为Ο(n+k)。n表示排序数量，k表示排序范围；计数排序还有个优点在于不用记录原数，所有只要排序范围比较小是比较省空间的；

堆排序变种

Accepted

1425

499MS

2156K

1290 B

G++

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 5;
int arr[MAXN];
int n, m, k;
void minHeapFix (int id) {
    int mn = id << 1;
    if (mn > m) {
        return;
    }
    if (mn < m && arr[mn | 1] < arr[mn]) {
        mn |= 1;
    }
    if (arr[mn] < arr[id]) {
        swap(arr[mn], arr[id]);
        minHeapFix(mn);
    }
}
int main() {
    while (~scanf("%d%d", &n, &m)) {
        // 因为题目要求前m大，所以这里的堆只维护前m大的数
        for (int i = 1; i <= m; i++) {
            scanf("%d", &arr[i]);
        }
        for (int i = m >> 1; i; i--) {
            minHeapFix(i);
        }
        for (int i = m + 1; i <= n; i++) {
            scanf("%d", &k);
            // 这里维护的是小顶堆，堆顶最小，如果k比前m大中最小的数要大，用k替换堆顶，再维护小顶堆
            if (k > arr[1]) {
                arr[1] = k;
                minHeapFix(1);
            }
        }
        k = m;
        for (int i = 1; i < k; i++) {
            swap(arr[1], arr[m--]);
            minHeapFix(1);
        }
        for (int i = 1; i < k; i++) {
            printf("%d ", arr[i]);
        }
        printf("%d
", arr[k]);
    }
    return 0;
}

这题用堆排好在于他不用维护n个数只要维护前m大的数就够了，但是题目中说(0<n,m<1000000)可见m也不小了，所以比计排还要慢些，如果m比较小还是很快的。

快速排序变种

Accepted

1425

468MS

3332K

1460 B

G++

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 5;
int arr[MAXN];
int n, m;
void quickSort(int l, int r) {
    if (l >= r) {
        return;
    }
    int mid = l + r >> 1, id;
    if (arr[l] <= arr[mid] && arr[l] <= arr[r]) {
        id = arr[mid] <= arr[r] ? mid : r;
    } else {
        if (arr[mid] <= arr[r]) {
            id = arr[l] <= arr[r] ? l : r;
        } else {
            id = arr[l] <= arr[mid] ? l : mid;
        }
    }
    swap(arr[l], arr[id]);
    int ge = l + 1, lt = r;
    while (ge < lt) {
        if (arr[ge] >= arr[l]) {
            ge++;
        } else if (arr[lt] >= arr[l]){
            swap(arr[ge], arr[lt]);
            ge++;
            lt--;
        } else {
            while (arr[lt] < arr[l] && ge < lt) {
                lt--;
            }
        }
    }
    if (arr[ge] < arr[l]) {
        ge--;
    }
    swap(arr[ge], arr[l]);
    quickSort(l, ge - 1);
    // 变种就变在这个if, 因为只要前m大的数有序，所以当ge >= m时就不用排后面的数了
    if (ge < m) {
        quickSort(ge + 1, r);
    }
}
int main() {
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &arr[i]);
        }
        quickSort(1, n);
        for (int i = 1; i < m; i++) {
            printf("%d ", arr[i]);
        }
        printf("%d
", arr[m]);
    }
    return 0;
}

快速排序再变种

Accepted

1425

468MS

3332K

1264 B

G++

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 5;
int arr[MAXN];
int n, m;
void quickSort(int l, int r, int mn, int mx) {
    if (l >= r || mn >= mx) {
        return;
    }
    // 取排序范围的中值作为mid
    int mid = mn + mx >> 1;
    /* 
    下面的if很重要，原先没加导致
    5 5
    1 2 3 4 5
    这组数据死循环。
    */
    if (mid == mn) {
        mid++;
    }
    int ge = l, lt = r;
    while (ge < lt) {
        if (arr[ge] >= mid) {
            ge++;
        } else if (arr[lt] >= mid){
            swap(arr[ge], arr[lt]);
            ge++;
            lt--;
        } else {
            while (arr[lt] < mid && ge < lt) {
                lt--;
            }
        }
    }
    if (arr[ge] < mid) {
        ge--;
    }
    quickSort(l, ge, mid, mx);
    if (ge < m) {
        quickSort(ge + 1, r, mn, mid - 1);
    }
}
int main() {
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &arr[i]);
        }
        quickSort(1, n, -5e5, 5e5);
        for (int i = 1; i < m; i++) {
            printf("%d ", arr[i]);
        }
        printf("%d
", arr[m]);
    }
    return 0;
}

一般的快排都会采用三点取中法来找mid，但是这个mid并不是数组真正的中位数，所以这里采用数据范围的中值作为mid。本来以为会快一点的，但是好像和上面的快排差不多，看样子三点取中法还是很靠谱的。另外写二分一定注意死循环，快被二分死循环搞疯了。