【算法基础】由插入排序来看如何分析和设计算法

插入排序及其解决思路

算法的作用自然不用多说，无论是在校学生，还是已经工作多年，只要想在计算机这条道路走得更远，算法都是必不可少的。

就像编程语言中的“Hello World！”程序一般，学习算法一开始学的便是排序算法。排序问题在日常生活中也是很常见的，说得专业点：

输入是：n个数的一个序列$<a_1,a_2,...,a_{n-1},a_n>$
输出是：这n个数的一个全新的序列$<a_1^,,a_2^,,...,a_{n-1}^,,a_n^,>$，其特征是$a_1^, \leq a_2^, \leq ... \leq a_{n-1}^, \leq a_n^,$

举个例子，在本科阶段学校往往要求做的实验中大多是“学生管理系统”、“信息管理系统”、“图书管理系统”这些。就比如“学生管理系统”中的分数，每当往里面添加一个新的分数时，便会和其他的进行比较从而得到由高到低或由低到高的排序。

我本人是不太喜欢做这种管理系统的…… 再举个比较有意思的例子。

大家肯定都玩过扑克牌，撇开部分人不说，相信大部分童鞋都热衷于将牌按序号排好。那么这其中就蕴含着算法的思想：

1）手中的扑克牌有2种可能：没有扑克牌（为空）或者有扑克牌且已排好序。
2）从桌上抓起一张牌后，从左往右（从右往左）依次进行比较，最终选择一个合适的位置插入。

简单的说，插入排序的精髓在于“逐个比较”。

在列出代码之前，先来看看下面的第一张图，我画的不是太好，就是有没有经过排序的 “8，7，4，2，3，9”几个数字，根据上面的描述，将排序过程描述为：

1）将第二个数字“7”和“8”比较，发现7更小，于是将“8”赋值到“7”所在的位置，然后将7赋值给“8”所在的位置。
2）将”4“移到”7“所在的位置，”7“和”8“后移一位。
3）同样的步骤，将”2“和”3“移到”4“的前面。
4）”9“比前面的数字都大，故不移动。

仅仅是这样的描述还是不够的，我们需要更加专业一点。

1）设置一个循环，从第二个数字开始（索引为1）不断与前面的数字相比。
2）每次循环开始时作为比较的数的索引为j，设置temp为其值。（因为在前面也看到了，将”8“赋值到”7“的位置时，如果不将”7“保存起来，那么便丢失了这个数字。）
3）取得j的前一位i。
4）只要i仍在数组中，并且索引为i处的值大于temp，就将i后一位的值设为i处的值，同时将i减1。
5）在i不在数组中或i处的值不必temp大时结束第四部的循环，然后将i后一位的值设置为temp。

将上面这部分描述翻译为insertion_sort函数，下面是完整的测试程序。

#include <iostream>
#include <cstdio>

using namespace std;

#define MAX_N 1000

int A[MAX_N];
int n;

void insertion_sort();

int main()
{
    printf("数组长度：\n");
    scanf("%d",&n);
    printf("数组内容：\n");
    for(int i=0;i<n;i++)
    {
        scanf("%d",&A[i]);
    }
    insertion_sort();
        for(int i=0;i<n;i++)
    {
        printf("%d ",A[i]);
    }
    return 0;
}

void insertion_sort()
{
    for(int j=1;j<n;j++)
    {
        int temp=A[j];
        int i=j-1;
        while(i>=0&&A[i]>temp)
        {
            A[i+1]=A[i];
            i=i-1;
        }
        A[i+1]=temp;
    }
}

下面是能够帮助我们理解算法的正确性的循环不变式的三条性质：

初始化：循环第一次迭代之前，它为真。
保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。
终止：在循环终止时，不变式能够提供一个有助于证明算法正确性的性质。

就比如上面排序的例子，终止意味着在最后一次迭代时，由传入数组元素构成的子数组元素都已排好序，因此此时子数组就等同与原数组，于是循环终止。