直接插入排序
概念
直接插入排序就是將一堆數(shù)據(jù)分為兩個(gè)部分(思想上分開而已，實(shí)際上還是在同一個(gè)數(shù)組中)，一部分是有序的，一部分是無序的，每次從無序表中找一個(gè)需要插入有序表中值，找到有序表中合適的位置插入，這個(gè)合適的位置就是說這個(gè)新的值插入之后有序表仍然是有序的。n個(gè)數(shù)據(jù)，一開始第一個(gè)放在有序表，剩下n-1個(gè)放在無序表，等到無序表中每一個(gè)都找出來插入到無序表中的時(shí)候就排序完畢了。
(直接)插入排序.gif
看這個(gè)動態(tài)圖，你會很直觀清晰的理解直接插入排序，注意每次比對有序表中的一個(gè)值的時(shí)候，如果有序表中那個(gè)值比現(xiàn)在要插入的值大的話需要往后面移動的，所以插入的值需要用一個(gè)變量保存起來，這樣就可以將原來無序表的位置直接覆蓋了。
思路分析
- 一開始無序表有n-1個(gè)數(shù)據(jù)，所以需要一個(gè)一個(gè)拿出來插入有序表中，需要n-1趟
- 每一趟取出無序表第一個(gè)，也就是有序表最后一個(gè)下標(biāo)位置加一那個(gè)值，保存這個(gè)insertVal和insValIndex，和無序表中從后往前進(jìn)行比較，比當(dāng)前比較的有序表的數(shù)小則那個(gè)有序表的數(shù)后移。
代碼實(shí)現(xiàn)
感覺挺簡單的東西越說越復(fù)雜了一樣，看看代碼應(yīng)該很容易就理解了。
package _6_sort;
import java.util.Arrays;
import java.util.Date;
/**
* author waigo
* create 2021-01-27 9:54
*/
public class InsertSort {
public static void insertSort(int[] data) {
for (int i = 1; i < data.length; i++) {//n-1次,一開始有序表就一個(gè)數(shù)，下標(biāo)為0
int insertVal = data[i], insValIndex = i - 1;//插入值就是當(dāng)前無序表的第一個(gè)，嘗試插入無序表最后一個(gè)位置
//insValIndex = i - 1比起insValIndex = i來說好處是每一種情況下都是一樣的，最后都是插入insValIndex+1的位置，不用進(jìn)行多一個(gè)判斷
while (insValIndex >= 0 && insertVal < data[insValIndex]) {
data[insValIndex + 1] = data[insValIndex];//插入位置那個(gè)數(shù)后移
insValIndex--;//插入位置往前移
}
//當(dāng)前insValIndex找到的就是比insertVal小的那個(gè)數(shù)，插入到insValIndex+1的位置
data[insValIndex + 1] = insertVal;
}
}
public static void main(String[] args) {
int[] arr = RandomProducer.produceRandom(5,10000,80000);
// int[] arr = {101,34,119,1};
// System.out.println("排序前");
// System.out.println(Arrays.toString(arr));
Date from = new Date();
insertSort(arr);
// System.out.println("排序后");
// System.out.println(Arrays.toString(arr));
System.out.println("運(yùn)行了"+(new Date().getTime() - from.getTime())+"毫秒");
//測試80000個(gè)隨機(jī)數(shù)的排序，大概0.8秒，比冒泡18s和簡單選擇4s快多了
}
}
