排序综合

· · 个人记录

[0.x]前言

本文针对初赛

程序以cpp为例

由于时间关系，并非所有算法都提供了样例代码

参考github项目LeetCodeAnimation

本blog中的动图全部引用这里

<!-- more -->

目录

[1.x]十大排序

[1.0]概述

排序，顾名思义，将一组数据按照一定顺序重新排列。很容易看出这是非常常用的东西，因此我们肯定希望更快的实现它。但不同的排序有不同的性质，其中的思想也有很大的学习价值，所以我们要尽数掌握。(其实只是初赛要考？)

大的来分，排序分为内排序和外排序，两者的区别并不是我们学习的重点。我们移步到内排序。内排序分为比较类和非比较类，两者的区别自然是是否需要比较。

不过论实际码题的时候，使用<algorithm>中的sort()在大部分情况下是够用的(cpp)。(至少在蒟蒻这个水平是完全够用的嘤嘤嘤)

首先在初赛范围内，考察排序算法的原理、时间复杂度、稳定性。首先贴一张全表。

[1.1]冒泡排序

冒泡排序的名字是其原理的形象比喻。关于冒泡最优情况下为什么是O(n)将在算法示例之后。算法实现如下：

算法描述：

1.第i轮，从i位开始，令j=i

2.比较j和j+1上的数，并进行有序化(如果需要升序就将小的放在前面，反之把大的放在前面，为保证稳定性相等不变换)

3.不断重复[2]直到j==n返回true

4.1.如果i<n，那么i=i+1并返回[1]

4.2.如果i =n，排序结束

算法样例：

#include<iostream>
using std::cin;using std::cout;
int n,a[1000];
void swap(int *p,int *q){
    int c = *p; *p = *q , *q = c;
    return;
}
int main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    /*主体开始*/
    for(int i = 1;i <= n-1;i++){
        for(int j = i;j <= n-1;j++){
            if(a[j] > a[j + 1]) swap(&a[j] , &a[j + 1]); 
        }
    }
    /*主体结束*/
    for(int i = 1;i <= n;i++){
        cout << a[i] << " ";
    }
}

补充说明：关于冒泡排序的最优情况问题，我们可以用一个flag标记，如果它在第一次扫描过程中没有交换，显然得到这是一个有序数列。那么就不需要之后的n-2次扫描了

[1.2]快速排序

快排是比较常用的排序算法，也是<algorithm>中sort()的原型。算法实现如下：

算法描述：

1.选择基数作为比较对象。(一般选择最左或最右)

2.令除基数外的最左数下标为l,最右数下标为r

3.判断r位数字是否比基数小(升序时)，如果不是，那么r左移

4.判断l位数字是否比基数大(升序时)，如果不是，那么l右移

5.当l==r返回true时将i位数和基数交换

6.对1至l-1和r+1至n分别进行[1] (二分过程)

算法样例：

#include <iostream>
using std::cin;using std::cout;using std::swap;
int a[100001],n;
void q_sort(int L,int R){
    //默认最左的a[L]为基数 
    if(L > R) return;
    int l,r;
    l = L , r = R;
    while(l != r){
        while(l < r && a[r] >= a[L]) r--;
        while(l < r && a[l] <= a[L]) l++;
        if(l < r) swap(a[l] , a[r]);
    }
    swap(a[l] , a[L]);
    q_sort(L,l-1);
    q_sort(l+1,R);
    return;
}

int main(){
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    q_sort(1,n);
    for(int i = 1;i <= n;i++){
        cout << a[i] <<" ";
    }
    return 0;
}

[1.3]插入排序

插入排序首先构造有序数列，然后将无序数列中的元素插入到有序数列中。

算法描述：

1.第i轮，有1~i为有序数列。令j=i+1

2.j不断左移，比较j位和i+1位的数的大小，并进行插入操作，返回[1]

[1.4]希尔排序

希尔排序十分迷幻，你可以发现它的复杂度十分一枝独秀

[1.5]选择排序

选择排序它看起来非常稳定，但其实还是存在问题的，放在最后解释。

算法描述：

1.扫描无序数列，找到【最小/最大】的一个，将它放到无序数列前，有序数列末。

2.重复[1]直到不存在无序数列

算法示例：

#include<iostream>
using std::cin;using std::cout;using std::swap;
int n,a[1000],min;
int main(){
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 2;i <= n - 1;i++){
        for(int j = i + 1;j <= n;j++)
         min = a[i] <= a[j] ? i : j;
        swap(a[min] , a[i]);
    }
    for(int i = 1;i <= n;i++) cout << a[i] << " ";
}

补充说明：

确实，乍一看选择排序好像很稳定。但实际上并非如此。

确实，在每一次交换过程中，我们能保证min位上的数和其后的与它等大的数的相对位置不变。但是，在你交换的过程中，和min交换的那个数的稳定性就被破坏了。什么意思？举个例子：

在无序数列5_A 3_A 5_B 1_A 2_A中，模拟知道我们需要将5_A和1_A交换，于是数列就变成了1_A 3_A 5_B 5_A 2_A，显然，5的稳定性就被破坏了。

[1.6]堆排序

堆排利用了【大根堆/小根堆的性质】

大根堆性质：任何一个非叶节点的值不小于其左儿子和右儿子的值

根据该性质，我们可以得到，我们维护的大根堆的根节点是整个数列中最大的。

小根堆反之。

算法描述：

1.1.将数列中的第一个元素一次推如堆底，并将该数从队列中删除

1.2.依据堆的性质将底部的元素向根部移动，返回[1.1]

1.3.等到全部元素被推入堆中，建堆完成

2.1.输出堆根，然后将堆根删除，将堆底元素直接移动到堆根

2.2.根据堆的性质下移，返回[2.1]

2.3.等到堆为空，则输出完成

[1.7]归并排序

归并排序将原数列不断分裂，然后再将有序数列合并。

算法描述：

1.选取目标队列mid，将数列分为两部分，作为新的目标队列

2.当目标队列中元素数量为2或1，或该序列的所有子序列已经被分别有序化时，不断比较两个子序列的首尾，将较小(升序时)的一项推入储存数组，得到储存数组中的有序数列后覆盖原数列。返回[1]

算法示例：

#include<iostream>
using std::cin;using std::cout;
int n,a[1000],tmp[1000];
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 , p = l , j = mid + 1;
    //归并
    while(i <= mid && j <= r){
        if(a[i] > a[j]) tmp[p++] = a[j++];
        else tmp[p++] = a[i++];
    }
    //处理奇数元素情况下的多余元素
    while(i <= mid) tmp[p++] = a[i++];
    while(j <= r) tmp[p++] = a[j++];
    //覆盖原数列
    for(int i = l;i <= r;i++){
        a[i] = tmp[i];
    }
}
int main(){
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    merge_sort(1,n);
    for(int i = 1;i <= n;i++) cout << a[i] << " ";
    return 0;
}

[1.8]计数排序

计数排序其实是朴素桶排的优化版本(反正浪费空间的德行是一样的)，区别就是选取了起点和终点，适合数据偏差值较小，但都偏大的数据范围。

[1.9]桶排序

没写这篇博客之前我都不知道桶排还可以这样玩(妙得一匹啊)

[1.10]基数排序

一个原理非常神奇的排序方法，按照每一位的大小进行排序，用队列维护先进先出的性质就可以保证稳定性。

[2.x]其他排序

此处为考点外的内容，用来补充说明课外知识

[2.1]地精排序

传送门

[2.2] Bogo Sort / 猴子排序

#include<iostream>
#include<algorithm>
#define rep(i,a,b) for(register long long i = (a);i <= (b);++i)
int n,a[1000010];
inline bool judge(){
    bool flag = true;
    rep(i,2,n) if(a[i - 1] > a[i]){flag = false; break;}
    return flag;
}
int main(){
    std::cin >> n;
    rep(i,1,n) std::cin >> a[i];
    while(!judge()) std::random_shuffle(a + 1,a + n + 1);
    rep(i,1,n) std::cout << a[i] << " ";
    return 0;
}