直接選擇排序是選擇排序中最基礎的一部分
在此拿出來講是為了為后面的折半選擇排序和希爾排序(縮小增量排序)做好鋪墊，打好基礎

中心思想：

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 還是存在無序序列的]執(zhí)行步驟4 否則也就是i>=len的時候就說明所有的無序序列都被插入到了有序的序列中也就是說已經排好序列了。

圖的例子：

說了那么多還是上個圖比較實在，圖的排序過程很形象。

直接選擇排序.png

代碼實現：

根據看了一些博客啥的，發(fā)現直接排序實現方案有幾種，在此將自己了解到的列出來。

1. my-version

package directInsertion;

import java.util.Arrays;

/**
 * 直接插入排序 默認的排序規(guī)則為從小到大的排序方式
 * 
 * @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));
    }
}

說實在的我個人能力有限，弄成這樣我就滿意了，但是之后發(fā)現網上有更簡潔的代碼，一比較才發(fā)現自己是多么的麻煩
發(fā)上一個簡單版本：

2. simple version

這是一個邊移動 邊比較的方法 相當于my-version將內循環(huán)中的兩個for糅合
my-version 是先比較完確定好位置之后 再移動

package directInsertion;

import java.util.Arrays;

/**
 * 直接插入排序 默認的排序規(guī)則為從小到大的排序方式
 * 
 * @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));
    }
}