11634: 【原1634】Sort, sort and sort

题目描述

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

Description

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

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
``````

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;
}
``````