Home 排序算法
Post
Cancel

排序算法

ssc.png Double Bubbles

还记得什么是稳定排序吗, C++ 里的稳定排序是 stable_sort, 原理是归并排序; 而 sort 是不稳定的, 原理是快速排序.

归并排序

归并排序 (merge sort) 是稳定排序算法.

归并排序基于分治思想将数组分段排序后合并, 时间复杂度在最优、最坏与平均情况下均为 $O(n\log{n})$, 空间复杂度为 $O(n)$.

归并排序可以只使用 $O(1)$ 的辅助空间, 但为便捷通常使用与原数组等长的辅助数组.

写法一: 数组索引范围是 [l,r)

1
2
3
4
5
6
7
8
9
10
11
void merge(int l,int r){ //数组索引范围是[l,r)
    if(r-l<=1) return;
    int mid=l+(r-l)>>1;
    merge(l,mid),merge(mid,r); //[l,mid) [mid,r)
    int i=l,j=mid,k=l;
    for(;k<r;++k){
        if(j==r||(i<mid&&a[i]<=a[j])) b[k]=a[i++];
        else b[k]=a[j++];
    }
    for(i=l;i<r;++i) a[i]=b[i]; //将b中的数据复制回原数组a
}

写法二: 数组索引范围是 [l,r]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void merge(int l,int r){ //数组索引范围是[l,r]
    if(r<=l) return;
    int mid=l+(r-l)>>1;
    merge(l,mid),merge(mid+1,r); //[l,mid] [mid+1,r]
    int i=l,j=mid+1,k=l;
    for(;k<=r;++k){
        if(j==r+1||(i<=mid&&a[i]<=a[j])) b[k]=a[i++];
        else b[k]=a[j++];
    }
    for(i=l;i<=r;++i) a[i]=b[i];
    //
    // // or:
    //
    // int k=start;
    // while(start1<=end1&&start2<=end2)
    //     t[k++]=a[start1]<a[start2]?a[start1++]:a[start2++];
    // while(start1<=end1)
    //     t[k++]=a[start1++];
    // while(start2<=end2)
    //     t[k++]=a[start2++];
    // for(i=start;i<=end;++i) a[i]=t[i];
}

求逆序对

对于当前的区间 [l,r], 由于 [l,mid][mid+1,r] 都已经有序了, 所以在求逆序对的时候只需要作如下考虑:

如果对 i<j, 有 a[i]>a[j], 那么就说明 a[i],a[j] 是一对逆序对. 而从索引为 i 的元素到索引为 mid 的元素都是有序的且都大于等于 a[i], 所以 a[i] ... a[mid] 必定大于 a[j], 也就是说 a[j] 可以分别和 a[i] ... a[mid] 构成 mid-i+1 个逆序对.

我们不考虑索引在 [mid+1,j) 范围内的元素, 因为它们在指针指到 i, j 之前已经加过了. 也就是说, 我们其实是对每个 j 找出它在 [l,mid] 范围内的逆序对数量, 然后加起来.

例题

写法一: 全写到一个 merge 函数里, 在 merge 函数里递归.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int ans=0;
void merge(int l,int r){ //[l,r]
    if(r<=l) return;
    int mid=l+(r-l)>>1;
    merge(l,mid),merge(mid+1,r);
    int i=l,j=mid+1,k=l;
    for(;k<=r;++k){
        if(i<=mid&&j<=r&&a[i]>a[j]){
            ans+=mid-i+1;
            b[k]=a[j++];
        }else if(j==r+1||(i<=mid&&a[i]<=a[j]))
            b[k]=a[i++];
        else b[k]=a[j++];
    }
    for(i=l;i<=r;++i) a[i]=b[i];
}

写法二: 另一种常见的写法, 写到两个函数里, 即 mergemergeSort 函数, 在 mergeSort 函数里递归.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void merge(int l,int m,int r){ //[l,r]
    int i=l,j=m+1,k=l;
    while(i<=m&&j<=r){
        if(a[i]>a[j]){
            tmp[k++]=a[j++];
            ans+=m-i+1;
        }else tmp[k++]=a[i++];
    }
    while(i<=m) tmp[k++]=a[i++];
    while(j<=r) tmp[k++]=a[j++];
    for(i=l;i<=r;++i)
        a[i]=tmp[i];
}
void mergeSort(int l,int r){
    if(l<r){
        int m=(l+r)>>1;
        mergeSort(l,m);
        mergeSort(m+1,r);
        merge(l,m,r);
    }
}

其实细心的读者可能还会发现, 常见的归并模板在排序时也有两种写法, 一种是 3 个 while 循环, 一种是一个 for 循环里面用 if 判断. 从上面的几段代码其实就可以看出来. 当然了, 你喜欢哪种就写哪种.

正是因为归并排序将两个区间的元素按其原有顺序「复制」到另一个数组中, 因此是『稳定』的.

快速排序

快速排序(英语:Quicksort),又称分区交换排序(英语:partition-exchange sort),简称「快排」,是一种被广泛运用的排序算法。

快速排序的基本思想是:

快速排序的工作原理是通过『分治』的方式来将一个数组排序。

快速排序分为三个步骤:

  • 将数列划分为两部分(要求保证相对大小关系);
  • 递归到两个子序列中分别进行快速排序;
  • 不用合并,因为此时数列已经完全有序。

其实很容易看到, 归并排序是先排序小区间再排序大区间, 快速排序是先排序大区间再排序小区间.

通过一次排序将要排序的数据分为两部分,其中一部分的所有数据都比另一部分的所有数据小,然后再分别对这两部分进行快速排序。妥妥的二分思想了属于是。

归并排序是两份数据各自有序了, 但两份之间不确定; 快速排序是两份数据之间确定了大小关系, 即一份中所有的数据都比另一份的所有数据小, 但是每一份内部的数据可能是无序的.

下面给出几种快速排序的实现方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
void quickSort(int a[],int low,int high){ //[low,high]
    if(low>=high) return;
    int i=low,j=high;
    int x=a[low];
    while(i<j){
        while(i<j&&a[j]>=x) j--;
        if(i<j) a[i++]=a[j];
        while(i<j&&a[i]<=x) i++;
        if(i<j) a[j--]=a[i];
    }
    a[i]=x;
    quickSort(a,low,i-1);
    quickSort(a,i+1,high);
}
int main(){
    int a[10]={8,1,9,7,2,4,5,6,10,3};
    quickSort(a,0,9);
    return 0;
}

具体来说, 快速排序是要把数列分成两个部分, 然后保证前一个子数列中的数都小于后一个子数列中的数. 为了保证平均时间复杂度, 一般是随机选择一个数 pivot 来当做两个子数列的分界. 上面的代码选择的是当前区间的第一个数作为 pivot, 下面的代码选择的是当前区间中处于中间位置的数作为 pivot. 下面的做法比较适用于已经大部分排好序的数列, 因为这样可以较大可能地取到当前区间的中位数. 这是一种朴素优化思想.

注意我这里的表述: 中位数是指排序后的数列中间位置的数, 中间位置的数是随便给一个序列, 索引位于中间位置的数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
using namespace std;
int n,a[1000001];
void qsort(int l,int r)//应用二分思想
{
    int mid=a[(l+r)/2];//中间数
    int i=l,j=r;
    do{
        while(a[i]<mid) i++;//查找左半部分比中间数大的数
        while(a[j]>mid) j--;//查找右半部分比中间数小的数
        if(i<=j)//如果有一组不满足排序条件(左小右大)的数
        {
            swap(a[i],a[j]);//交换
            i++;
            j--;
        }
    }while(i<=j);//这里注意要有=
    if(l<j) qsort(l,j);//递归搜索左半部分
    if(i<r) qsort(i,r);//递归搜索右半部分
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    qsort(1,n);
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}

快速排序是一种不稳定的排序算法。

快速排序的最优时间复杂度和平均时间复杂度为 $O(n\log{n})$, 最坏时间复杂度为 $O(n^2)$.

  • 最优情况下, 每一次选择的分界值 pivot 都是序列的中位数, 每个长度为 n 的区间都要比较 n 次, 且递归的时候两个子区间长度都是 $\dfrac{n}{2}$, 递推式为: $T(n)=2T(n/2)+\Theta(n)$.
  • 最坏情况下, 每一次选择的分界值都是序列的最值, 每个长度为 n 的区间都要比较 n 次, 且递归的时候两个子区间长度分别是 n-1 和 1, 递推式为: $T(n)=2T(n/2)+\Theta(n)$.
  • 对于平均情况, 每一次选择的分界值可以看作是等概率随机的.

三路快速排序

常见的朴素优化思路:

  • 通过三数取中(即选取第一个、最后一个以及中间的元素中的中位数)的方法来选择两个子序列的分界元素。这样可以避免极端数据(如升序序列或降序序列)带来的退化;
  • 当序列较短时,使用插入排序的效率更高;
  • 每趟排序后,将与分界元素相等的元素聚集在分界元素周围,这样可以避免极端数据(如序列中大部分元素都相等)带来的退化。

三路快速排序(英语:3-way Radix Quicksort)是快速排序和 基数排序 的混合。它的算法思想基于 荷兰国旗问题 的解法。

与原始的快速排序不同,三路快速排序在随机选取分界点 pivot 后,将待排数列划分为三个部分:小于 pivot、等于 pivot 以及大于 pivot。这样做即实现了将与分界元素相等的元素聚集在分界元素周围这一效果。

三路快速排序在处理含有多个重复值的数组时,效率远高于原始快速排序。其最佳时间复杂度为 O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// C++ Version
// 模板的T参数表示元素的类型,此类型需要定义小于(<)运算
template <typename T>
// arr 为需要被排序的数组,len 为数组长度
void quick_sort(T arr[], const int len) {
  if (len <= 1) return;
  // // 随机选择基准(pivot)
  // const T pivot = arr[rand() % len];
  // i:当前操作的元素
  // j:第一个等于 pivot 的元素
  // k:第一个大于 pivot 的元素
  int i = 0, j = 0, k = len;
  int pivot = arr[0];
  // 完成一趟三路快排,将序列分为:
  // 小于 pivot 的元素| 等于 pivot 的元素 | 大于 pivot 的元素
  while (i < k) {
    if (arr[i] < pivot)
      swap(arr[i++], arr[j++]);
    else if (pivot < arr[i])
      swap(arr[i], arr[--k]);
    else
      i++;
  }
  // 递归完成对于两个子序列的快速排序
  quick_sort(arr, j);
  quick_sort(arr + k, len - k);
}

线性寻找第 k 大的数

这里我们暂时定义“第 k 大的数”为序列排成升序时, 第 k 个位置上的数 (编号从 0 开始).

最简单的方法是先排序, 然后直接找到第 k 大的位置的元素. 这样做的时间复杂度是 $O(n\log{n})$, 对于这个问题来说很不划算. 我们完全可以用 O(n) 来解决.

考虑快排的工作过程. 当我们把 [l,r] 划分为 [l,p-1][p+1,r] 时, a[p][l,r] 中第 p 大的数, 也就是说当前区间确定出了比 a[p] 小的 p-l 个数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 模板的 T 参数表示元素的类型,此类型需要定义小于(<)运算
template <typename T>
// arr 为查找范围数组,rk 为需要查找的排名(从 0 开始),len 为数组长度
T find_kth_element(T arr[], int rk, const int len) {
  if (len <= 1) return arr[0];
  // // 随机选择基准(pivot)
  // const T pivot = arr[rand() % len];
  // i:当前操作的元素
  // j:第一个等于 pivot 的元素
  // k:第一个大于 pivot 的元素
  int i = 0, j = 0, k = len;
  int pivot = arr[0];
  // 完成一趟三路快排,将序列分为:
  // 小于 pivot 的元素 | 等于 pivot 的元素 | 大于 pivot 的元素
  while (i < k) {
    if (arr[i] < pivot)
      swap(arr[i++], arr[j++]);
    else if (pivot < arr[i])
      swap(arr[i], arr[--k]);
    else
      i++;
  }
  // 根据要找的排名与两条分界线的位置,去不同的区间递归查找第 k 大的数
  // 如果小于 pivot 的元素个数比k多,则第 k 大的元素一定是一个小于 pivot 的元素
  if (rk < j) return find_kth_element(arr, rk, j);
  // 否则,如果小于 pivot 和等于 pivot 的元素加起来也没有 k 多,
  // 则第 k 大的元素一定是一个大于 pivot 的元素
  else if (rk >= k)
    return find_kth_element(arr + k, rk - k, len - k);
  // 否则,pivot 就是第 k 大的元素
  return pivot;
}

Bubble Sort

Bubbles NEVER use bubble sort because it’s too SLOWWWWW!!!

但是 Bubble Sort 是一种稳定的排序算法!

1
2
3
4
5
6
7
8
void bubble_sort(int arr[], const int len) {
  for (int i = 0; i < len; i++) {
    for (int j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1])
        swap(arr[j], arr[j + 1]);
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
void bubble_sort(int arr[], const int len) {
  for (int i = 0; i < len; i++) {
    bool swapped = false;
    for (int j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
        swapped = true;
      }
    }
    if (!swapped) break;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 假设数组的大小是n+1,冒泡排序从数组下标1开始
void bubble_sort(int *a, int n) {
  bool flag = true;
  while (flag) {
    flag = false;
    for (int i = 1; i < n; ++i) {
      if (a[i] > a[i + 1]) {
        flag = true;
        int t = a[i];
        a[i] = a[i + 1];
        a[i + 1] = t;
      }
    }
  }
}

Selection Sort

1
2
3
4
5
6
7
8
9
10
void selection_sort(int arr[], const int len) {
  for (int i = 0; i < len; i++) {
    int min = i;
    for (int j = i + 1; j < len; j++) {
      if (arr[j] < arr[min])
        min = j;
    }
    swap(arr[i], arr[min]);
  }
}

Insertion Sort

1
2
3
4
5
6
7
8
9
void insertion_sort(int arr[], const int len) {
  for (int i = 1; i < len; i++) {
    int j = i;
    while (j > 0 && arr[j] < arr[j - 1]) {
      swap(arr[j], arr[j - 1]);
      j--;
    }
  }
}
This post is licensed under CC BY 4.0 by the author.