撰写了文章发布于 2020-02-20 14:12:44

《程序编写编程入门 - 算法》排序（一）

本系列收藏夹
 爱发电！

算法

何为算法？举个简单的例子，输入一个数n，计算从1加到n的结果。你已经学会使用循环了，加加看如何？
而另一方面，不知道你是否听过一个口诀，首数加尾数乘以个数除以二。
这就是算法

当你学会了编程这一基础工具，知道了文档如何阅读，你的编程生涯才刚刚开始。

OJ

OJ，在线判题系统，对于编程中各种技巧，人们将其写成试题拥有和代码测试一样的题目-答案对，并依据内存占用/执行时间/结果正确成都来对每个人的算法进行评判。
同时，也是一种非常非常迅速的提升自身编程水平的方法。

如果你希望精进自己的编程水平，你一定需要进入这些网站，翻阅并尝试其中的试题，看题解并理解其中的想法，并将其为自己所用。
磨刀不误砍柴功。

排序

你已经学会了数组，还记得数组的增加/删除/修改等基本操作吗？
想象一副扑克牌(或者直接拿一副扑克牌出来) 拿取其中的三分之一，不用很精确，这一般是你斗地主的基础手牌

设计一个程序，使其可以对一个有20个元素的数组其值的范围为 1 - 13进行从小到大的排序

你的排序函数形式参数可以是 void sort(int a[]); 或 void sort(int *a)，并在函数内部像正常数组那样使用它们，对其数据的操作也会反映到函数外部的传入变量。
你可以使用如下代码进行判断

for(int j=0; j<19; j++){
    assert(a[j] <= a[j+1]);
}

需要注意我们使用到了j+1，因此我们只循环18 我提供了几个数组以供测试

{5,11,6,6,6,11,13,2,6,5,4,9,10,7,12,3,10,3,11,1}
{9,3,11,7,4,5,1,6,2,10,10,6,10,4,10,4,10,7,6,11}

当然，你也可以使用程序产生的随机数。

看着你手中或者脑子里的扑克牌，想象自己是如何移动每张牌的，找一个笨方法但可以不断循环来排序，并将这种过程用程序语言描述出来。

修改程序和测试代码，这是5000个随机数，将其排序（出于篇幅限制）打开 https://c.runoob.com/compile/13

#!/usr/bin/ruby
# -*- coding: UTF-8 -*-

5000.times do
    print("#{rand(10000)},")
end

输入到代码窗格，并点击“点击运行”，会生成5000个 0-9999范围随机数，不过其最后会多一个逗号，注意删除。大部分电脑生成如此大量随机数会导致相当程度的卡顿

使用你的函数来排序这个数组

时间复杂度

你会发现，当排序数量更多的时候，你的电脑程序执行会有一个明显的卡顿。如果你使用的是vs，在排序函数调用所在行下断点，并执行一次步过（逐过程），你有右侧【诊断工具】的事件，会告诉你你的电脑花费了多少时间去处理这个排序操作
另外，你在windows系统中还可以使用如下代码来打印执行前后的系统时间，

#include <cstdio>
#include <Windows.h>

void main(){
    int a[5000]={你的随机数}
    printf("%lu\n", GetTickCount());
    sort(a); //你的排序函数
    printf("%lu\n", GetTickCount());
}

或者你可以使用time头文件提供的计时工具，我们将在后文中展示

GitTickCount是由系统统计，你电脑开机至今的毫秒数，精确到18ms
就算对于同一电脑，在程序运行时也会因为你系统所处的环境而不同。因此，为了量化这种时间，就有了一种概念称作“时间复杂度”

时间复杂度实际上是一种数字上的概念，其最终描述的是你程序的数据量与运算时间的对应关系，其用、O()来表示

O(1)是最简单的一个时间复杂度，不论有多少数据，你的程序段运行时间不会变长，例如解决1加到n的问题时，你采用首数加尾数乘以个数除以二的算法

O(n)则表示，当你有n个数据，你会花费n倍与某个值的时间，例如你设计了一个循环n次的循环，那么其内容就会重复执行n次，其所花费的时间就是n倍的执行一次时间，即为O(n)

O(n^2) 当你有n个数据，你需要花费n^2(n平方）个时间，例如你在一个n次的循环中放置了另一个n次的循环，同理，多重嵌套则继续增加平方数

O(2n) 你使用了两个连续的循环，其都为n，那么其统计为2n同理递增

O(logn) 这里log是以2为底的，在递归或者二分算法中，这种算法每执行一次操作，会处理完成剩下数据中的一半，即数据越多，其对时间影响增加的越小

空间复杂度

在一个算法拥有时间复杂度的同时，还拥有空间复杂度，但其更为不常用，简单来讲就是程序占用了多少内存，其基本上是 O(1)和O(n)，例如数组，由于我们总是要预先分配好数组的长度，所以数组总是O(1)，而一些动态申请内存的机制，则通常是O(n)。

递归

你或许没听过这个词，递归是通过函数对其本身的调用来实现的一种编程技巧，他的形式是这样的。

int foo(){
    return foo();
}

你或许奇怪，既然如此设计，不就成为了死循环么。于是类比循环我们需要关注循环范围和条件更新，递归我们则需要关注他的结束条件和参数更新。
一个遍历 0 - 100 的递归看起来像这样

int foo(int a){
    if(a == 100) return 0; 
    //结束条件：当 a==100的时候不再进行更深入的调用

    return foo(a-1);
    //每次a-1后传入下一层递归
}

你可以发现，在绝大多数情况下，递归是可以与循环互换的，对于循环条件过于复杂，用递归执行可以极大的增加程序可读性。
而由于递归本身使用的是函数调用，其会占用程序栈区，因此不宜递归层次过深。
分析一个递归的方法，则是可以将其在调用处打开。

对于学习算法，我十分推荐《算法》
https://www.ituring.com.cn/book/875
其详细的讲述了各种常用算法，其原理及其实现方式，虽然其使用java语言作为样例，但其对算法本身讲解十分透彻，未来如果有机会，我会在后续《算法》系列文章中更新基于此书的各种经典算法讲解。

当然，对于编程的使用者，已经有超级多的成品代码库提供了相当多的优秀算法代码，你只需要对这些库进行利用就可以了

排序算法

在我们了解了时间复杂度这个概念之后，我们就要正式学习排序算法了。针对一个排序算法，我们需要关注算法如下几个特性

稳定： ab相等，在原数据中，a在b前面，排序以后a还在b前面则稳定（否则不稳定）
内排序：在内存中排序称为内排序（否则为外排序）
时间复杂度：对于一个大致有序或完全混乱或完全相反的表进行排序的时间显然是不同的，对于排序算法则有最好状况、平均状况、最坏状况三种情况下的时间复杂度

数组基本操作

现在开始回到代码中，新建一个项目，把前文中的时间计算和断言写入其中

#include <cstdio>
#include <cassert>
#include <ctime>

int main(){
  clock_t s, f;
  char a[100] = {随机数};
  //这里请使用

  s = clock();

  f = clock();

  printf("%d tick\n", (f-s));
  for(int i=0; i<99; i++) assert(a[i] <= a[i+1]);
}

如果你直接运行，他会显示你运行了 0 tick时间，这是正常的，我们后续需要在s和f之间加入我们的排序算法。
这里的tick是指CPU时钟周期，来作为我们对算法运行时间的统一衡量标准。
另外一方面，如果你使用了更古老的电脑（比如我的三星N220笔记本电脑）这并不一定是0，这是正常的。

然后我们撰写数组的基本操作，就目前来讲，我们并不清楚我们需要什么样的操作，这不是一个好的开头，但为了让后续的内容更连贯，总而言之我们先编写插入与交换。

向前插入：对于a > b，我们把下标为a的元素插入到b位置，并把二者中间的元素向后移。
向后插入：对于a < b, 我们把下标为a的元素插入到b位置，并把二者中间的元素前。
交换：对于 a, b 我们把数组中 ab两个元素互换。

对于向后插入

int temp = arr[a];
for( int i = a; i != b; i++){
    arr[i] = arr[i+1];
}
arr[b] = temp;

对于向前插入

int temp = arr[a];
for(int i = a; i != b; i--){
    arr[i] = arr[i-1];
}
arr[b] = temp;

这两段程序是非常相似的，如果你已经自己写出来两个插入，我们完全可以把他们合并成一个：

void insert(int arr[], int from, int to){
  int add = 1, temp = arr[from];
  if (from > to) add = -1;
  for(int i = from; i != to; i += add){
    arr[i] = arr[i + add];
  }
  arr[to] = temp;
}

同样我们撰写交换函数

void swap(int arr[], int from, int to){
  int temp;
  temp = arr[from];
  arr[from] = arr[to];
  arr[to] = temp;
}

在写完这些基本的代码之后，你会发现，对于同样的两个数，其插入要比交换耗费更长时间。也因此，我们几乎不会用到刚写好的插入函数。

在开始第一个算法之前，我会用 = 号表示两个数字比对，o 表示两个数字交换，| 表示排序执行的范围， v 表示已排序范围, x表示待排序范围， t 表示临时变量， ^表示插入

冒泡排序（Bubble Sort）

你见到的第一个排序算法，他实际上就像是一个泡泡往上冒，我们拿自小到大排序来举例

比较两个元素，如果前者比较大则交换两个
不断进行比较，直到最后一个元素，此时最大的一个元素被冒到最后
重复前两步，但不比较最后一个
直到完成所有步骤

5 2 4 1 3
|       |
= =
o o
2 5 4 1 3
  = =
  o o
2 4 5 1 3
    = =
    o o
2 4 1 5 3
      = =
    o o
2 4 1 3 5
|     |
= =
2 4 1 3 5
  = =
  o o
2 1 4 3 5
    = =
    o o
2 1 3 4 5
|   |
= =
o o
1 2 3 4 5
  = =
| |
= =
排序完成

根据这种思路，我们撰写程序，并尝试运行。（动手试试？）

void bubble_sort(int arr[], int size){
  size -= 1;//我们传入的是数组大小，还记得吗？数组是从0开始的，你可以把这句写进for循环中 i = size - 1
  for(int i=size; i; i--)  
  //我们的范围是逐个递减的，因此我使用循环i来处理这种递减，作为排序范围的上限
    for(int j=0; j<i; j++)
      //从0到上限-1，其与其后一个数会进行判断
      if(arr[j] > arr[j+1]) swap(arr, j, j+1);
}

这个程序在我的古董电脑上执行了 469590 个tick，冒泡的平均时间复杂度是 O(N^2)，但其实际操作所花费时间远远超过其他O(N^2)的算法，因此也被称作排序界的耻辱, 是一种稳定算法。其唯一的优点就是算法简单，你甚至可以在一行内写完他，但其时间较长且交换次数较多，每一次冒泡都可能经历数次交换。
如果你对其进行优化，例如在if中加入计数，如果一趟之中没有发生任何交换，就宣布排序成功，这在数据大致有序的情况下非常有用。

选择排序（Selection Sort）

第二种十分简单的算法，选择排序，这是一种不稳定算法（大小相等的两个数顺序可能会改变）其步骤如下：

遍历数组，找到最小值的位置
将最小值与第一个交换
排除第一个数据，标记其为已排序，对后续内容重复执行1-2步，直到排序完成

5 2 4 1 3 t
|       |
= = = = = 3
o     o
1 2 4 5 3
v |     |
  = = = = 1
v v |   | 
    = = = 4 
    o   o
1 2 3 5 4
v   v | |
      = = 4
      o o
1 2 3 4 5
排序完成

void selection_sort(int arr[], int size){
  int min;
  for(int i=0; i < size; i++){ //i从0开始循环，逐渐递增
    min = i;
    for(int j=i; j < size; j++){
      if(arr[min] > arr[j]) min = j;
    }
    swap(arr, i, min);
  }
}

相比于冒泡排序，选择排序在我的电脑上仅仅执行了200545个tick ，这主要是由于在选择排序中，数据交换的次数执行相当的少，尤其是当待排序数据储存在硬盘之中时，选择排序的速度相比于其他大多数算法会有很明显的优势。
其缺点在于时间过于固定，也因此其平均速度、最大、最小速度皆为 O(N^2),但我们依然可以通过例如在寻找最小值时同时寻找最大值，使得排序范围从两个方向向中间收缩，来减少读取次数来进一步提升执行速度。

插入排序（Insertion Sort）

插入排序同样是一种非常简明易懂的排序方法，是稳定排序算法其步骤如下：

将最开始的数字标记为已排序
把未排序的第一个数字插入到已排序区域中合适的位置
对未排序区域重复执行1-2步直到完成

 5 2 4 1 3
 v |     |
 = =
^  ^
 2 5 4 1 3
 v v |   |
 = = =
  ^  ^
 2 4 5 1 3
 v   v | |
 = = = =
^      ^
 1 2 4 5 3
 v     v |
   = = = =
    ^    ^
 1 2 3 4 5
 排序完成

void insertion_sort(int arr[], int size){
  int i, j;
  for(i=1; i < size; i++){
    j = i;
    while(j){
        j--;
      if(arr[i] >= arr[j]) {j+=1; break;}
    }
    insert(arr, i, j);
  }
}

执行经过了195985个tick，插入排序是稳定排序，其最优解为O(N)，而平均时间为O(N^2)，虽然我们通过插入函数，使得执行时间减少了一半，但当我们学习了链式表后，这种状况会大大改善。

希尔排序（Shell Sort）

写到这里，文章已经十分冗长，但我们还有一个算法需要讲解，希尔排序是属于初级排序算法，是不稳定排序算法，同时是一种快速排序算法。也是历史上第一个突破O(N^2)时间的算法，这使得其被广泛使用在各种代码之中。

希尔排序的平均时间是 O(N^1.3)，这是一个很大的进步。在很多情况下，如果一个很小的数字，却排在待排数组的末端，那么这个数字需要进行“一个长距离的旅行”才能到达数组前端，也就是其本应该在的位置。
为了解决这种现象，我们采用以下方案进行排序：

设一个数 x，让数组中每间隔x取出一个数字（请注意，这是逻辑上的取出，存储的位置并没有变）
把这些数字看作一个新的数组，并对其执行插入排序。
重复这个过程，直到所有数字完成一遍排序
降低这个数字x，重复执行1-3步，直到x = 1

4 3 6 5 2 1 8 7
x     x     x    第一遍排序，x = 3
4     5     8
  x     x     x
  2     3     7  
    x     x      第一遍排序完成
    1     6
4 2 1 5 3 6 8 7
x   x   x   x   第二遍排序， x = 2
1   3   4   8
  x   x   x   x
  2   5   6   7
1 2 3 5 4 6 8 7 
|             | 第三遍排序， x = 1 
1 2 3 4 5 6 7 8

这个x的序列，被称作递增序列，而如何选择这个递增序列，是该算法研究的重点。在历史上有诸多理论研究，用以在某些极端状况下使得希尔排序的速度变快，但这也仅限于理论研究，程序员们在如何选择这个递增序列这件事上，更多情况下是依据习惯和经验。

void shell_insert(int arr[], int from, int to, int step) {
    //由于实际上我们只需要向前插入，所以不做方向判断
    int temp = arr[from];
    if (from == to) return;
    for (int i = from; i > to; i -= step) {
        arr[i] = arr[i - step];
    }
    arr[to] = temp;
}

void shell_one_step(int arr[], int from, int step) {
    int i = from;
    //对from下标的元素，向前进行一次插入排序操作，插入间隔是step
    while (i >= step){
        i -= step;
        if (arr[from] >= arr[i]) { i += step; break; }
    }
    shell_insert(arr, from, i, step);
}
void shell_sort(int arr[], int size) {
    int x[7] = { 1, 4, 13, 40, 121, 367, 1102};
    for (int i = 7; i--;) { //对“递增序列”进行循环
        for (int j = x[i]; j < size; j++) {
            //与示例不同，同一个间隔下的不同分组实际上是交替进行的
            shell_one_step(arr, j, x[i]);
        }
    }
}

//作为对比，我同样编写了一模一样，但间隔只为1的标准插入排序
void insert_sort(int arr[], int size) {
    int x[7] = { 1, 4, 13, 40, 121, 367, 1102};
    for (int i = 1; i--;) {
        for (int j = x[i]; j < size; j++) {
            shell_one_step(arr, j, x[i]);
        }
    }
}

在执行代码后，对同样的数组，希尔排序执行了6654个tick，而插入排序执行了194400个tick，如你所见，希尔排序的执行时间远远低于插入排序，因此在一个并不大的数组进行排序的时候，希尔排序以其可以接受的排序时间，和其精简的代码而被广泛使用。（这里为了展示各种细节，将希尔排序拆分成了三个函数，实际使用中并不需要如此麻烦）

你或许在网上看过一些展示排序算法不同点的视频，例如
https://www.bilibili.com/video/av1039639
他们大多数来自于这个网站
https://panthema.net/2013/sound-of-sorting/
你可以从其上面下载到相应的软件来看看不同的排序有区别。

著作权归作者所有。禁止以任何形式转载、演绎或修改，如有需要请先联系作者获得授权。

{{article_voters_count}}人赞同

...