排序

概念

• 1.1 排序
  排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
  平时的上下文中，如果提到排序，通常指的是排升序（非降序）。
  通常意义上的排序，都是指的原地排序(in place sort)。

• 1.2 稳定性
  两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序
  算法。

  9 , 5 , 2 , 7 , 12 , 2 , 4 , 6 , 9 , 23
  排序后
  前面的 2 依旧在后面的 2 的后面那么称这个算法具有稳定性

直接插入排序

整个区间被分为

1. 有序区间
2. 无序区间
   每次选择无序区间的第一个元素，在有序区间内选择合适的位置插入，随着数组的遍历完成以及元素的插入，数组就有序起来

9 , 5 , 2 , 7 , 12 , 2 , 4 , 6 , 9 , 23

（1）利用key记住5
（2）从5开始，我们默认第一个元素有序，拿5和9比较，比9小，
9向后移动
（3）5继续比较发现没有元素，那么将5插入成第一个元素
（4）数组变为了 5，9， 2 , 7 , 12 , 2 , 4 , 6 , 9 , 23
（5）现在认为有序区间有两个元素，所以在无序区间继续选择
（6）利用key记住2
（7）我们拿2和9比较，比9小，9向后移动
（8）数组变为了5，9，9，7，12，2，4，6，9，23
（9）在拿2和5比较，比5小，5向后移动
（10）数组变为了 5，5，9，7，12，2，4，6，9，23
（11）2没有要比的元素，将其插入
（12）数组变为了2，5，9，7，12，2，4，6，9，23
.。。。
继续下去数组最后就会有序

实现

    //插入排序
    public static void insertSort(int[] array){
        //从1开始是因为我们默认第一个元素是有序的
        for(int i = 1;i < array.length;i++){
            //这里用变量记住这个要进行插入的数据
            int key = array[i];
            //j表示有序区间的最后一个下标（从后往前比较）
            int j = i - 1;
            //如果有序区间的元素大那么有序区间向后移动，让key进行插入。（这就是为什么要用key记住插入的数据
            // 防止被移动的有序元素覆盖掉，大于号是为了保证稳定性）
            for(; j >= 0 && array[j] > key;j--){
                array[j+1] = array[j];
            }
            //j+1才是真正要插入的地方
            array[j+1] = key;
        }
    }

总结：
直接插入排序是一种稳定的算法，因为它是按照原本数组的顺序一步步向后遍历的，插入的时候移动条件是大于才移动。
所以等于的时候数组没有进行改变，这就保证了数组的稳定性！
注：如有运行错误，请评论一下我尽快更改，谢谢啦！