排序算法系列(4)——直接插入排序

直接选择排序是选择排序中最基础的一部分
在此拿出来讲是为了为后面的折半选择排序和希尔排序(缩小增量排序)做好铺垫，打好基础

---

中心思想：

1. 首先有一个需要排序的array [ 定义一个变量len = array.length]
2. 先认为array[0]是一个已经排好序的序列，认为array[1]~array[len-1]是无序序列。
3. 那么就开始遍历了，首先 令 i=1
4. 那么将array[i] 需要插入已经有序的序列array[0]~array[i-1]中。
   然后就形成了 有序序列array[0]~array[i]
5. 然后 i++ 若i<len [也就是说数组没有out of index 还是存在无序序列的]执行步骤4 否则也就是i>=len的时候就说明所有的无序序列都被插入到了有序的序列中也就是说已经排好序列了。

---

图的例子：

说了那么多还是上个图比较实在，图的排序过程很形象。

直接选择排序.png

---

代码实现：

根据看了一些博客啥的，发现直接排序实现方案有几种，在此将自己了解到的列出来。

1. my-version

package directInsertion;

import java.util.Arrays;

/**
 * 直接插入排序 默认的排序规则为从小到大的排序方式
 * 
 * @author mengf
 *
 */
public class Main {

    public static int[] directInsertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            // 判断array[i]需要放入的array的正确位置 j记录正确位置的index
            int j = i - 1;
            for (; j >= 0; j--) {
                // 一旦比前面某个大就说明在那个后面一个
                if (array[j] <= array[i]) {
                    j++;
                    break;
                }
                // array[i]应该在0位置的情况
                if (j == 0) {
                    break;
                }
            }

            int temp = array[i];
            // 找到array[i]对应的位置之后就需要插入
            for (int k = i; k > j; k--) {
                array[k] = array[k - 1];
            }
            array[j] = temp;
        }

        return array;
    }

    public static void main(String[] args) {
        int[] array = { 5, 9, 6, 2 };
        directInsertionSort(array);
        System.out.println(Arrays.toString(array));
    }
}

说实在的我个人能力有限，弄成这样我就满意了，但是之后发现网上有更简洁的代码，一比较才发现自己是多么的麻烦
发上一个简单版本：

2. simple version

这是一个边移动 边比较的方法 相当于my-version将内循环中的两个for糅合
my-version 是先比较完确定好位置之后 再移动

package directInsertion;

import java.util.Arrays;

/**
 * 直接插入排序 默认的排序规则为从小到大的排序方式
 * 
 * @author mengf
 *
 */
public class Main {

    public static int[] directInsertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            // 只有i比前面一个排好序的小的时候才说明需要前移 否则说明不需要前移
            if (array[i] < array[i - 1]) {
                int temp = array[i];
//              //边比较边移动
//              for (int j = i - 1; j >= 0; j--) {
//                  if (array[j] > temp) {
//                      array[j + 1] = array[j];
//                      if (j == 0) {
//                          array[j] = temp;
//                      }
//                  } else {
//                      array[j + 1] = temp;
//                      break;
//                  }
//              }
                //这样写可以不像上面那样 把j=0 挑出来 防止数组边界溢出
                //想想很有道理！！！！
                int j = i - 1;
                for (; j >= 0 && array[j] > temp; j--) {
                    array[j+1] = array[j];
                }
                array[j+1] = temp;
            }
        }

        return array;
    }

    public static void main(String[] args) {
        int[] array = { 5, 9, 6, 2 };
        directInsertionSort(array);
        System.out.println(Arrays.toString(array));
    }
}