IceSandwich

排序（二）

描述排序算法原理

算法
字数统计: 2.1k阅读时长: 9 min
2019/01/20 Share

上篇我们探讨了几种O(N2)（冒泡排序、选择排序、插入排序）和O(N1.25)（希尔排序）的排序算法，但是面对巨量的数据面前它们又是低效率的，因此，这节将探讨高等排序算法。

上篇    算法：排序（一）

 

计数排序/桶排序

==Update 2020/07/14：此处计数排序/桶排序实现不具有实用性，具体请看最新的排序文章：线性时间排序==

计数排序/桶排序真的很简单，很暴力，很快速，很。。。占内存。~~

允许我盗用一下别人的图来说明这个排序思想。图来自《啊哈！算法》

如上，将数据放入一个数组里，可以起到统计数字数量的作用（计数排序），也可以起到排序的作用（桶排序），其实这玩意我经常用来去重。。。

这个排序算法能达到O(N)级别，肥肠快～相比于O(N2)算法，处理1000个数据时快1000倍！

只是，真的很占内存，如果要1E9的数据，你还会用桶排序吗？而且，你还需要数据最大不超过哪个数字才行。

1
2
3
4
5
6
7
8
9
10
#include "SortUtils.hpp"

void Sort(int a[], int n) {
    int bucket[100] = { 0 }; //数据里最大不超过100
    for (int i = 0; i < n; ++i) //将数据放入桶里
        bucket[a[i]] = 1;
    for (int i = 0, j = 0; j < 100; j++) //遍历所有的桶，找出非空的桶
        if (bucket[j] == 1)
            a[i++] = j;
}

结果：

1
2
3
4
5
6
7
8
Source Array: 33 61 12 89 23 5 17 1 99 36 48
Sorted Array: 1 5 12 17 23 33 36 48 61 89 99
| Check Sorted: yes
| Array Length: 11
|   Swap times: 0
|Compare times: 0
| Run time(μs): 1 μs
| Run time(ms): 0.001 ms

 

归并排序

归并排序跟其他排序不同，其他排序是改变原来数组的内容，归并排序只能新建一个数组将排序后的数字放进去，具体思想如下：（图自这里）

归并排序

先将数组分成两部分，直到剩下一个数字，然后按序合并。合并有序序列需要一定的技巧，不能单纯地将两个数组首尾相接。

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
#include "SortUtils.hpp"
#include <memory.h>

//合并有序数组a和b
int* Conquer(int* a, int an, int* b, int bn) {
    int *res = new int[an+bn]; //新建一个an+bn长度的数组
    for (int ia = 0, ib = 0, ir = 0; ir < an+bn; ++ir)
        if (ib == bn || (ia != an && a[ia] < b[ib])) res[ir] = a[ia++];
        else if (ia == an || (ib != bn && b[ib] < a[ia])) res[ir] = b[ib++];
        //其实第二个ib!=bn不用的，因为第一个条件ib==bn已经确保了ib不等于bn了，这样写为了美观。。。
    delete[] a; delete[] b; //及时删除之前分配的数组
    return res;
}

//分解数组然后合并
int* Devide(int a[], int n) {
    if (n == 1) return a;
    int mid = n/2;
    int *xleft = new int[mid], *xright = new int[n-mid]; //分成左右两部分
    memcpy(xleft, a, sizeof(int)*mid); memcpy(xright, a+mid, sizeof(int)*(n-mid));
    return Conquer(Devide(xleft, mid), mid, Devide(xright, n-mid), n-mid);
}

void Sort(int a[], int n) {
    int *cpy = Devide(a, n); //返回的是一个排序后的数组，原数组没有被修改
    memcpy(a, cpy, sizeof(int)*n); //因而需要复制排序后的数组到原数组
    delete[] cpy; //然后删除排序后的数组，因为这个是动态分配的
}

你也可以不用新建一块空间存储新的数据，不过还是需要有个临时的位置存放原数据，如果这样的话可能跟高效，毕竟没有涉及大量的数组创建和删除操作。而且这样不需要考虑分的操作了，因为分的结果就是每个数字取出来的结果嘛（如上图绿线一行）。

效果还是很高效的：（swap的确用不上，compare就很难获取了所以。。。这两个值为0）

1
2
3
4
5
6
| Check Sorted: yes
| Array Length: 1000
|   Swap times: 0
|Compare times: 0
| Run time(μs): 659 μs
| Run time(ms): 0.659 ms

 

分割

分割不是排序的一种，但是理解它有助于理解下面的快速排序。分割很简单，选定一个数，通过算法，使得这个数左边都小于这个数，这个数右边都大于这个数，注意左右两边不一定有序，只需满足大小关系即可。

这里有大量很详细地说明分割的过程。需要图来解释一切的同学点进去吧←_←

在开始写代码之前，由于我们的SortUtils.hpp是适合于排序的，而分割不是排序，因而需要修改一点东西，比如修改Check函数，其他都是修改输出的字而已。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#ifdef PARTITION
    extern int splitMid;
    bool Check(int n) {
        //左边小于mid位置的数字，右边大于mid位置的数字
        for (int i = 0; i < splitMid; ++i) 
            if (__nums[i] > __nums[splitMid]) 
                return false;
        for (int i = splitMid+1; i < n; ++i) 
            if (__nums[i] < __nums[splitMid]) 
                return false;
        return true;
    }
#else
    bool Check(int n) {
        for (int i = 0; i < n-2; ++i)
            if (__nums[i] > __nums[i+1])
                return false;
        return true;
    }
#endif

我们统一选最后一个数为分割的标准：

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
#define PARTITION
#include "SortUtils.hpp"
int splitMid;
#define PARTITION_TYPE 1
//由于分割不对左右两边的顺序做要求，分割的结果有很多种，这里我提供两种方法。

void Sort(int a[], int n) {
    splitMid = n-1; //选最后一个作为分割的标准

    #if PARTITION_TYPE == 1 //灵感来自《挑战程序设计竞赛》
        int i, j; //0~i为小于等于splitMid的数，i~j为大于splitMid的数，j~n为未处理的数
        for (i = j = -1; j < n-1; ++j)
            if (CompareTo(j+1, splitMid) <= 0)
                Swap(j+1, ++i);
        splitMid = i;
    #elif PARTITION_TYPE == 2 //灵感来自《啊哈！算法》
        int i = 0, j = n-2;
        while (i < j) {
            while (i < j && CompareTo(i, splitMid) < 0) ++i;
            while (j > i && CompareTo(j, splitMid) > 0) --j;
            if (i != j)
                Swap(i++, j--);
        }
        if (CompareTo(i, splitMid) > 0 || CompareTo(++i, splitMid) > 0) {
            Swap(i, splitMid);
            splitMid = i;
        }
    #endif
}

结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#类型1
Source Array: 33 61 12 89 23 5 17 1 99 36 48
 Split Array: 33 12 23 5 17 1 36 [48] 99 61 89
|Check Splited: yes
| Array Length: 11
|   Swap times: 8
|Compare times: 11
| Run time(μs): 2 μs
| Run time(ms): 0.002 ms
#类型2
Source Array: 33 61 12 89 23 5 17 1 99 36 48
 Split Array: 33 36 12 1 23 5 17 [48] 99 61 89
|Check Splited: yes
| Array Length: 11
|   Swap times: 3
|Compare times: 11
| Run time(μs): 2 μs
| Run time(ms): 0.002 ms

 

快速排序

还记得当年的希尔排序吗？希尔排序就是利用插入排序的优点改进的，快速排序其实是利用分割的优点改进的。分割的复杂度是O(N)，非常高效，因此可以进行利用。

其实。。。网上大部分关于快速排序的都是在说分割，很少真正关于快速排序本身的，反正我找不到。。。所以，不给你们放图了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include "SortUtils.hpp"

int Partition(int a[], int s, int e) { //分割
    int splitMid = e-1, i, j;
    for (i = j = s-1; j < e-1; ++j)
        if (CompareTo(j+1, splitMid) <= 0)
            Swap(++i, j+1);
    return i; //返回轴
}

void QuickSort(int a[], int s, int e) {
    if (e-s <= 1) return;
    int mid = Partition(a, s, e);
    QuickSort(a, s, mid);
    QuickSort(a, mid+1, e);
}

void Sort(int a[], int n) {
    QuickSort(a, 0, n);
}

如你所见，快速排序采用了分治的思想，利用递归的方法完成排序。然后结果如下：

1
2
3
4
5
6
7
8
Source Array: 33 61 12 89 23 5 17 1 99 36 48
Sorted Array: 1 5 12 17 23 33 36 48 61 89 99
| Check Sorted: yes
| Array Length: 11
|   Swap times: 27
|Compare times: 38
| Run time(μs): 5 μs
| Run time(ms): 0.005 ms

 

性能

1000条数据已经无法显示算法的优越性了，于是，我生成了1E5个整数进行测试。

首先是希尔排序：

1
2
3
4
5
6
| Check Sorted: yes
| Array Length: 100000
|   Swap times: 2073536
|Compare times: 3179386
| Run time(μs): 36751 μs
| Run time(ms): 36.751 ms

之后是归并排序：

1
2
3
4
5
6
| Check Sorted: yes
| Array Length: 100000
|   Swap times: 0
|Compare times: 0
| Run time(μs): 23038 μs
| Run time(ms): 23.038 ms

最后是快速排序：

1
2
3
4
5
6
| Check Sorted: yes
| Array Length: 100000
|   Swap times: 1019079
|Compare times: 1995044
| Run time(μs): 25031 μs
| Run time(ms): 25.031 ms

可以看到，快速排序不总是那么快的哦～要根据情况选择适合的排序方式才是坠重要滴！

这里有python版本的排序算法解释，写的和配的图都很好～

最后引用一张图，结束排序算法的探讨。另外纠正下，最好时间应该用小欧o表示的，最差时间用大欧O表示。。。反正没所谓啦！～这不是重点。。。

原文作者：IceSandwich

原文链接：https://icesandwich.github.io/2019/01/20/%E6%8E%92%E5%BA%8F%E4%BA%8C/

发表日期：January 20th 2019, 12:00:00 am

更新日期：July 14th 2020, 7:39:32 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 计数排序/桶排序
  2. 2. 归并排序
  3. 3. 分割
  4. 4. 快速排序
  5. 5. 性能
Total : 21
2021
2020
2019
c docker 算法 GTK 三维重建 KinectFusion 稠密重建 MSSQL html gtk opencv cuda BundleFusion 油猴脚本 js esp8266 arduino python torch Premiere FFmpeg 渗透
算法原理 docker GTK 三维重建 gtk BundleFusion 算法 脚本 硬件 研究 FFMPEG 渗透