跳转至

排序

稳定性ψ(｀∇´)ψ

就是说，假设原序列当中有两个相同的元素 \(a_i, a_j\)。

如果这个排序算法没有改变 \(a_i, a_j\) 的相对位置。

那么这个排序算法就是稳定的。

基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序。

选择排序、堆排序、快速排序不是稳定排序。

选择排序ψ(｀∇´)ψ

就是遍历 \(n\) 轮 \(1 \to n\)，第 \(i\) 轮找到第 \(i\) 小的数，然后放到位置 \(i\) 上（实现时把这个数和 \(a_i\) 交换）。

平均，最坏，最优，复杂度 \(O(n^2)\)，因为每次循环次数是固定的。

1
2
3
4
5
6
7
for(int i = 1; i < n; ++i) {
  int ith = i;
  for(int j = i + 1; j <= n; ++j) {
    if(a[j] < a[ith]) ith = j;
  }
  swap(a[i], a[ith]);
}

插入排序ψ(｀∇´)ψ

类似打牌的时候的排序方法。

把原序列分成【没有排序】和【排序过】两部分。

每次从【没有排序】的里面抓一张，扔到【排序过】的一个合适位置（第一个大于它的元素）前面。

具体实现是，从 \(2\) 开始，假设 \([1, i)\) 是已经排序过的，然后对于 \(a_i\)，不断让前面的元素后移，直到找到合适的位置，就把 \(a_i\) 放进去。

1
2
3
4
5
6
7
for(int i = 2; i <= n; ++i) {
  int key = a[i]; // 注意要提前储存 a[i]，不然第一次后移 a[i] = a[i - 1] 就把 a[i] 覆盖掉了。
  int j = i - 1;
  while(j > 0 && a[j] > key) 
    a[j + 1] = a[j], --j;
  a[j + 1] = key;
}

最优复杂度 \(O(n)\)，就是如果序列已经排好了就完全不会后移，是稳定的排序。

最坏复杂度 \(O(n^2)\)，如果序列翻转过来，总共要跑的距离就是 \(\sum\limits_{i = 1}^{n} (i - 1) = O(n^2)\)。

平均复杂度是 \(O(n^2)\)。

冒泡排序ψ(｀∇´)ψ

扫特别多遍，每次扫描都交换看到的逆序对。

然后可以证明，扫完第 \(i\) 轮之后，后 \(i\) 项是最大的 \(i\) 项。

这个用数学归纳法就能证明。

就是你考虑第一轮，假设在位置 \(x\) 找到了最大的元素，它必然会被一直交换交换交换，然后一直交换到最后。

第二轮必然会把第二大的元素交换交换到 \(n-1\)。

以此类推可以证明冒泡排序的正确性，这个过程就好比泡泡冒上去一样，所以叫冒泡排序。

1
2
3
4
5
6
7
8
bool ff = true;
while(ff) {
  ff = false;
  for(int i = 1; i < n; ++i) {
    if(a[i] > a[i + 1]) 
      ff = true, swap(a[i], a[i + 1]);
  }
}

最优复杂度就是已经排序过的情况，扫一遍就完了，复杂度 \(O(n)\)。

最坏情况，就是翻转过来，要交换 \(\dfrac{n(n - 1)}{2} = O(n^2)\) 次。

平均复杂度是 \(O(n^2)\)。

显然是稳定的，因为考虑两个相同的元素 \(a_x, a_y, x < y\)，那么 \(a_x\) 被交换到 \(y - 1\) 的位置的时候就不会被交换到后面了（因为写的 \(a_i > a_{i + 1}\) 才交换），那 \(a_y\) 必然先被换到后面，相对顺序没有改变。

关于冒泡排序有一个结论（来自 POJ2299 - Ultra-QuickSort）

就是，如果只允许进行比较和交换相邻两项的操作（就是冒泡排序）。

对于一个给定序列 \(a\)，让他有序，最少需要的操作次数就是 \(a\) 的逆序对个数。

所以冒泡排序使一个序列有序的交换次数应当是 \(a\) 的逆序对个数。

（因为冒泡每执行一次交换操作，就相当于消除了一个逆序对，并且之后不会再让这个逆序对出现）

计数排序ψ(｀∇´)ψ

开一个桶，维护值域 \(|w|\)，（注意这个不是桶排是计数）。

然后 \(O(n)\) 扫一遍把所有元素扔进桶里面。

然后从小到大拿出来就行了，显然是稳定的，因为先出现的会被先放进桶，你可以把桶理解为一个队列。

但这样还不够快，因为值域里面不一定都会出现。

所以给桶做一个前缀和，倒过来计算一下排名就行了。

1
2
3
4
5
6
for(int i = 1; i <= n; ++i) 
  cnt[a[i]]++;
for(int i = 1; i <= w; ++i)
  cnt[i] += cnt[i - 1];
for(int i = n; i >= 1; --i) 
  b[cnt[a[i]]--] = a[i];

复杂度稳定 \(O(n + w)\)。

快速排序ψ(｀∇´)ψ

每次把序列分成两个部分，其中第一个子序列的数都小于后一个子序列的数。

然后递归到每个子序列里面在搞。

最后递归完了就直接有序了，一般实现的时候会随机选一个分界 \(key\)，大于 \(key\) 的扔到后面，小于等于 \(key\) 的扔到前面。

然后有一种叫三路快排的优化，就是把等于的单独扔到基准分界值附近，这样多个相等的元素就会聚集在一起，减小之后多次处理的常数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void Qsort(int a[], int len) {
  if(len <= 1) return;
  int key = a[1 + rand() % len];
  // i：当前操作的元素
  // j：第一个等于 key 的元素
  // k：第一个大于 key 的元素
  int i = 1, j = 1, k = len + 1;
  // 完成一趟三路快排，将序列分为：
  // 小于 pivot 的元素｜ 等于 pivot 的元素 ｜ 大于 pivot 的元素
  while(i < k) {
    if(a[i] < key) swap(a[i++], a[j++]);
    else if(a[i] > key) swap(a[i], a[--k]);
    else ++i;
  }
  Qsort(a, j - 1), Qsort(a + k - 1, len - k + 1);
}

明显不稳定，原始快排最坏 \(O(n^2)\)，平均最优都是 \(O(n \log n)\)。

因为每次取 key 的时候，如果每次都能取到中位数作为分界，递归式是 \(T(n) = 2T(n/2) + \Theta(n)\)，主定理可以得到。

如果每次都取到最大值，递归式就是 \(T(n) = T(n - 1) + \Theta(n)\)（长度等于一不用递归），累加可以得到。

归并排序ψ(｀∇´)ψ

很有意思的一个算法。

就是把序列先从中间分开，然后递归下去对两块块内排序，

递归回来，假设此时序列左右两半都已经从小到大排序好（先不管它怎么排的，因为这是一个递归，最后只有一个元素的时候就是排序好的，然后一层一层返回上来合并的时候就排好序了）。

然后直接不断取两块的“头”的最小值，扔进一个辅助数组。

最后赋值一下就行了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void MergeSort(int l, int r) {
  if(l >= r) return; // length == 1 or < 1
  int mid = (l + r) >> 1;
  MergeSort(l, mid), MergeSort(mid + 1, r);
  for(int i = l, j = mid + 1, k = l; k <= r; ++k) {
    if((j > r) || (i <= mid && a[i] <= a[j])) // 注意用 <= 保证稳定性
      tmp[k] = a[i++];
    else tmp[k] = a[j++];
  }
  for(int i = l; i <= r; ++i) a[i] = tmp[i];
}

稳定的 \(O(n \log n)\) 的排序。

然后这个是可以拿来做逆序对的。

因为选后一段的时候就相当于消除了逆序对，个数是前一段当前没有加进去的数的个数。

就是 mid - i + 1 个。

代码见下面逆序对板块。

还有一种利用它线性找第 \(k\) 大的算法，因为不是稳定的，所以找不到最前的一个第 \(k\) 大。

但是 Median of Median 可以最坏 \(O(n)\) 做稳定的第 \(k\) 大。

一些简单应用ψ(｀∇´)ψ

离散化ψ(｀∇´)ψ

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
vector<int>v;
int main(){
    for(register int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        v.push_back(a[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(register int i=1;i<=n;++i){
        a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
    }
}

思想就是把一些特别大的数映射到一个比较小的范围之内。

需要的话可以另外新开一个数组存离散之后的值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// 二维
vector<int>v;
int main(){
    for(register int i=1;i<=n;i++){
        scanf("%d%d%d",&x[i],&y[i],&e[i]);
        v.push_back(x[i]);
        v.push_back(y[i]);
    }
    sort(v.begin(),v.end()); // 排序
    v.erase(unique(v.begin(),v.end()),v.end()); // 去重
    for(register int i=1;i<=n;i++){
        x[i]=lower_bound(v.begin(),v.end(),x[i])-v.begin()+1;
        y[i]=lower_bound(v.begin(),v.end(),y[i])-v.begin()+1;
    } // 只用一个 vector 会省空间
}

对顶堆ψ(｀∇´)ψ

维护动态中位数问题。

假设每个时刻序列 \(a\) 的长度 \(n\) 都是奇数。

那么让排名在 \(1 \to \lfloor m/2 \rfloor\) 的扔到大根堆，其他的扔到小根堆。

如果某个堆不满足条件，那么把它的堆顶扔到另外一个堆去。

答案就是小根堆的堆顶。

逆序对ψ(｀∇´)ψ

定义逆序对为形如 (i, j)，保证 \(i < j, a_i > a_j\) 的点对。

求一个序列的逆序对个数。

最简单的做法就是暴力 \(O(n^2)\)。

\(\log\) 做法可以树状数组，也可以归并排序。

树状数组做法可能更简单一点。

只需要离散化，然后动态加入，每次加入的时候查一查前面比他大的数有多少个即可。

归并排序的话：

代码实现中的 ans += mid - i + 1 就是在统计逆序对个数。

具体来说，算法把靠后的数放到前面了（较小的数放在前面），所以在这个数原来位置之前的、比它大的数都会和它形成逆序对，而这个个数就是还没有合并进去的数的个数，即 mid - i + 1。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void MergeSort(int l, int r) {
  if(l >= r) return;
  MergeSort(l, mid), MergeSort(mid + 1, r);
  for(int i = l, j = mid + 1, k = l; k <= r; ++k) {
    if((j > r) || (i <= mid && a[i] <= a[j]))
      tmp[k] = a[i++];
    else tmp[k] = a[j++], ans += (mid - i + 1);
  }
  for(int i = l; i <= r; ++i) a[i] = tmp[i];
}
最后更新: May 9, 2023