資料結構（二十）：插入排序算法

插入排序原理很簡單，講一組資料分成兩組，我分别将其稱為有序組與待插入組。每次從待插入組中取出一個元素，與有序組的元素進行比較，并找到合适的位置，将該元素插到有序組當中。就這樣，每次插入一個元素，有序組增加，待插入組減少。直到待插入組元素個數為0。當然，插入過程中涉及到了元素的移動。

package com.atguigu.sort;

import java.text.SimpleDateFormat;

import java.util.Arrays;

import java.util.Date;

public class InsertSort {

    public static void main(String[] args) {

        //int[] arr = {101, 34, 119, 1, -1, 89}; 

        // 建立要給80000個的随機的數組

        int[] arr = new int[80000];

        for (int i = 0; i < 80000; i++) {

            arr[i] = (int) (Math.random() * 8000000); // 生成一個[0, 8000000) 數

        }

        System.out.println("插入排序前");

        Date data1 = new Date();

        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");

        String date1Str = simpleDateFormat.format(data1);

        System.out.println("排序前的時間是=" + date1Str);

        insertSort(arr); //調用插入排序算法

        Date data2 = new Date();

        String date2Str = simpleDateFormat.format(data2);

        System.out.println("排序前的時間是=" + date2Str);

        //System.out.println(Arrays.toString(arr));

    }

    //插入排序

    public static void insertSort(int[] arr) {

        int insertVal = 0;

        int insertIndex = 0;

        //使用for循環來把代碼簡化

        for(int i = 1; i < arr.length; i++) {

            //定義待插入的數

            insertVal = arr[i];

            insertIndex = i - 1; // 即arr[1]的前面這個數的下标

            // 給insertVal 找到插入的位置

            // 說明

            // 1. insertIndex >= 0 保證在給insertVal 找插入位置，不越界

            // 2. insertVal < arr[insertIndex] 待插入的數，還沒有找到插入位置

            // 3. 就需要将 arr[insertIndex] 後移

            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {

                arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]

                insertIndex--;

            }

            // 當退出while循環時，說明插入的位置找到, insertIndex + 1

            // 舉例：了解不了，我們一會 debug

            //這裡我們判斷是否需要指派

            if(insertIndex + 1 != i) {

                arr[insertIndex + 1] = insertVal;

            }

            //System.out.println("第"+i+"輪插入");

            //System.out.println(Arrays.toString(arr));

        }

    }

}