直接插入排序

学习算法主要学习其思想，本章将讲述插入排序的直接插入排序算法；

主要思想：对于一个待排序的序列，我们假设第一个数已经为排好序的序列；并从第二个记录开始，往前比较，插入到有序序列当中，直至待排序序列最后一个记录插入结束。

注：直接插入排序需要设立哨兵（用于存放待插入记录）

 

public class StraightInsertionSort {
    
    private static int[] sortArray = {20,9,18,77,10,6,9};

    /**
      * sort(直接插入排序,升序)
     */
    public static void sort() {
        
        for (int index = 1;index < sortArray.length; index++) {
            
            if (sortArray[index] < sortArray[index - 1]) {
                // 哨兵
                int guard = sortArray[index];
                int indexJ = index - 1;
                // 往后移位
                sortArray[index] = sortArray[indexJ];
                // 从后往前遍历，直到找到位置
                while (indexJ > 0 && guard < sortArray[indexJ - 1]) {
                    sortArray[indexJ] = sortArray[indexJ - 1];
                    indexJ--;
                }
                sortArray[indexJ] = guard;
            }
            printSortResult();
        }
    }
    
    public static void printSortResult() {
        
        for(int val : sortArray) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
    /**
      * main(执行主函数)
      * @param args
      */
    public static void main(String[] args) {
        sort();
    }

}