排序

比较排序

冒泡排序

简单插入排序

简单选择排序

归并排序

描述：

归并排序，使用双指针和分治的思路

步骤（仅以递增为例）:

1. div（分）
2. merge（sort 步骤）

div: 每次操作把数组分为两半，直到无法再分为止

merge: 假设已经有两段有序数组，i 指针和j 指针分别指向两数组的头部：

1. 比较i，j指针指向元素的值
   • 把较小的元素优先排列（放入结果数组），假设为i 指针
   • i 指针向后移动，继续与j 指针比较，直到某一数组中已经没有元素
   • 把另一数组剩余元素，全部放入结果数组中

时间复杂度：$O(nlogn)$（最稳定）

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int a[N];
int b[N];
int n;

void merge_sort(int l, int r){
    if (l >= r) return;

    int mid = l + r >> 1;

    sort(l, mid), sort(mid + 1, r);

    int i = l, j = mid + 1, k = 0;

    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 (int k = 0, i = l; i <= r; i ++, k ++) a[i] = b[k];

}

int main(){

    cin >> n;

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

    merge_sort(0, n - 1);


    for (int i = 0; i < n ; i ++)
    {
        if (i) cout << ' ';
        cout << a[i];
    }

    return 0;
}

逆序对的数量

逆序对的定义：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。

描述： 利用归并算法的`分治`思想，递归地解决问题：

• div: 计算相邻元素间的逆序对数
• merge: 计算相邻数组间的逆序对数

  同一意思：应当把元素和数组都看为同单位

时间复杂度：$O(nlogn)$

#include <iostream>
#define LL long long

using namespace std;

const int N = 1e5 + 10;
int a[N];
int b[N];
int n;

LL merge_sort(int l, int r){
    if (l >= r) return 0;

    int mid = l + r >> 1;

    LL res = 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]) 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 (int k = 0, i = l; i <= r; i ++, k ++) a[i] = b[k];

    return res;

}

int main(){

    cin >> n;

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

    LL res = merge_sort(0, n - 1);

    cout << res;

    return 0;
}

TIP

理解 res += mid - i + 1

由于递增，仅当 a[j] < a[i] 才需要计算逆序对

而左右两数组已排序好，因此，可由a[j] < a[i]知：a[j] < a[i~mid]

即：有mid - i + 1 个逆序对数

希尔排序

快速排序

描述：

快速排序， 使用双指针和分治的思路

选择头，尾或中间的元素作为参考 xi 指针从头遍历，j 指针从尾遍历

:

1. i 指针遍历到的元素比参考 x大
2. j 指针遍历到的元素比参考 x小
3. 交换i 指针和j 指针指向的元素

重复三个步骤：直到i 指针与j 指针互相穿过，说明数组已经被分成两部分：

• 比参考 x小的部分
• 比参考 x大的部分

因此只要递归地排序两部分，直到再也分不出两部分（此时的边界还是l>=r）

时间复杂度：

• 最优：$O(nlogn)$
• 最坏：$O(n^2)$

#include <iostream>

using namespace std;

const int N = 1e5 + 5;
int a[N];
int n;

void quick_sort(int l, int r){
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = a[l + r >> 1 ];

    while (i < j){
        do ++ i; while (a[i] < x);
        do -- j; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }

    quick_sort(l, j), quick_sort(j + 1, r);

}

int main() {

    cin >> n;

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

    quick_sort(0, n - 1);

    for (int i = 0 ; i < n ; i ++)
    {
        if (i) cout << ' ';
        cout << a[i];
    }

    return 0;
}

第 k 个数

描述：

因此可以舍弃另一半，继续搜索（排出更小的范围），边界当然就是 q[l] == q[k]

时间复杂度：$O(n)$

#include <iostream>

using namespace std;

const int N = 1e5 + 5;
int a[N];
int n, m;

int quick_sort(int l, int r, int k){
    if (l >= r) return a[l];

    int i = l - 1, j = r + 1, x = a[l + r >> 1 ];

    while (i < j){
        do ++ i; while (a[i] < x);
        do -- j; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }

    if (k <= l + 1) return quick_sort(l, j, k);
    else return quick_sort(j + 1, r, k));
}

int main() {

    cin >> n >> m;

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

    cout << quick_sort(0, n - 1, m);

    return 0;
}