人有人的思维，计算机有计算机的思维，它们很不相同。如果你要问其中最大的不同是什么，那就是一种被称为递归（recursive）的逆向思维。相比之下，人的正向思维被称为递推（iterative）。要了解什么是递归，我们先了解什么是递推。

一、递推

递推是人本能的正向思维，比如我们在学习解方程时，先学习解一元方程，再学习解二元方程，之后才学解三元方程，最后推广到有任意未知数的方程，就是所谓的线性方程组，这种循序渐进、由易到难、由小到大、由局部到整体等正向思维方式就是递推。

如果用递推的方法计算一个整数的阶乘，比如5! = 12345，那么做法是从小到大一个个乘起来，如果算n!，那么要从1乘到n，使用递推计算n!的函数实现代码如下所示：

// algorithm\recursive.c

#include 

int factorial_iterative(int n)
{
    if(n < 0)
        return 0;
    
    int i, res = 1;
    
    for(i = 1; i <= n; i++)
        res *= i;
    
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

上面的代码逻辑符合我们从小到大、自底向上的递推思维方式，我们从来不觉得它有什么问题。事实上，我们在中学里学的数学归纳法就是递推方法的典型应用。

计算机思维正相反，它是自顶向下，从整体到局部的递归思维。什么是递归呢？直接解释概念很难讲清楚，下面以一个面试题为例来说明：

我们俩来做一个游戏，第一个人先从1和2中挑一个数字，第二个人可以在对方的基础上选择加1，或者加2。然后又轮到了第一个人，他可以再次选择加1，或者加2，之后把选择权交给对方。就这样双方交替地选择加1或者加2，谁要是正好加到20，谁就赢了。用什么策略可以保证一定能赢？

我们先简化上面的问题，把加到20改为加到10。按照递推思维，假如让你先选，你选2，我加2到4，你加1到5，我再加2到7，接下来你不论选加1到8还是加2到9，我都赢定了。再假如我先选，我选1，你选加2到3，我选加1到4，你选加2到6，我选加1到7，又回到第一次最后的状态，我还是赢定了。

可能你已经从上面的例子中想清楚这道题里面的技巧了，如果仅仅抢到10，情况并不复杂，你即使想不清楚它的道理，试几次也能找到规律，但是如果是抢20，情况就复杂多了，如果是抢30甚至50呢？就不能通过穷举法这种笨办法解决问题了，就必须找到它的规律。

可能你已经看出来了，要想抢到20，就需要抢到17，因为抢到了17，无论对方加1还是加2，你都可以加到20。而要想抢到17，就要抢到14，依此类推，就必须抢到11、8、5、2，因此对于这道题，只要第一个人抢到了2，他就赢定了。这里面的核心在于看清楚，无论对方选择1还是2，你都可以让第一轮两个人加起来的数值等于3，于是你就可以牢牢控制整个过程了。

这道看似是智力题的面试题是要考察候选人的什么技能呢？就是对计算机递归思想的理解。对于一般人，让他们数到20，他们会从小到大数，也就是正向的递推思维。但是这道题的解题思想正好相反，它是要寻找20，就要先寻找17，至于怎么从17到20，方法你是知道的，接下来要寻找17，就要寻找14，依此类推，这就是递归思想。

二、递归

上面这道面试题，可能有点过于简单，但是面试官其实还留有后手。比如他会问面试者，按照上述方法，从1开始加到20，一个有多少种不同的递加过程？

解这道题的技巧也在于使用递归，如果你从1、2、3开始找规律就难了。我们假定数到20有F(20)种不同的路径，那么到达20这个数字，前一步只有两个可能的情况，即从18直接蹦到20，或者从19数到20，由于这两种情况彼此是不同的，因此走到20的路径数量，其实就是走到18的路径数量，加上走到19的路径数量，也就是说F(20) = F(19) + F(18)，类似的，F(19) = F(18) + F(17)，这就是递推公式。

最后，F(1)只有一个可能性，就是F(1) = 1，F(2)有两个可能性，要么直接蹦到2，要么从1走到2，所以F(2) = 2。知道了F(1)和F(2)，就可以知道F(3)，然后再倒着推导回去，一直到F(20)即可。

数学比较好的朋友可能已经看出来了，这就是著名的斐波那契数列，如果我们认为F(0) 也等于1，那么这个数列就是这样的1(=F(0))、1、2、3、5、8、13、21…，这个数列几乎按照几何级数的速度递增，到了F(20)，就已经是10946了。

斐波那契数列其实反映出一个物种自然繁衍，或者一个组织自然发展过程中成员的变化规律。斐波那契数列最初是这样描述的：有一对兔子，它们生下了一对小兔子，前面的成为兔一代，后面的称为兔二代，然后这两代兔子各生出一对儿兔子，这样就有了第三代。这时第一代兔子老了，就生不了小兔子了，但是第二、第三代还能生，于是它们生出了第四代，然后它们不断繁衍下去，请问第N代兔子有多少对儿？

斐波那契数列增长有多快呢？我们假设F(n)表示数列中的第n个数，F(n+1)表示数列中的第n+1个数，我们用Rn = F(n+1)/F(n)表示数列增长的相对速率，简单计算下即可得知，Rn很快趋近于1.618，这恰好是黄金分割的比例。黄金分割比例是个神奇的数字，或许反映了宇宙自身的一个常数，比如自然界中的蜗牛壳、龙卷风、星系的形状都符合等角螺旋线，也被称为自然生长螺旋线，就是由黄金分割的几何相似性绘出的。

上面这个比率（Rn = 1.618）几乎也是一个企业扩张时能够接受的最高的员工数量增长速率，如果超过这个速率，企业的文化就很难维持了。企业在招入新员工时，通常要由一个老员工带一个新员工，缺了这个环节，企业的人一多就各自为战了。而当老员工带过两三个新员工后，他们会追求更高的职业发展道路，不会花太多时间继续带新人了，因此带新员工的人基本也就是职级中等偏下的人，这很像上面的兔子繁殖，只有那些已经性成熟而且还年轻的在生育。

上面那道面试题，将数到20的不同路径扩展到数到n的不同路径，实际上就是求斐波那契数列的第N个数，根据上面的递推公式可以扩展得到F(n) = F(n-1) + F(n-2)。有了递推公式，还需要递归边界，也即前面提到的F(0) = F(1) = 1。递推公式可以将求解F(n)的未知解自顶向下转换为求解F(n-1)与F(n-2)的未知解，直到达到递归边界的已知解，再通过递归边界的已知解自底向上递推（或回归），求得F(n)的已知解。

使用递归计算斐波那契数列第N个数的函数实现代码如下：

// algorithm\recursive.c

int fibonacci_recursive(int n)
{
    if(n < 0)
        return 0;
    else if(n == 0 || n == 1)
        return 1;
    else
        return (fibonacci_recursive(n-1) + fibonacci_recursive(n-2));
}
1
2
3
4
5
6
7
8
9
10
11

从上面的解题过程可以总结：递归就在于使用计算机自顶向下、从整体到局部的思维方式分析问题，找到把原问题自顶向下层层展开（或分解）的递推公式，通过不断重复使用递推公式，把原问题展开（或分解）到有已知解的递归边界处，再从递归边界的已知解，自底向上递推（或回归）求得原问题的解。

递归可以说是计算机科学的精髓，包含自顶向下和自底向上两个递推过程（可以把其中一个称为回归或回溯过程），递归的实现需要找到递推公式与递归边界两个部分：

• 递归边界：子问题展开或分解的尽头；
• 递推公式：将原问题分解为若干个子问题的方式。

为了更直观的了解递归过程，我们看下递归调用示意图，先从最开始简单的求n!为例，先给出使用递归方法求解n!的函数实现代码如下：

// algorithm\recursive.c

int factorial_recursive(int n)
{
    if(n < 0)
        return 0;
    else if(n == 0)
        return 1;
    else
        return n*factorial_recursive(n-1);
}
1
2
3
4
5
6
7
8
9
10
11

跟递推方式求解的函数代码相比更简洁些，以求解3！为例，给出递归求解阶乘的过程示意图如下：

从上图可以明显看出递归求解自顶向下与自底向上两个递推过程，这个过程有点类似于堆栈的后进先出结构。计算机实际执行递归时，确实使用了计算机的系统堆栈，由此可以看出，如果递归层级过深，就会导致系统堆栈不够用而出现错误。

我们再看斐波那契数列的递归求解过程，对此应该更有体会，以F(4)为例，斐波那契数列递归求解示意图如下：

由上图可以看出斐波那契数列求解的递归调用过程比阶乘求解的递归调用复杂得多，如果阶乘求解的递归调用复杂度为O(n)，斐波那契数列的递归调用复杂度就是O(2^n)，后者的递归调用复杂度呈指数增长，采用上面的函数实现方式只能求解比较小的斐波那契数列，比如前40项。

斐波那契数列递归求解为何会有这么大的复杂度呢？再仔细看其递归求解过程示意图，发现再递归求解过程中有大量的重复计算。要想提高算法的运行效率自然要让计算机尽可能少做事，现在计算机做了大量重复计算，效率自然大大降低。如何避免这种大量重复计算呢？

最简单的就是将中间计算结果保存起来，在下次使用时直接取用，不用再重新计算，比如在外部建一个数组专门用来保存中间结果，按这种方式实现的斐波那契数列递归求解函数代码如下：

// algorithm\recursive.c

#define MAXN    1000

int fibonacci[MAXN] = {0};

int fibonacci_recursive_memory(int n)
{
    if(n < 0)
        return 0;
    else if(n == 0 || n == 1)
        return 1;
    else if(fibonacci[n] != 0)
        return fibonacci[n];
    else
    {
        fibonacci[n] = fibonacci_recursive_memory(n-1) + fibonacci_recursive_memory(n-2);
        return fibonacci[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这种保存中间结果，避免重复计算的过程相当于让递归函数有了记忆功能，可以称为带记忆功能的递归，优化前后的斐波那契数列递归求解过程对比示意图如下：

从上图可以看出，通过采用保存中间结果，避免重复计算的优化，将斐波那契数列的递归求解调用复杂度从O(2^n)降低到了O(n)，相当于借助外部数组O(n)的空间将递归计算时间复杂度从指数级别降低到了线性级别，这是非常有效的以空间换时间的方法。保存中间结果避免重复计算的技巧也是计算这类重叠子问题的非常有效的方法。

三、递归设计—递推实现

递归的原理在计算机科学中更多的体现在逻辑的做事方法或解决问题的思维方式，在具体的实现上，如果直接采用递归的方法，逻辑简单，代码很短，非常简洁漂亮。但是，由于要不断的把中间状态放到堆栈中（压栈或入栈），然后再出来（弹出栈或出栈），占用空间较多，当递归层级很深时，可能会因系统栈空间不够用而出现错误。

因此，在具体实现时，很多情况是使用递归的原则设计，递推的原则实现，比如斐波那契数列求解第N个数的问题，采用递推方式的函数实现代码如下：

// algorithm\recursive.c

int fibonacci_iterative(int n)
{
    if(n < 0)
        return 0;

    int i, temp, res1 = 1, res2 = 1;
    for(i = 2; i <= n; i++)
    {
        temp = res1;
        res1 = res2;
        res2 += temp;
    }

    return res2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

递推的实现方式是自底向上，从递归边界出发，向上根据递推公式求得原问题的解，实际上相当于递归过程的后半部分，但省去了大量中间状态入栈与出栈的操作，节省了大量系统栈的空间占用。

3.1 尾递归

有些问题很难采用递推方式实现，或者我们既想省去对系统栈的大量占用，又想使用递归这种简洁漂亮的实现方式，有没有什么办法可以两者兼顾呢？

再回顾下前面介绍的通过外部数组保存中间结果，避免大量重复计算来提高算法效率的方法，中间结果既然可以保存在外部数组中，当然也可以保存在函数参数中。如果把递归调用过程的中间结果或中间状态保存在函数参数中，使其不依赖上一次的调用结果，当达到递归边界时，可以直接从参数中获得原问题的解，而省去了回归过程，这种省去回归过程的递归就获得了递推的优点。

如果要省去递归调用的回归过程，除了要将递归调用的中间结果或状态保存到函数参数中，还需要保证递归调用后面没有任何计算，也即递归调用只出现在函数末尾，而且函数末尾只返回递归函数本身，这种特殊的递归称为尾递归。

先看简单的n!求解，采用尾递归方式的函数实现代码：

// algorithm\recursive.c

int factorial_Tailrecursive(int n, int res)
{
    if(n < 0)
        return 0;
    else if(n == 0)
        return res;
    else
        return factorial_Tailrecursive(n-1, n*res);
}
1
2
3
4
5
6
7
8
9
10
11

仔细看尾递归调用的参数变化过程，也是符合递推思维的，递归调用被省去的回归求解过程实际上转移到递归函数的参数中了。从n!求解的递归边界：0！= 1可知，调用该函数时res初值传入1，比如求5！，函数调用格式为factorial_Tailrecursive(5, 1)。

再看斐波那契数列求解第N个数的问题，采用尾递归方式如何实现？由于斐波那契数列的递推公式中需要前面两级的解，所以该问题的尾递归函数需要两个参数分别保存前面两级的解。按照递推思维，尾调用的两个参数初值分别为递归边界F(0) =1与F(1) = 1，在参数中实现的递归公式则体现为前两级解的和，按照这种方式，采用尾递归方式求解该问题的函数实现代码如下：

// algorithm\recursive.c

int fibonacci_Tailrecursive(int n, int res1, int res2)
{
    if(n < 0)
        return 0;
    else if(n == 0)
        return res1;
    else if(n == 1)
        return res2;
    else
        return fibonacci_Tailrecursive(n-1, res2, res2 + res1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

需要注意的是尾递归调用本身并不能节省大量的系统栈开销，现在的编译器对C/C++都实现了尾递归优化（比如gcc / g++要开启尾递归优化需要设置优化等级-O2或-O3），由于尾递归调用已经把本层级计算得到的所有结果全部传给下一层级了，本层级无需再保存任何数据，编译器判断下一层级的尾递归调用不需要再去创建一个函数栈空间，可以直接复用当前的函数栈空间，把原先的数据覆盖即可，通过函数栈空间的复用，达到尾递归对栈空间的使用达到递推方式实现的效果。但是，编译器并没有对所有语言实现尾递归调用的优化，比如编译器对java、python这种更高级的语言就没有实现尾递归优化，没办法通过尾递归调用节省大量的系统栈空间占用。

四、递归应用示例

4.1 求解最大公约数

正整数a与b的最大公约数是指a与b的所有公约数中最大的那个公约数，一般用gcd(a, b)来表示。求解最大公约数最常使用的是辗转相除法（即欧几里得算法），该算法基于下面这个定理：

• 设a、b均为正整数，则gcd(a, b) = gcd(b, a%b)

证明：
设a = kb + r（a，b，k，r皆为正整数，且r 设d为a和b的一个公约数，即a和b都可以被d整除。而r = a - kb，两边同时除以d，r/d=a/d-kb/d=m，由等式右边可知m为整数，因此d也是b与r（也即a % b）的公约数。因此d既是a与b的公约数，也是b与a%b的公约数。由d的任意性，得a和b的公约数都是b和a%b的公约数。
设d为b和a%b的公约数，由于a = kb + r = kb + a%b，由于k是正整数，则d也是a和b的公约数，同样由d的任意性，得a和a%b的公约数都是a和b的公约数。
因此a和b的公约数与b和a%b的公约数全部相等，故其最大公约数也必然相等，得证。

上面这个定理可以直接作为递归算法的递推公式使用，有了递推公式，还需要找到递归边界，即数据规模减小到什么程度可以直接计算出结果。很简单，0和任意一个整数a的最大公约数都是a（也即gcd(a, 0) = a），这个结论可以作为递归边界。有了递推公式和递归边界，就可以编写出求解最大公约数的递归函数实现代码：

// algorithm\recursive.c

int gcd(int a, int b)
{
    if(b == 0)
        return a;
    else
        return gcd(b, a % b);
}
1
2
3
4
5
6
7
8
9

上面的递归函数以尾递归的形式实现，便于C/C++编译器优化。如果还要求解最小公倍数，则直接用a和b的乘积除以其最大公约数即可得到。

4.2 插入排序算法

排序算法可以算是基础算法中最常用的了，基础的排序算法主要有插入排序、冒泡排序、选择排序等（高级点的排序算法后面再介绍），这三种基础排序算法都是相邻元素比较，每个元素都需要跟其它N-1个元素进行比较，要完成N个元素分别跟其它N-1个元素的比较，需要的最坏与平均时间复杂度都是O(n²)（可以通过逆序数证明：通过交换相邻元素来完成排序的算法，其最坏与平均时间复杂度为O(n²)）。

虽然三种排序算法的时间复杂度一致，但在工程中插入排序算法平均消耗的时间最少，在小规模数据排序中，插入排序算法比另外两种排序算法更常用。比如在快速排序算法的优化中，当数据规模很小时（比如10个数以内），就可以使用插入排序算法代替快速排序算法节约时间。

插入排序算法是指，对序列A的n个元素A[0]–A[n-1]，令i从1到n-1枚举，进行n-1趟操作，假设某一趟，序列A的前k-1个元素A[0]–A[k-1]已经有序，而范围[k, n-1]还未有序，那么该趟从范围[0, k-1]中寻找某个位置i，使得将A[k]插入位置i后（此时A[i]–A[k-1]会后移一位至A[i+1]–A[k]），则范围[0, K]变得有序。下面给出一个动画展示该过程：

插入排序这种在序列A的前k-1个有序元素A[0]–A[k-1]中插入A[k]，使得序列A[0]–A[k]有序的操作很符合递推公式的特点，如果使用递归方法实现插入排序算法，这个过程就可以作为递推公式。有了递推公式，还需要递归边界，再回顾插入排序的过程，k从1开始不断递增，直到k = n-1，便实现了A[0]–A[n-1]有序的目的，也就完成了插入排序的过程，因此可以把k = n作为递归边界。

我们要以尾递归方式实现，还需要考虑使用哪些参数来保存递归调用某层的全部中间结果。在递归调用中，k从1开始逐渐递增到n-1，因此k需要作为一个参数，序列A的首地址和元素个数也需要作为参数传入，这三个参数就可以保存递归调用的全部中间结果了。

按照上面的分析，编写插入排序算法的尾递归实现代码如下：

// algorithm\sort.c

void insert_sort(int *data, int n, int k)
{
    if(data == NULL || k < 0 || k >= n)
        return;
    
    int i = k-1, temp = data[k];
    while (i >= 0 && data[i] > temp) {
        data[i+1] = data[i];
        i--;
    }
    data[i+1] = temp;

    insert_sort(data, n, k+1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

对于排序算法的原始无序数据，我采用了随机数生成，使用随机数生成n个无序数据的实现代码如下：

// algorithm\sort.c
#include 
#include 
#include 

#define MAX_COUNT      100000

int * data_init(int n)
{
    if(n < 1)
        return NULL;

    int *data = malloc(n * sizeof(int));
    if(data == NULL)
        return NULL;

    srand(time(NULL));

    for(int i = 0; i < n; i++)
        data[i] = rand();

    return data;
}

bool validate_data(int *data, int n)
{
    bool res = true;
    if(data == NULL || n < 1)
        res = false;

    for (int i = 1; i < n && res == true; i++) {
        if(data[i] < data[i - 1])
            res = false;
    }

    if(res == true)
        printf("\nThe data sequence has been ordered.\n\n");
    else
        printf("\nThe data sequence is unordered.\n\n");

    return res;
}

int main(void)
{
    int *data = data_init(MAX_COUNT);
    if(data == NULL)
        return -1;

    insert_sort(data, MAX_COUNT, 1);
  
    validate_data(data, MAX_COUNT);

    free(data);
    return 0;
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

插入排序为何比冒泡排序与选择排序速度更快呢？主要是因为插入排序算法更充分利用了序列中已存在的顺序信息，数据序列在部分有序时，插入排序可以减少比较次数，也即逆序数越少，插入排序越快。当数据序列接近有序，也即逆序数很少时，插入排序几乎是最快的排序算法（逆序数很少时，插入排序算法的时间复杂度接近O(N)）。

4.3 希尔排序算法

前面我们已经提到插入排序算法的时间复杂度为O(n²)，我们想对排序算法进行优化，以获得更高的计算效率。要想提高效率，就需要让计算机少做事情，放到排序算法中就是要减少数据之间的相互比较次数。

对于插入排序算法，每个待排序元素A[k]都要和前面的A[0]–A[k-1]个元素进行比较，效率自然较低。如果我们把序列A分为多组，每组分别排序后，再放到一起排序，就能减少数据之间的相互比较次数。举个例子，假如一个学校有20000名学生，如果直接相互比较排出名次，每个人都要和所有人去比较，效率自然比较低，如果我们将这20000名学生放到10个班级中，每个班级内先相互比较排出名次，再把这2万名学生放到一起，只跟各班级名次相近的学生相互比较即可，每个人需要比较的对手少了很多，效率自然比前面的方法高不少。

希尔排序和后面要介绍的归并排序、快速排序等都是基于上述逻辑，也即将序列A分解为多个小序列，对小序列分别排序，比直接进行大序列A的排序要节省不少时间。

希尔排序对序列A的分组是以增量序列（h1, h2, …, ht）的形式进行的，按增量序列个数k，对序列A进行k趟排序。比如选择增量hk，对应的一组增量序列就是A[i]、A[i + hk]、A[i + 2 * hk]…A[i + k * hk]（其中i + k * hk < n），对这组增量序列进行插入排序。在使用增量序列hk的一趟排序之后，对于每一个i，有A[i] <= A[i + hk]，所有相隔hk的元素都被排序。下面给出一个动画展示该过程：

对于希尔排序增量序列的选取，我们采用比较简单且常用的增量序列：ht = n / 2和hk = h(k+1) / 2，也即不断将序列增量除以2。这种增量序列并不是最好的，还存在一些更好的增量序列（比如Hibbard增量序列：hk = 2^k-1）能带来更高的计算效率，但比这种增量序列更复杂，这里主要介绍算法思想与原理，故选取最简单常用也是希尔推荐的增量序列实现希尔排序算法。

要以递归方式实现希尔排序算法，首先找到递推公式，按照增量序列中的某个增量hk，对被该增量分割出的多组小序列分别进行插入排序（比如增量hk分割出的多组小序列的首个元素分别为A[0], A[1],…, A[hk-1]）。使用增量hk完成排序后，选择增量序列中的下一个增量h(k+1)进行同样的排序操作，这个过程就可以作为递推公式。递归边界如何确定呢？增量序列的界限即是递归边界，对于我们选择的增量序列，不断除以2，最小增量为1，我们可以把增量1作为递归边界。

如果我们以尾递归形式实现希尔排序算法，还需要使用合适的参数保存递归调用过程的中间状态，对比前面介绍的插入排序，很容易想到增量hk要作为一个参数，序列A的首地址和元素个数也需要作为参数传入，这三个参数就可以保存递归调用过程的全部中间状态。

在实现希尔排序算法前，还需要对前面的插入排序算法进行修改，前面的插入排序算法默认增量为1，我们需要增加一个增量参数hk，以便对希尔排序中被增量hk分割出的多组小序列分别进行插入排序。修改后的插入排序算法如下：

void insert_sort(int *data, int n, int k, int step)
{
    if(data == NULL || k < 0 || k >= n || step < 1 || step >= n)
        return;
    
    int i = k - step, temp = data[k];
    while (i >= 0 && data[i] > temp) {
        data[i + step] = data[i];
        i -= step;
    }
    data[i + step] = temp; 

    insert_sort(data, n, k+ step, step);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

在此基础上实现的希尔排序代码如下：

// algorithm\sort.c
void shell_sort(int *data, int n, int step)
{
    if(data == NULL || step < 1 || step >= n)
        return;

    int i;
    for(i = 0; i < step; i++)
        insert_sort(data, n, i, step);
    
    shell_sort(data, n, step / 2);
}

int main(void)
{
    int *data = data_init(MAX_COUNT);
    if(data == NULL)
        return -1;

    shell_sort(data, MAX_COUNT, MAX_COUNT / 2);

    validate_data(data, MAX_COUNT);

    free(data);
    return 0;
}
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

为了便于比较插入排序与希尔排序的时间复杂度，我们使用C语言的一个函数clock()分别记录排序开始时间与结束时间，获得两种排序算法消耗的时间，在main函数中增加函数执行时间计算的代码如下：

// algorithm\sort.c
#include 
#include 
#include 

#define MAX_COUNT      100000

int main(void)
{
    int method;
    printf("insert sort: 1\n");
    printf("shell  sort: 2\n");
    printf("Select method: ");
    scanf("%d", &method);

    int *data = data_init(MAX_COUNT);
    if(data == NULL)
        return -1;

    clock_t start = clock();
    switch (method)
    {
    case 1:
        insert_sort(data, MAX_COUNT, 1, 1);
        break;

    case 2:
        shell_sort(data, MAX_COUNT, MAX_COUNT / 2);
        break;
    
    default:
        break;
    }
    clock_t end = clock();
    double time = (double)(end - start) / (CLOCKS_PER_SEC / 1000);

    validate_data(data, MAX_COUNT);
    printf("execution time: %.3lf ms.\n", time);

    free(data);
    return 0;
}
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
33
34
35
36
37
38
39
40
41
42

使用插入排序和希尔排序分别对100000个随机数进行排序，执行时间分别如下：

从上面的结果可以看出，希尔排序比插入排序的效率高了很多，还是挺明显的。希尔排序的时间复杂度根据选取增量序列的不同而不同，对于我们选择的增量序列，其时间复杂度也是O(n²)。对于Hibbard增量序列，其时间复杂度为O(n^(3/2))，由此也可以看出，通过增量序列将原序列进行分组，让序列元素执行远距离交换，可以让排序算法的平均时间复杂度低于O(n²)。

对于我们选择的增量序列，虽然希尔排序与插入排序的时间复杂度都是O(n²)，但衡量时间复杂度一般省略了常数，主要是看计算时间随数据量增大的相对增长速率。在工程应用中，对相同数据量的计算，虽然两种算法的时间复杂度一致，但可能一种算法的工程时间复杂度是O(k * n²)，另一种算法的工程时间复杂度是O( n² / t)，其中t与m均为大于1的常数，那么这两种算法在工程应用中，后者的效率是前者的 k * t 倍，希尔排序与插入排序就类似这种情况。

本章算法实现源码下载地址：https://github.com/StreamAI/ADT-and-Algorithm-in-C/tree/master/algorithm

本章使用的代码编辑器为VS Code，编译器为gcc，VS Code插件为Code Runner，该插件的配置界面如下（此插件默认调用gcc / g++并没有设置优化选项，所以不能对尾递归进行优化，可以通过手动输入gcc / g++编译命令开启-O2或-O3优化，以便编译器对尾递归的函数栈使用进行优化）：

更多文章：

• 《Data Structures and Algorithm analysis Sample Source Code》
• 《数据结构与算法分析（四）— 时间与空间复杂度》
• 《数据结构与算法分析（六）— 分治与减治 + 分治排序与二分查找》