本文章原出处：chicago01.top，转载不需说明，随意转载

几大常见的排序算法

算法分类

• 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破$O(nlogn)$，因此称为非线性时间比较类排序。
• 线性时间非比较类排序： 不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

[HTML_REMOVED]

时间复杂度

相关定义

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法流程

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤1~3，直到排序完成。

动画演示

http://www.atool.org/sort.php

代码演示

inline void BubbleSort()
{
    int len = arr.length();

    for(int i = 0;i < len - 1;++i)
    {
        for(int j = 0;j < len - 1;++j)
        {
            if(arr[j] > arr[j + i])
            {
                t = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = t;
            }
        }
    }
}

选择排序（Selection Sort）

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法流程

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为R[1..n]，有序区为空；
• 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
• n-1趟结束，数组有序化了。

动画演示

http://www.atool.org/sort.php

代码演示

inline void SelectionSort()
{
    int len = arr.length();
    int minindex,temp;

    for(int i = 0;i < len - 1;++i)
    {
        minindex = i;
        for(int j = i+1;j < len;++i)
        {
            if(a[j] < a[minindex])
                minindex = j;
        }
        temp = a[i];
        a[i] = a[minindex];
        a[minindex] = temp;
    }
}

插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法流程

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

动画演示

http://www.atool.org/sort.php

代码演示

void insertSort(int a[], int n)
{
   for(int i = 1; i < n; i++) 
   //第一个元素作为基准元素，从第二个元素开始把其插到正确的位置
   {
      if(a[i] < a[i-1]) 
       //如果第i个元素比前面的元素小
      {
          int j = i-1;     
          //需要判断第i个元素与前面的多个元素的大小，换成j继续判断
          int x = a[i]; 
          //将第i个元素复制为哨兵
          while(j >= 0 && x < a[j]) 
          //找哨兵的正确位置，比哨兵大的元素依次后移
          {
                a[j+1] = a[j]; 
            j--;
          }
          a[j+1] = x;  //把哨兵插入到正确的位置
      }   
   }
}

归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法流程

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

动画演示

http://www.atool.org/sort.php

代码演示

void Merge(int arr[], int p, int q, int r)
{
    int n1 = q - p + 1;
    int n2 = r - q + 1;
    int left[n1 + 1], right[n2];

    for (int i = 0; i != n1; ++i){
        left[i] = arr[p + i];
    }
    left[n1] = N;

    for (int j = 0; j != n2 - 1; ++j){
        right[j] = arr[q + j + 1];
    }
    right[n2 - 1] = N;

    int i = 0, j = 0;
    for(int k = p; k != r + 1; ++k){
        if(left[i] > right[j]){
            arr[k] = right[j];
            ++j;
        }
        else{
            arr[k] = left[i];
            ++i;
        }
    }
}
void MergeSort(int arr[], int p, int r)
{
    if(p < r){
        int q = (p + r)/2;
        MergeSort(arr, p, q);
        MergeSort(arr, q + 1, r);
        Merge(arr, p, q, r);
    }
}

快速排序（Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法流程

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

动画演示

http://www.atool.org/sort.php

代码演示

void quicksort(int left, int right) 
{
    int i, j, t, temp;
    if(left > right)
        return;
    temp = a[left]; //temp中存的就是基准数
    i = left;
    j = right;
    while(i != j) { //顺序很重要，要先从右边开始找
        while(a[j] >= temp && i < j)
            j--;
        while(a[i] <= temp && i < j)//再找右边的
            i++;       
        if(i < j)//交换两个数在数组中的位置
        {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    //最终将基准数归位
    a[left] = a[i];
    a[i] = temp;
    quicksort(left, i-1);//继续处理左边的，这里是一个递归的过程
    quicksort(i+1, right);//继续处理右边的 ，这里是一个递归的过程
}

离散化

在很多情况下，问题的范围虽然定义在整数集合$Z$，但是只涉及其中$m$个有限数值，并且与数值的绝对大小无关（只把这些数值作为代表，或只与它们的相对顺序有关）。此时，我们就可以把整数集合$Z$中的这$m$个整数与$1～m$建立映射关系。

通俗来讲，就是把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。

算法流程

• 预处理

• 先将无序数组排序。

• 去重。

• 二分查找

知识拓展

1. C++STL中的unique函数解析
2. C++ lower_bound 与 upper_bound 函数

模板

//离散化预处理
inline void discrete()
{
    //排序
    sort(a + 1,a + n + 1);
    //去重
    for(int i = 1;i <= n;++i)
    {
        if(i == 1 || a[i] != a[i-1])
            b[++m] = a[i];
    }
}

//二分查找 x映射为那个1~m之间的整数
inline int query(int x)
{
    return lower_bound(b + 1,b + m + 1,x) - b;
}

例1 Cinema

莫斯科正在举办一个大型国际会议，有$n$个来自不同国家的科学家参会。

每个科学家都只懂得一种语言。

为了方便起见，我们把世界上的所有语言用$1$到$10^9$之间的整数编号。

在会议结束后，所有的科学家决定一起去看场电影放松一下。

他们去的电影院里一共有$m$部电影正在上映，每部电影的语音和字幕都采用不同的语言。

对于观影的科学家来说，如果能听懂电影的语音，他就会很开心；如果能看懂字幕，他就会比较开心；如果全都不懂，他就会不开心。

现在科学家们决定大家看同一场电影。

请你帮忙选择一部电影，可以让观影很开心的人最多。

如果有多部电影满足条件，则在这些电影中挑选观影比较开心的人最多的那一部。

输入格式

第一行输入一个整数$n$，代表科学家的数量。

第二行输入$n$个整数$a_1,a_2…a_n$,其中$a_i$表示第$i$个科学家懂得的语言的编号。

第三行输入一个整数$m$，代表电影的数量。

第四行输入$m$个整数$b_1,b_2…b_m$,其中$b_i$表示第i部电影的语音采用的语言的编号。

第五行输入$m$个整数$c_1,c_2…c_m$,其中$c_i$表示第i部电影的字幕采用的语言的编号。

请注意对于同一部电影来说，$b_i≠c_i$。

同一行内数字用空格隔开。

输出格式

输出一个整数，代表最终选择的电影的编号。

如果答案不唯一，输出任意一个均可。

数据范围

$1≤n,m≤200000$,
$1≤a_i,b_i,c_i≤10^9$

输入样例：

3
2 3 2
2
3 2
2 3

输出样例：

2

题解

用不可重集map来进行映射，很容易想到。

然后再排序查找，这里要进行重载，因为语言和字幕的权重是不一样的。

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

const int MAX = 200010;
int n,mm;
unordered_map<int, int> m;

struct node {
    int pos,lan,sub;
    bool operator <(const node &num) const
    {
        if(lan == num.lan) return sub > num.sub;
        else return lan > num.lan;
    }
}a[MAX];

inline void init()
{
    cin >> n;
    for(int i = 1;i <= n;++i)
    {
        int x;
        cin >> x;
        m[x]++;
    }

    cin >> mm;
    for(int i = 1;i <= mm;++i)
    {
        int x;
        cin >> x;
        a[i].pos = i;
        a[i].lan = m[x];
    }

    for(int i = 1;i <= mm;++i)
    {
        int x;
        cin >> x;
        a[i].sub = m[x];
    }
}

inline void find()
{
    sort(a+1,a+mm+1);
    cout << a[1].pos;
}

int main(void)
{
    init();

    find();

    return 0;
}

中位数

没什么，就是中位数。。。

例1 货仓选址

在一条数轴上有 $N$ 家商店，它们的坐标分别为 $A_1$~$A_N$。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入格式

第一行输入整数$N$。

第二行$N$个整数$A_1$~$A_N$。

输出格式

输出一个整数，表示距离之和的最小值。

数据范围

$1≤N≤100000$

输入样例：

4
6 2 9 1

输出样例：

12

题解

排序之后查找中位数，然后相加，完事。

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

const int MAX = 1e5 + 10;
int num[MAX],n;

inline void init()
{
    cin >> n;

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

inline long long find()
{
    sort(num+1,num+n+1);

    int mid = num[(1+n)/2];
    long long ans = 0;

    for(int i = 1;i <= n;++i)
        ans += abs(num[i] - mid);

    return ans;
}

int main(void)
{
    init();

    cout << find();

    return 0;
}

逆序对

设有一个序列$a_1, a_2, a_3,…a_{n-1}, a_n$,对于序列中任意两个元素$a_i,a_j$，若$i<j,a_i>a_j$，则说明$a_i$和$a_j$是一对逆序对。

逆序对求解

暴力

写两层循环，时间复杂度为$O(n^2)$ 。

归并排序

比如将下面两个区间排序

$a_i$ $mid=4$ $a_j$

$3,4,7,9$ $1,5,8,10$

首先将右区间的 $1$ 取出，放到$r_k$中，此时 $1$ 是比每个$a_i$中的元素都小，也就是说此时i的指针指向 $a_1$ 的位置，此刻得到的逆序对的数量为 $4$ ； $r_k= 1$ ;

然后再将$a_i$和$a_j$比较（直到$a_i<a_j$），$a_i<a_j$ 将$a_i$的元素放到$r_k$中； $r_k= 1,3,4$;

现在$a_j>a_i$,$ i$ 指向$a_3$的位置，将 $5$ 放到$r_k$中，得到的逆序对数量为 $2$ ； $r_k= 1,3,4,5$

以此类推，直到进行完归并排序，每次合并都会求出逆序对的数目，即$mid-i+1$,最后每次将$ans$加上$mid-i+1$即可得到最后的答案；

树状数组

咕咕咕。。。。

参考资料

1. 十大经典排序算法总结
2. 洛谷：逆序对题解