快速排序

每一轮挑选一个基准元素（随机选择，编程时一般选取第一个），并让比它大或小的元素移动到基准元素的两边，把数列拆解成了两个部分。而后对这两部分分别进行快速排序。

时间复杂度：O(nlogn)，辅助空间复杂度：O(logn)，不稳定

最坏时间复杂度：O(n^2)

例如，从小大到排序，找一个基准值为 5。

左侧 8 是第一个比 5 大的数字，右侧 3 是第一个比 5 小的数字。

交换 8 和 5：

最后分为比 5 小的一组和比 5 大的一组，然后继续分治：

#include <bits/stdc++.h>
using namespace std;


const int N = 1e5 + 10;


int n;
int a[N];


void qsort(int a[], int L, int R){
  if(L >= R) return;
  int pivot = a[L];


  int i = L - 1, j = R + 1;
  while(i < j){
    while(a[++i] < pivot);
    while(a[--j] > pivot);
    if(i < j) swap(a[i], a[j]);
  }


  qsort(a, L, j), qsort(a, j + 1, R);
}


int main() {


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


  random_shuffle(a + 1, a + n + 1);
  qsort(a, 1, n);


  for(int i = 1; i <= n; i++) cout << a[i] << ' ';


  return 0;
}

归并排序

对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，逐层进行合并。

时间复杂度：O(nlogn)，辅助空间复杂度：O(n)，稳定。

依次类推：

归并排序常考应用：求逆序对 res = mid - i + 1

#include <iostream>
#include <cstdio>
using namespace std;


typedef long long LL;


const int N = 1e6 + 10;


int n, a[N], tmp[N];
LL ans = 0;
void merge_sort(int a[], int l, int r);


int main() {
  
  scanf("%d", &n);


  for(int i = 1; i <= n; i++)  scanf("%d", &a[i]);


  merge_sort(a, 1, n);


  printf("%lld\n", ans);


  return 0;
}


void merge_sort(int a[], int l, int r){


  if(l >= r)  return;


  int mid = l + r >> 1;


  merge_sort(a, l, mid), merge_sort(a, mid + 1, r);


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


  while(i <= mid && j <= r){
    if(a[i] <= a[j]) tmp[k++] = a[i++];
    else {
      tmp[k++] = a[j++];
      ans += mid - i + 1;
    }
  }
  while(i <= mid) tmp[k++] = a[i++];
  while(j <= r) tmp[k++] = a[j++];
  
  for(int k = 1, i = l; i <= r; i++, k++)  a[i] = tmp[k];
  
}