插入排序

---

《算法导论》第二章(算法基础)

---

2.1 插入排序

• 思路分析
  我们来想象一个有趣的例子,我们得到一个任务是:
  将一副扑克牌打乱然后进行排序
  我们来分析一下大概的流程
  1.洗牌,将所有牌打乱,放置在桌子上
  2.首先从桌子上的牌顶中取得一张牌,放置在左手中
  3.以上就完成了我们的所有初始化工作
  4.现在可以进行正式的排序工作
  再从牌顶取得一张牌,拿在右手中,记住这张牌的大小
  目光聚焦在左手中,目光从右向左扫视,
  (我们这里假设左手中的牌是按照从左到右依次增大顺序排序的)
  而且我们左手中的牌就是我们最后的输出结果
  也就是说我们左手中的牌始终是排好顺序的
  而且我们设定左手中的牌从左到右依次增大
  因此就是从已经排好序的牌中的较大一端开始
  比较右手中的牌和左手中的牌
  由于第一次我们左手中只有一张牌
  因此只需要一次比较
  我们就可以确定右手中的牌应该插入到左手的牌的哪个地方
  无非就是小于在左,大于在右
  这样我们就完成了第一次排序
  下面我们继续进行分析并试图从其中总结出一些较为通用的规律
  进而提炼出我们的排序算法
  我们又取出牌顶的一张牌(注:不一定是牌顶,只不过是一种人为的规定,一种规范而已,我们总是强调风格的一致性,这也是一种风格,一旦确定这样的风格,就不要轻易地去改变,坚持下去,而且，由于我们这里桌子上的牌始终是混乱的，因此其实从这些牌中的什么位置取出一张牌用于比较，这个位置并不重要)
  注意现在我们的左手中已经有了两张牌
  和上次相同,我们的目光从右向左扫视我们的左手
  并进行比较
  然后根据比较的结果插入我们右手中的牌
  注意,这个部分是我们算法的重点
  希望大家可以静下心来
  仔细想象一下当我们真正拿着牌在排序的时候
  我们的大脑究竟是如何进行判断的
  这个过程要分析地越精细越好
  越有助于我们对程序流程和结构的剖析
  首先:
  (声明:
  严谨起见,我们将
  左手中的牌的个数记录为:j,目前j = 2
  将左手中的牌看作一个数组对象left
  使用left.length表示左手中的牌的个数也就是这个数组的长度
  也就是left[0]表示left数组的第一个变量，并以此类推
  右手中牌的大小的使用key这个变量来进行表示
  )
  我们判断的流程是:
  if (key > left[left.length - 1]){
  直接在目前左手中被比较的牌的右方插入
  也就是说在原来混乱的数组中，这两张牌其实是已经排好顺序的
  由于左手中的牌，总是拍好顺序的，因此
  当我们从桌面上拿出一张牌的时候
  如果第一次比较就发现了
  右手中的牌比左手中最右边的牌（其实也是左手中最大的牌）大
  那么就说明此刻右手中的牌比左手中任意一个都要大
  所以理所当然就应该把这张牌插入到左手牌的最右边的位置
  这里默认左手的空间足够（也就是不用移动）
  }else{
  将目光在左手中向左移动一位
  也就是关注再左边的一张牌并进行比较
  同时，将刚才比较的牌向右移动一位
  用于腾出插入的位置
  }
  现在，我们来重新审视一下我们向左手中插入一张牌的过程
  如果我们想要把这个过程在计算机中模拟的话
  我们就不得不解决这样一个问题
  就是如何来储存这些数据（即左手中的牌）
  使用数组吗？
  我们知道我们左手中的牌的数量并不固定
  如果使用一个数组的话，
  因为数组长度不能进行动态变化
  因此我们可以想到
  我们根据输入的混乱顺序的数组的长度
  向系统申请一块相同大小的长度
  这样左手（类比成一种容器，也就是类似于变量）就有了足够的容量来进行数据的储存
  这样我们就不用考虑数组长度变化的问题
  但是这样一来
  我们就浪费了内存空间
  书中的思路是这样的
  直接在原始数据的数组中进行排序
  这样的话
  就节省了大部分的内存空间
  但是有一个缺点就是我们不能回溯到原始的混乱数据
  根据我自己的理解
  书中的思路可以使用和刚才我们举的例子非常类似的一个例子来解释
  就是我们不把洗好的牌放置在桌子上
  而是直接就把它放在左手中
  然后后面的思路就几乎相同
  我们刚才的例子中
  桌面就相当于原始混乱数据
  而左手就相当于我们重新向系统申请了一块和原始数据相同大小的内存（或者说是一种可以伸缩长度的数据结构）
  然后就开始进行最开始我们讲的排序操作

---

• 总结
  学习算法如果可以从生活中的例子中模拟类似的情况，是非常有助于理解算法的原理和流程的。

---

• 代码实现

package chapter2;

/**
 * 插入排序算法
 * Created by 王一航 on 2016/7/1.
 */
public class InsertionSort {
    //初始化数据
    static  int[] numbers;
    //主入口
    public static void main(String[] args) {
        init();//初始化待排序数据
        show();//打印输出数据
        sort();//进行排序
        show();//打印输出数据
    }
    //初始化数组
    public static void init(){
        //将未排序的数据赋值给数组(洗牌,并将洗好的牌放置在桌子上)
        numbers = new int[]{5,2,4,6,3,6,42,66,33,87,34,11,12,10,33,12,22,32,1};
    }
    //排序算法
    public static void sort(){
        //首先从桌子上的扑克牌中取出一张,放置在左手中(这也就是为什么j = 1,而不是j = 0)
        for(int j = 1; j < numbers.length; j++){
            int key = numbers[j];//(从桌子上取出一张牌,放置在右手中)
            int i = j - 1;//眼睛盯住左手中的牌,以便于等一下进行比较
            while((i >= 0) && (numbers[i] > key)){//和左手中的牌比较大小
                numbers[i + 1] = numbers[i];
                //发现比右手中的牌大,则将其向右移动一位,以腾出插入右手中牌的空间
                //numbers[j] = numbers[i];
                i--;//将目光向左移动,以便于下一次比较
            }
            numbers[i + 1] = key;//将右手中的牌插入左手中的腾出的空闲位置
        }
    }
    //打印数组
    public static void show(){
        for(int i = 0; i < numbers.length; i++){
            System.out.print(numbers[i] + " ");
        }
    }
}