经典算法学习之---折半插入排序

活动地址：CSDN21天学习挑战赛

一、什么是算法

本专栏为《手撕算法》栏目的子专栏：《经典算法》，会讲述一些经典算法，并进行分析。在此之前我们要先了解什么是算法，能够解决什么样的问题。

1. 算法的定义

以下为经典教材《Introduction.to.Algorithms》开篇中的内容。

Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.

可以看到，任何被明确定义的计算过程都可以称作算法，它将某个值或一组值作为输入，并产生某个值或一组值作为输出。所以算法可以被称作将输入转为输出的一系列的计算步骤。
这样的概括是比较标准和抽象的，其实说白了就是步骤明确的解决问题的方法。由于是在计算机中执行，所以通常先用伪代码来表示，清晰的表达出思路和步骤，这样在真正执行的时候，就可以使用不同的语言来实现出相同的效果。
概括的说，算法就是解决问题的工具。在描述一个算法时，我们关注的是输入与输出。也就是说只要把原始数据和结果数据描述清楚了，那么算法所做的事情也就清楚了。我们在设计一个算法时也是需要先明确我们有什么和我们要什么，这一点相信大家在后面的文章中会慢慢体会到。

2. 补充的概念

• 数据结构

算法经常会和数据结构一起出现，这是因为对于同一个问题（如：排序），使用不同的数据结构来存储数据，对应的算法可能千差万别。所以在整个学习过程中，也会涉及到各种数据结构的使用。
常见的数据结构包括：数组、堆、栈、队列、链表、树等等。

• 算法的效率

在一个算法设计完成后，还需要对算法的执行情况做一个评估。一个好的算法，可以大幅度的节省运行的资源消耗和时间。在进行评估时不需要太具体，毕竟数据量是不确定的，通常是以数据量为基准来确定一个量级，通常会使用到时间复杂度和空间复杂度这两个概念。

• 时间复杂度

通常把算法中的基本操作重复执行的频度称为算法的时间复杂度。算法中的基本操作一般是指算法中最深层循环内的语句（赋值、判断、四则运算等基础操作）。我们可以把时间频度记为T(n)，它与算法中语句的执行次数成正比。其中的n被称为问题的规模，大多数情况下为输入的数据量。
对于每一段代码，都可以转化为常数或与n相关的函数表达式，记做f(n) 。如果我们把每一段代码的花费的时间加起来就能够得到一个刻画时间复杂度的表达式，在合并后保留量级最大的部分即可确定时间复杂度，记做O(f(n)) ，其中的O就是代表数量级。
常见的时间复杂度有（由低到高）：O(1)、O( log ⁡ 2 n \log _{2} n log2​n)、O(n)、O( n log ⁡ 2 n n\log _{2} n nlog2​n)、O( n 2 n^{2} n2)、O( n 3 n^{3} n3)、O( 2 n 2^{n} 2n)、O(n!)。

• 空间复杂度

程序从开始执行到结束所需要的内存容量，也就是整个过程中最大需要占用多少的空间。为了评估算法本身，输入数据所占用的空间不会考虑，通常更关注算法运行时需要额外定义多少临时变量或多少存储结构。如：如果需要借助一个临时变量来进行两个元素的交换，则空间复杂度为O(1)。

• 伪代码约定

伪代码是用来描述算法执行的步骤，不会具体到某一种语言，为了表达清晰和标准化，会有一些约定的含义：
缩进：表示块结构，如循环结构或选择结构，使用缩进来表示这一部分都在该结构中。
循环计数器：对于循环结构，在循环终止时，计数器的值应该为第一个超出界限的值。
to：表示循环计数器的值增加。
downto：表示循环计数器的值减少。
by：循环计数器的值默认变化量为1，当大于1时可以使用by。
变量默认是局部定义的。
数组元素访问：通过"数组名[下标]"形式，在伪代码中，下标从1开始（"A[1]“代表数组A的第一个元素）。
子数组：使用”…"来代表数组中的一个范围，如"A[i…j]"代表从第i个到第j个元素组成的子数组。
对象与属性：复合的数据会被组织成对象，如链表包含后继（next）和存储的数据（data）,使用“对象名 + 点 + 属性名”。
特殊值NIL：表示指针不指向任何对象，如二叉树节点无子孩子可认为左右子节点信息为NIL。
return：返回到调用过程的调用点，在伪代码中允许返回多个值。
and和or：与运算和或运算默认短路，即如果已经能够确定表达式结果时，其他条件不会去判断或执行。

二、插入排序

1. 插入排序介绍

插入排序的基本思路是每次插入一个元素，每一趟完成对一个待排元素的放置，直到全部插入完成。

• 直接插入排序

直接插入排序是一种最简单的排序方法，过程就是将每个待排元素逐个插入到已经排好的有序序列中。

• 折半插入排序

由于在插入排序的过程中，已经生成了一个（排好的元素组成的）有序数列。所以在插入待排元素时可以使用折半查找的方式更快速的确定新元素的位置，当元素个数较多时，折半插入排序优于直接插入排序。

• 希尔排序

希尔排序可以看做是分组插入的排序方法，把全部元素分成几组（等距元素分到一组），在每一组内进行直接插入排序。然后继续减少间距，形成新的分组，进行排序，直到间距为1时停止。\

2. 折半插入排序

• 输入

n个数的序列，通常直接存放在数组中，可能是任何顺序。

• 输出

输入序列的一个新排列，满足从小到大的顺序（默认讨论升序，简单的修改就可以实现降序排列）。

• 算法说明

每次从原有数据中取出一个数，插入到之前已经排好的序列中，直到所有的数全部取完，那么新的有序排列也就完成了。这个过程与直接插入排序十分类似，不同的地方在于插入时如何寻找位置。

1. 直接插入排序：从后（排好的最后一个元素）至前逐一比较寻找位置。
2. 折半插入排序：利用已排好的元素有序的特点，使用折半查找的方式快速确定位置。

• 算法流程

以下图片取材自《数据结构简明教程》：

1. 输入数据集被分为有序区和无序区两部分。

2. 最初有序区没有元素，从无序区不断取出元素放入，保证放入的元素均已有序。

3. 已知前i个元素已排好（下标从0至i-1），从无序区取出第一个元素（数据集的第i + 1个元素）。

4. 先与有序区的最后一个元素比较

   1. 如果较大则代表该元素已经在合适的位置，则直接归入有序区，进入下一个元素的判断。
   2. 如果较小则需要进一步确定位置，执行以下步骤。

5. 搜索区间为从low至high，初始区间为整个有序区（从0至i-1）。

6. 将待插入元素记录在临时变量tmp中，为后续的元素串位做准备。

7. 计算mid = (low + high) / 2，将该位置的元素与R[i]比较。

8. 不断的缩小搜索区间，直到确定插入位置（原理与折半查找相同）。

9. 确定位置后，将有序区中的元素从后至前逐个后串，最后将tmp中的值覆盖到插入位置。

3. 伪代码

折半插入排序可以看做是将直接插入排序与折半查找两种算法进行结合，排序的思路与直接插入排序相同，只是在确定插入位置时借助了折半查找的方法（不考虑集合中有重复元素的情况）。

for i = 2 to A.length
    if A[i] < A[i - 1]
        tmp = A[i]
        low = 0
        high = i - 1
        while low <= high
            mid = (low + high) / 2
            if A[mid] > tmp
                high = mid - 1
            else
                low = mid + 1
        for j = i - 1 downto high + 1
            A[j + 1] = A[j]
        A[high + 1] = tmp
1
2
3
4
5
6
7
8
9
10
11
12
13
14

由于不会出现重复元素，所以最后一定会将搜索区间缩小至low与high重合（左右区间端点不断移动）。在最后一次循环时，low、high的值相同，在比较完成后，left与right发生交错，相差为1，此时要选择一个变量的值作为新插入元素的位置参照。
需要明确的是，最后一次比较时不会出现左端点向左移或右端点向右移的情况，因为在上一次比较时，待插入元素必定是能够落在low与high的区间内的，这就决定了tmp一定大于low对应的元素，小于high对应的元素。
并且由于mid的计算方法，最后一次比较是tmp与low对应元素的比较，并且tmp（待插入元素）是较大的，此时进else分支。并且我们知道最终的插入位置应该放在最后比较元素的后一个位置，也就是mid对应位置的后面，所以是mid + 1。
如果用low表示，就刚好是low，如果用right表示，则应该是high + 1。

三、算法实践

1. 算法实现

• 输入数据（input）：11，34，20，10，12，35，41，32，43，14
• Java源代码

public class BinaryInsert {

    public static void main(String[] args) {
        // input data
        int[] a = {11,34,20,10,12,35,41,32,43,14};
        // 数组下标从0开始，j初始为1，指向第二个元素
        for (int i = 1;i < a.length;i++){
            if (a[i] < a[i - 1]){
                // 使用temp记录当前元素的值
                int tmp = a[i];
                // 初始化变量
                int left = 0;
                int right = i - 1;
                // while循环作用：使用二分查找确定元素位置，并串出对应的位置
                while(left <= right){
                    // 取中间元素，以下写法防止数据量较大时发生溢出
                    int mid = (right - left) / 2 + left;
                    if(a[mid] > tmp){
                        // 待排元素较小，将搜索区间缩小至左一半
                        right = mid - 1;
                    }else {
                        // 待排元素较大，将搜索区间缩小至右一半
                        left = mid + 1;
                    }
                }
                // 将待排元素放在对应的位置
                for (int j = i - 1;j >= right + 1;j--){
                    a[j + 1] = a[j];
                }
                a[right + 1] = tmp;
            }
        }
        // 查看排序结果
        for (int data : a){
            System.out.print(data + "\t");
        }
    }

}
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

• 执行效果

2. 时间复杂度

对于折半插入排序来说，由于元素的串位次数没有发生变化，只是在查找位置是更加快速了，所以总得来说与直接插入排序处于同一量级，在数据量很大时，要优于直接插入排序。

• 最坏的情况

如果输入的元素刚好是反向有序的，那么每次都需要进行位置的查找，但是在查找的次数要少一些。可以知道，由于区间每次缩小一半，可以得到寻找位置的次数最多为 log ⁡ 2 i \log _{2} i log2​i 量级，但是由于移动元素的次数没变，时间复杂度依然是 O( n 2 n^{2} n2) 。

• 最好的情况

最好的情况与直接插入排序相同，如果元素已经是正向有序的，那么在最开始比较的时候就会认为在合适的位置，不需要再进行位置的寻找和串位，因此时间复杂度为O(n) 。

• 平均情况

综合两种情况，插入排序的时间复杂度为O( n 2 n^{2} n2) 。

3. 空间复杂度

算法执行过程中直接在原集合上操作，只需要几个额外的变量记录关键信息，所以空间复杂度为常数级：O(1) 。

文章来源1，2，3