O(nlogn)排序算法

排序算法

介绍常见时间复杂度为\(O(nlogn)\)的排序算法

1. 快速排序

分治思想

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
void quick_sort(int l, int r){
    if(l >= r) return;
    int x = a[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j){
        while(a[ ++ i] < x);
        while(a[ -- j] > x);
        if(i < j) swap(a[i], a[j]);
    }
    quick_sort(l, j), quick_sort(j + 1, r);
}
int main(){
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    quick_sort(0, n - 1);
    for(int i = 0; i < n; i ++ ) printf("%d ", a[i]);
    return 0;
}

题目一

Luogu P1923 【深基9.例4】求第 k 小的数

#include<bits/stdc++.h>
using namespace std;
const int N = 5e6 + 10;
int a[N], n, k; // k代表索引
int quick_sort(int l, int r){
    if(l >= r) return a[l];
    int x = a[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j){
        while(a[ ++ i] < x);
        while(a[ -- j] > x);
        if(i < j) swap(a[i], a[j]);
    }
    if(k <= j) return quick_sort(l, j);
    return quick_sort(j + 1, r);
}
int main(){
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    printf("%d", quick_sort(0, n - 1));
    return 0;
}

题目二

Luogu P1138 第 k 小整数

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int a[N], n, k, t, len; // k代表索引, t暂存数据, len表示a数组的长度
bool c[N]; // bool数组
int quick_sort(int l, int r){
    if(l >= r) return a[l];
    int x = a[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j){
        while(a[ ++ i] < x);
        while(a[ -- j] > x);
        if(i < j) swap(a[i], a[j]);
    }
    if(k <= j) return quick_sort(l, j);
    return quick_sort(j + 1, r);
}
int main(){
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i ++ ){
        scanf("%d", &t);
        if(!c[t]){
            a[len ++ ] = t;
            c[t] = true;
        }
    }
    k -- ; // k代表索引
    k >= len ? puts("NO RESULT") : printf("%d", quick_sort(0, len - 1));
    return 0;
}

2. 归并排序

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[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 = l;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) b[k ++ ] = a[i ++ ]; // 保证稳定性
        else b[k ++ ] = a[j ++ ];
    }
    while(i <= mid) b[k ++ ] = a[i ++ ];
    while(j <= r) b[k ++ ] = a[j ++ ];
    for(i = l; i <= r; i ++ ) a[i] = b[i];
}
int main(){
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    merge_sort(0, n - 1);
    for(int i = 0; i < n; i ++ ) printf("%d ", a[i]);
    return 0;
}

题目一

Luogu P1908 逆序对

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
int a[N], b[N];
LL res;
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 = l;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) b[k ++ ] = a[i ++ ];
        else b[k ++ ] = a[j ++ ], res += mid - i + 1;  
    }
    while(i <= mid) b[k ++ ] = a[i ++ ];
    while(j <= r) b[k ++ ] = a[j ++ ];
    for(i = l; i <= r; i ++ ) a[i] = b[i];
}
int main(){
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    merge_sort(0, n - 1);
    printf("%lld", res);
    return 0;
}

3. 堆排序

题目一

P3378 【模板】堆
解法1

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], len;
void up(int i){
    // 如果父节点不为根节点,且父根节点的值大于子节点,则交换,递归此过程
    if(i / 2 && a[i / 2] > a[i]) swap(a[i], a[i / 2]), up(i / 2);
}
void push(int x){
    a[ ++ len] = x; // 压入x至数组结尾
    up(len); // 上移
}
void down(int i){
    int v = i;
    // 左子节点存在,且左子节点 < 父节点,父节点下移至左子节点
    if(i * 2 <= len && a[i * 2] < a[v]) v = i * 2;
    // 右子节点存在,且右子节点 < 父节点或者左子节点,父节点下移至右子节点
    if(i * 2 + 1 <= len && a[i * 2 + 1] < a[v]) v = i * 2 + 1;
    // 交互 父节点 和 左子节点或者右子节点
    if(i != v) swap(a[i], a[v]), down(v);
}
void pop(){
    a[1] = a[len -- ];
    down(1);
}
int peek(){
    return a[1];
}
int main(){
    int n, op, x;
    scanf("%d", &n);
    while(n -- ){
        scanf("%d", &op);
        if(op == 1){
            scanf("%d", &x);
            push(x);
        }else if(op == 2){
            printf("%d\n", peek());
        }else{
            pop();
        }
    }
    return 0;
}

解法2

#include<bits/stdc++.h>
using namespace std;
int main(){
    priority_queue<int, vector<int>, greater<int>> q;
    int n, op, x;
    scanf("%d", &n);
    while(n -- ){
        scanf("%d", &op);
        switch(op){
            case 1:
                scanf("%d", &x);
                q.push(x);
                break;
            case 2:
                printf("%d\n", q.top());
                break;
            case 3:
                q.pop();
                break;
        }
    }
    return 0;
}

题目二

Luogu P3378 【模板】堆

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], len;
void up(int i){
    // 如果父节点不为根节点,且父根节点的值大于子节点,则交换,递归此过程
    if(i / 2 && a[i / 2] > a[i]) swap(a[i], a[i / 2]), up(i / 2);
}
void push(int x){
    a[ ++ len] = x; // 压入x至数组结尾
    up(len); // 上移
}
void down(int i){
    int v = i;
    // 左子节点存在,且左子节点 < 父节点,父节点下移至左子节点
    if(i * 2 <= len && a[i * 2] < a[v]) v = i * 2;
    // 右子节点存在,且右子节点 < 父节点或者左子节点,父节点下移至右子节点
    if(i * 2 + 1 <= len && a[i * 2 + 1] < a[v]) v = i * 2 + 1;
    // 交互 父节点 和 左子节点或者右子节点
    if(i != v) swap(a[i], a[v]), down(v);
}
void pop(){
    a[1] = a[len -- ];
    down(1);
}
int peek(){
    return a[1];
}
int main(){
    int n, x;
    scanf("%d", &n);
    for(int i = 0; i < n; i ++ ){
        scanf("%d", &x);
        push(x);
    }
    for(int i = 0; i < n; i ++ ){
        printf("%d ", peek()), pop();
    }
    return 0;
}

普通电子计算机1秒钟的算力大概是8亿也就是\(8 \times 10^8\)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int cnt = 0;
    thread t([&](){
        while(true) cnt ++ ;
    });
    t.detach(); // 守护线程

    time_t nowtime;
    time(&nowtime);              // 获取1970年1月1日0点0分0秒到现在经过的秒数
    tm *p = localtime(&nowtime); // 将秒数转换为本地时间, 年从1900算起, 需要+1900, 月为0-11, 所以要+1
    printf("%04d:%02d:%02d %02d:%02d:%02d\n", p->tm_year + 1900, p->tm_mon + 1, p->tm_mday, p->tm_hour, p->tm_min, p->tm_sec);
    this_thread::sleep_for(chrono::seconds(1));
    time(&nowtime);    
    p = localtime(&nowtime);
    printf("%04d:%02d:%02d %02d:%02d:%02d\n", p->tm_year + 1900, p->tm_mon + 1, p->tm_mday, p->tm_hour, p->tm_min, p->tm_sec);
    printf("main: %d\n", cnt);
}

// Windows平台
#include <bits/stdc++.h>
#include <windows.h>
using namespace std;
int main()
{
    int cnt = 0;
    thread t([&](){
        while(true) cnt ++ ;
    });
    t.detach(); // 守护线程
    SYSTEMTIME time;
	GetLocalTime(&time);
	printf("%04d/%02d/%02d %02d:%02d:%02d:%03d\n", time.wYear, time.wMonth, time.wDay, time.wHour, time.wMinute, time.wSecond, time.wMilliseconds);
    this_thread::sleep_for(chrono::seconds(1));
    GetLocalTime(&time);
	printf("%04d/%02d/%02d %02d:%02d:%02d:%03d\n", time.wYear, time.wMonth, time.wDay, time.wHour, time.wMinute, time.wSecond, time.wMilliseconds);
    printf("main: %d\n", cnt);
    return 0;
}
// 789742137

思考: 堆排序为什么是不稳定的呢?

热门相关:全天下都知道太子爱她   青莲剑说   龙印战神   离婚合约:前妻的秘密   妻子的借口