Skip to content

11634: 【原1634】Sort, sort and sort

题目

题目描述

author: TA 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1634

Description

给定1~n的任意排列,用堆排,快排或归并进行从小到大排序,输出比较次数。

要求如下:

  • 堆排序:小根堆,建堆方式:
    1. 增加堆的长度,在末尾处插入元素。
    2. 比较当前元素和它的父结点值,如果小于父结点值,则交换,否则返回。
    3. 重复步骤2.
  • 归并排序:区间等分(如果是奇数,左边比右边小1)
  • 快速排序:以第一个元素为比较元

Input Format

第一行两个整数\(N,k\) ,分别代表数列长度和排序种类(1:堆排;2:归并;3:快排)。

接下来一行 \(N\) 个数代表一开始的序列\( {X_1,X_2,…,X_N}\)。

Output Format

输出一行代表比较次数。

Sample Input

5 1
1 3 2 4 5

Sample Output

9

Sample Input

5 2
1 3 2 4 5

Sample Output

6

Sample Input

5 3
1 3 2 4 5

Sample Output

8

Limits

对于\(30\%\)的数据,\(k = 1\)

对于\(30\%\)的数据,\(k = 2\)

对于\(40\%\)的数据,\(k = 3\)

BugenZhao's solution

//
// Created by BugenZhao on 2019/5/16.
//

//
// Created by BugenZhao on 2019/5/12.
//
//
// Created by BugenZhao on 2019/5/12.
//
//
// Created by BugenZhao on 2019/5/12.
//

#ifndef SBL_BQSORT_H
#define SBL_BQSORT_H

int count = 0;

template<typename Item>
class BQSort {
public:
    static int count;

private:
    static bool less(Item v, Item w) {
        ++count;
        return v < w;
    }

    static void exch(Item *a, int i, int j) {
        Item t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

public:
    static inline void sort(Item *a, int n) {
        sort(a, 0, n - 1);
    }

    static inline void sort(Item *a, int lo, int hi) {
        if (hi <= lo) return;
        int mid = partition(a, lo, hi);
        sort(a, lo, mid - 1);
        sort(a, mid + 1, hi);
    }

    static int partition(Item *a, int lo, int hi) {
        Item v = a[lo];
        while (true) {
            while (lo < hi && less(v, a[hi])) --hi;
            if (lo < hi) a[lo] = a[hi], ++lo;
            while (lo < hi && less(a[lo], v)) ++lo;
            if (lo < hi) a[hi] = a[lo], --hi;
            if (lo >= hi) break;
        }
        a[lo] = v;
        return lo;
    }
};

template<typename Item>
int BQSort<Item>::count = 0;

#endif //SBL_BQSORT_H


//
// Created by BugenZhao on 2019/5/16.
//

#ifndef SBL_BMINHEAPSORT_H
#define SBL_BMINHEAPSORT_H

template<typename Item>
class BMinHeapSort {
public:
    static int count;

private:
    static bool less(Item v, Item w) {
        ++count;
        return v < w;
    }

    static void exch(Item *a, int i, int j) {
        Item t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    static void sink(Item *a, int k, int N) {
        while (2 * k + 1 <= N) {
            int j = 2 * k + 1;
            if (j < N && less(a[j + 1], a[j])) ++j;
            if (less(a[k], a[j])) break;
            exch(a, k, j);
            k = j;
        }
    }

    static void swim(Item *a, int k) {
        int tmp;
        while (k && less(a[k], a[tmp = (k - 1) / 2])) {
            exch(a, k, tmp);
            k = tmp;
        }
    }

public:
    static void sort(Item *a, int n) {
        auto aux = new Item[n];
        for (int i = 0; i < n; ++i) {
            aux[i] = a[i];
        }
        int N = n - 1;
        for (int k = 1; k < n; ++k) {
            swim(aux, k);
        }
        for (int i = 0; i < n; ++i) {
            a[i] = aux[0];
            exch(aux, 0, N--);
            sink(aux, 0, N);
        }
        delete[] aux;
    }

    static void sort(Item *a, int lo, int hi) {
        Item *newa = a + lo;
        sort(newa, hi - lo + 1);
    }
};

template<typename Item>
int BMinHeapSort<Item>::count = 0;

#endif //SBL_BMINHEAPSORT_H
//
// Created by BugenZhao on 2019/5/16.
//

#ifndef SBL_BMERGESORT_H
#define SBL_BMERGESORT_H

template<typename Item>
class BMergeSort {
public:
    static int count;

private:
    static bool less(Item v, Item w) {
        ++count;
        return v < w;
    }

    static void doSort(Item *a, int lo, int hi, Item *aux) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo - 1) / 2;
        doSort(a, lo, mid, aux);
        doSort(a, mid + 1, hi, aux);
        merge(a, lo, mid, hi, aux);
    }

    static void merge(Item *a, int lo, int mid, int hi, Item *aux) {
        for (int i = lo; i <= hi; i++) {
            aux[i] = a[i];
        }
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (less(aux[i], aux[j])) a[k] = aux[i++];
            else a[k] = aux[j++];
        }
    }

public:
    static void sort(Item *a, int n) {
        sort(a, 0, n - 1);
    }

    static void sort(Item *a, int lo, int hi) {
        Item *aux = new Item[hi - lo + 1];
        doSort(a, lo, hi, aux);
        delete[] aux;
    }
};

template<typename Item>
int BMergeSort<Item>::count = 0;

#endif //SBL_BMERGESORT_H

#include <cstdio>
#include <string>

using std::ios, std::string;
using ll = long long;

int main() {
    int n, sel;
    scanf("%d%d", &n, &sel);
    auto a = new int[n];
    for (int i = 0; i < n; ++i) {
        scanf("%d", a + i);
    }
    int count = 0;
    switch (sel) {
        case 1:
            BMinHeapSort<int>::sort(a, n);
            count = BMinHeapSort<int>::count;
            break;
        case 2:
            BMergeSort<int>::sort(a, n);
            count = BMergeSort<int>::count;
            break;
        case 3:
            BQSort<int>::sort(a, n);
            count = BQSort<int>::count;
            break;
    }
    printf("%d\n", count);
    delete[] a;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

long long cnt = 0;

int val_data[1000009] = { 0 };

void quick_sort(int* left, int* right) {
    if (left >= right - 1)
        return;
    auto p = left, q = right - 1;
    auto key = *p;
    bool flag = true;
    while (p < q) {
        if (flag) {
            if (*q < key) {
                *p = *q;
                flag = false;
                ++p;
            }
            else {
                --q;
            }
            ++cnt;
        }
        else {
            if (*p > key) {
                *q = *p;
                flag = true;
                --p;
            }
            else {
                ++q;
            }
            ++cnt;
        }
    }
    *p = key;
    quick_sort(left, p + 1);
    quick_sort(p + 1, right);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; ++i)
        cin >> val_data[i];

    if (k == 3) {
        quick_sort(val_data, val_data + n);
        for (int i = 0; i < n; ++i) {
            cout << val_data[i] << " ";
        }
        cout << endl;
        cout << cnt;
    }

    return 0;
}

q4x3's solution

/**
 * 堆排+归并+快排计数
 * 快排计数方法很神奇
 **/
#include <iostream>

using namespace std;

long long int ans;
int dt[100233], pre[100233], nxt[100233];
int N, k;

void merge(int lo, int mi, int hi, int* a) {
    int* A = a + lo;
    int lb = mi - lo;
    int* B = new int[lb];
    int* BB = B;
    for(int i = 0;i < lb;++ i)
        B[i] = A[i];
    int lc = hi - mi;
    int* C = a + mi;
    int cnt = 0;
    while(1) {
        if ((lb == 0) && (lc == 0)) break;
        if (lb == 0) {
            A[cnt] = C[0];
            ++ cnt; ++ C; -- lc;
        }
        else if (lc == 0) {
            A[cnt] = B[0];
            ++ cnt; ++ B; --lb;
        }
        else {
            ++ ans;
            if(B[0] < C[0]) {
                A[cnt] = B[0];
                ++ cnt; ++ B; -- lb;
            }
            else {
                A[cnt] = C[0];
                ++ cnt; ++ C; -- lc;
            }
        }
    }
    delete []BB;
}

void mergeSort(int lo, int hi, int* a) {
    if(hi - lo < 2) return;
    int mi = (lo + hi) >> 1;
    mergeSort(lo, mi, a);
    mergeSort(mi, hi, a);
    merge(lo, mi, hi, a);
}

void up(int node) {
    if(node == 1) return;
    ++ ans;
    if(dt[node] < dt[node >> 1]) {
        swap(dt[node], dt[node >> 1]);
        up(node >> 1);
    }
}

void down(int node, int size) {
    if(node == size || (node << 1) > size) return;
    if((node << 1 | 1) > size) {
        ++ ans;
        if(dt[node << 1] < dt[node]) swap(dt[node << 1], dt[node]);
    } else {
        ans += 2;
        if(dt[node << 1] <= dt[node << 1 | 1]) {
            if(dt[node] > dt[node << 1]) {
                swap(dt[node], dt[node << 1]);
                down(node << 1, size);
            }
        } else {
            if(dt[node] > dt[node << 1 | 1]) {
                swap(dt[node], dt[node << 1 | 1]);
                down(node << 1 | 1, size);
            }
        }
    }
}

void build() {
    for(int i = 1;i <= N;++ i)
        up(i);
}

void quick() {
    for (int i = 1; i <= N; i++)
    {
        pre[i] = i - 1;
        nxt[i] = i + 1;
    }
    nxt[0] = 1;
    pre[N + 1] = N;
    for (int i = N; i >= 1; i--)
    {
        int k = dt[i];
        ans += (long long int)(nxt[k] - pre[k] - 2);
        nxt[pre[k]] = nxt[k];
        pre[nxt[k]] = pre[k];
    }
}

int main() {
    scanf("%d%d", &N, &k);
    for(int i = 1;i <= N;++ i)
        scanf("%d", &dt[i]);
    if(k == 1) {
        build();
        for(int i = N;i > 1;-- i) {
            swap(dt[i], dt[1]);
            down(1, i - 1);
        }
        printf("%lld\n", ans);
    }
    if(k == 2) {
        mergeSort(1, N + 1, dt);
        printf("%lld\n", ans);
    }
    if(k == 3) {
        quick();
        printf("%lld\n", ans);
    }
}

victrid's solution

#include <iostream>
using namespace std;
int ll[1000050];
int* MergeSort(int* list, int listSize, long long& cmp) {
    if (listSize == 1)
        return list;
    if (listSize == 2) {
        cmp++;
        [&](int& a, int& b) { if (a>b){a^=b;b^=a;a^=b;} }(list[0], list[1]);
        return list;
    }
    int* tmplist = new int[listSize];
    int* llst    = MergeSort(list, listSize / 2, cmp);
    int* rlst    = MergeSort(list + listSize / 2, listSize - listSize / 2, cmp);
    int lct = 0, rct = 0;
    while (lct + rct != listSize) {
        if (rct < listSize - listSize / 2 && lct < listSize / 2) {
            cmp++;
        }
        if ((llst[lct] <= rlst[rct] && lct < listSize / 2) || rct >= listSize - listSize / 2) {
            tmplist[lct + rct] = llst[lct];
            lct++;
        } else {
            tmplist[lct + rct] = rlst[rct];
            rct++;
        }
    }
    for (int i = 0; i < listSize; i++)
        list[i] = tmplist[i];
    delete[] tmplist;
    return list;
}
void siftdown(int* list, int listSize, int it, long long& cmp) {
    auto swap = [&](int& a, int& b) {if(a==b)return;a^=b;b^=a;a^=b; };
    if (((it + 1) << 1) > listSize)
        return;
    if (((it + 1) << 1 | 1) > listSize) {
        //1
        cmp++;
        if ([&](int& a, int& b) { if (a>b){swap(a,b);return false;}return true; }(list[it], list[((it + 1) << 1) - 1]))
            return siftdown(list, listSize, ((it + 1) << 1) - 1, cmp);
        //!
        return;
    }
    cmp += 2;
    if (list[((it + 1) << 1) - 1] < list[((it + 1) << 1 | 1) - 1]) {
        if ([&](int& a, int& b) { if (a>b){swap(a,b);return true;}return false; }(list[it], list[((it + 1) << 1) - 1]))
            return siftdown(list, listSize, ((it + 1) << 1) - 1, cmp);
    } else {
        if ([&](int& a, int& b) { if (a>b){swap(a,b);return true;}return false; }(list[it], list[((it + 1) << 1 | 1) - 1]))
            return siftdown(list, listSize, ((it + 1) << 1 | 1) - 1, cmp);
    }
    //!
    return;
}
int* HeapSort(int* list, int listSize, long long& cmp) {
    //from big to small
    auto swap = [&](int& a, int& b) {if(a==b)return;a^=b;b^=a;a^=b; };
    for (int i = 2; i <= listSize; i++) {
        int pos = i;
        while (pos != 1) {
            cmp++;
            if ([&](int& a, int& b) { if (a<b){swap(a,b);return false;}return true; }(list[pos - 1], list[(pos >> 1) - 1]))
                break;
            pos = pos >> 1;
        }
    }
    for (int i = listSize; i > 1; i--) {
        swap(list[i - 1], list[0]);
        siftdown(list, i - 1, 0, cmp);
    }
    return list;
}
struct node {
    int val;
    node* left;
    node* right;
};
node tr[1000050];
void QuickSortCount(int* list, int listSize, long long& cmp) {
    for (int i = 1; i <= listSize + 1; i++) {
        tr[i].val         = i;
        tr[i].left        = tr + i - 1;
        tr[i].left->right = tr + i;
    }
    for (int i = listSize - 1; i >= 0; i--) {
        cmp += tr[list[i]].right->val - tr[list[i]].left->val - 2;
        tr[list[i]].right->left = tr[list[i]].left;
        tr[list[i]].left->right = tr[list[i]].right;
        tr[list[i]].left        = nullptr;
        tr[list[i]].right       = nullptr;
    }
}

int main() {
    int N, k;
    long long cmp = 0;
    scanf("%d %d", &N, &k);
    for (int i = 0; i < N; ++i)
        scanf("%d", &ll[i]);
    switch (k) {
    case 1:
        HeapSort(ll, N, cmp);
        break;
    case 2:
        MergeSort(ll, N, cmp);
        break;
    case 3:
        QuickSortCount(ll, N, cmp);
        break;
    }
    printf("%lld", cmp);
    return 0;
}