0101插入排序-算法基础-算法导论第三版

文章目录

- 一插入排序
- 二循环不变式与插入排序的正确性
- 三伪代码中的一些约定
- 四 Java代码实现插入排序
- 结语

一插入排序

输入： $n$ 个数订单一个序列 $(a_1,a_2,\cdots,a_n)$ .

**输出：**输入序列的一个排列 $(a^{'}_1,a^{'}_2,\cdots,a^{'}_n)$ ,满足 $a^{'}_1\le a^{'}_2\le\cdots\le a^{'}_n$ (从小到大排序)。

我们希望的数也称为 关键词。

我们通常将算法描述为用一种 伪代码书写的程序。伪代码与真代码区别：

在伪代码中，使用最清晰、最简洁的表示方法来说明给定的算法。
伪代码不关系软件工程的问题。为了更简洁的表达算法的本质，常常忽略数据抽象、模块性和错误处理的问题。

tips: 关于插入排序的概念性描述，可以参考最后链接2，这里不在赘述。

插入排序的伪代码如下：

INSERTION-SORT(A)
	for i = 2 to A.length
		key = A[j]
		i = j-1
		while i>0 and a[i] > key
			a[i+1] = a[i]
			i = i - 1
		a[i+1] = key

二循环不变式与插入排序的正确性

在这里插入图片描述

上图表名 $A = (5, 2, 4, 6, 1, 3)$ 该算法如何工作。

下标 $j$ 指出正被插入到手中的”当前牌".
在for循环（循环变量为 $j$ ）的每次迭代开始，包含元素 $[1\cdots j-1]$ 的子数组构成了当前排序好的左手中的牌；剩余的子数组 $[j+1\cdots n]$ 对应与扔在桌子上的牌堆。

元素 $[1\cdots j-1]$ 就是原来在位置1到 $j - 1$ 的元素，但现在已按序排列。我们把 $[1\cdots j-1]$ 的这些性质形式地表示为一个循环不变式。

循环不变式主要用来帮助我们理解算法的正确性。关于循环不变式，我们必须证明三条性质：

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

循环不变式证明算法正确性与归纳法比较：

初始化对应与归纳法基本情况。
保持对应于归纳步。
归纳法中，归纳步是无限使用，这里当循环终止时，停止”归纳“。

通过循环不变式的三条性质，证明插入排序正确性：

初始化：在第一次循环迭代之前（j=2）。子数组 $A[1\cdots j-1]$ 为 $A [1]$ ，该数组已排序。这表名第一次循环迭代之前循环不变式成立。
保持：非形式化for循环的第4~7行将 $A[j-1]、A[j-2]、\cdots$ 依次向右移动一个位置，直到找到 $A [j]$ 的适当位置，第8行将 $A [j]$ 插入该位置。这时子数组 $A[1\cdots j]$ 由原来在 $A[1\cdots j]$ 的元素组成，但已按序排列。那么对for循环的下一次迭代增加j将保持循环不变式。
终止：导致循环终止的条件 $j\gt A.length=n$ ,每次循环迭代j增加1，此时 $j = n + 1$ 。在循环不变式的表述中把 $j 用 n + 1$ 代替。子数组 $A[1\cdots n]$ 由原来在 $A[1\cdots n]$ 中的元素组成，但已按序排列。子数组 $A[1\cdots n]$ 为整个数组，我们推断整个数组已排序。因此算法正确。

在本章后面及其他章节中，我们将采用这种循环不变式的方法证明算法的正确性。

三伪代码中的一些约定

缩进表示块结构，参考python。
while、for、与repeat-until等循环结构以及if-else条件结构与C、C++、Java、Python中的结构具有类似的解释。
符号"//"表示后面部分是注释。
形如 $i = j = e 等级与 j = e; i = j$
变量（如 $i, j, k ey$ ）是局部变量。若无显示说明，我们不使用全局变量。
数组元素通过"数组名[下标]“这样的形式来访问。记号” $\cdots$ "用于表示数组中值的一个范围。
复合数据通常被组织成对象，对象由属性组成。对象名后跟一个点在跟对象名来访问对象属性。
我们按值把参数传递给对象。当对象被传递时，传递指向该对象的指针（引用）。
一个return语句立即将控制返回到调用过程的调用点。
布尔运算符”and“和”or“都是短路的。
关键词error表示因为已被调用的过程情况不对而出现了一个错误。调用过程负责处理该错误，所以我们不用说明将采取什么行动。

四 Java代码实现插入排序

package com.gaogzhen.algorithms4.sort;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

/**
 * 插入排序
 * 算法：
 * 1. 插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的
 * 2. 现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的
 * 3. 按照此法对所有元素进行插入，直到整个序列排为有序的过
 */
public class Insertion {

    /**
     * 排序方法
     * @param a     实现了Comparable接口的待排序数组
     */
    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 1; i < N; i++) {
            for (int j = i ; j > 0 && less(a[j], a[j - 1]);  j--) {
                exch(a, j, j - 1);
            }

        }
    }

    /**
     * 比较大小
     * @param a     目标a
     * @param b     目标b
     * @return      返回布尔值
     */
    private static  boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

    /**
     * 交换数组元素
     * @param a     数组
     * @param i     索引
     * @param j     索引
     */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 打印数组
     * @param a     数组
     */
    private static void show(Comparable[] a) {
        // 单行打印数组
        for (int i = 0; i < a.length; i++) {
            StdOut.print(a[i] + " ");
        }
        StdOut.println();
    }

    /**
     * 测试数组是否已经有序
     * @param a     带测试数组
     * @return      测试结果: true-数组有序；false-数组无序
     */
    public static boolean isSorted(Comparable[] a) {
        // 测试数组是否已经有序
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i-1])) return false;
        }
        return  true;
    }

    public static void main(String[] args) {
        // 从标准输入读取字符串，将他们排序并输出
        String[] a = StdIn.readAllStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}