上節(jié)我們學習了選擇排序算法,本節(jié)我們繼續(xù)學習相關剩余算法如我們本節(jié)要學習的插入排序,直接入正題,先來介紹下什么是插入排序?
插入排序介紹
插入排序也是基于內存操作的,是對想要排序的元素已插入的方式尋找到該元素的位置已達到排序的效果.
看著很難以理解,通過一個例子來看看,如圖:
插入排序圖.png
上圖中初始狀態(tài)我們可以看成是一個數組R,其中R[0]~R[5]表示對應值的下標索引,其中該數組為R= {17,3,25,14,20,9},接著我們來看一下這個過程
- 說明:
- 1 我們可以將R數組看成是一個有序列列{17}和無序列{3,25,14,20,9},我們要做到是將.
- 無序列中的值往有序列{17}中插入,至于規(guī)則自己定.'
- 2 我這里就按照上圖中的來說插入的時候按照從小到大插入即可
- 過程:
- 第一次插入的時候,將無序列中的下標為1的值(3)插入有序列中{17}中,發(fā)現要插入的值小于有序列中的原先的值,首先將原先有序列中的值往后移動一位,接著將3插入空出來的位置即可.
- 第二次插入的時候是將數組R中的R[2]也就是值為25,通過判斷發(fā)現25大于有序列中的3和17,故它的位置不變,這里是一種巧合的場景.
- 第三次插入的時候,將數組R中的R[3]插入到有序列表{3,17,25}中通過比較14大于3小于17即插入到3和17之間即可
- 第四次和第五次重復上述過程即可
這就是上圖中插入排序的過程,通過上圖的過程我們來總結下插入排序的思想:
- 按照上述過程得到,我們可以將一個待排序的元素看成是一個有序列表和無序列表.
- 首先開始的時候有序列表中只有一個元素(所以它一定是有序的),無序列表中有n-1個元素
- 在排序的過程中,每次從無序列表中取出第一個元素,把它的排序號依次跟有序列表中的進行比較,然后將它插入到有序列表中的適當位置,使之成為新的有序列表.
知道了它的排序思想,我們通過代碼來完成該過程
代碼實現
假設我這里有一個待排序的數組元素集合arr={101,34,119,1},需要進行排序,我們來看過程
- 第一次的排序代碼實現
//逐步推導過程
//{101,34,119,1} -> 首先以{101}為有序列表,以{4,119,1}為無序列表
//將無序列表中的數往有序列表中添加
//定義待插入的數和索引下標
int insertVal = arr[1]; //這里也就是34
int insertIndex = 1 - 1; //arr[1]前面數的下標
//簡單說明:
//1. insertIndex>=0 其主要的目的是為了防止在插入時候為了約束越界
//2. insertVal < arr[insertIndex]表示待插入的數還沒有找到插入的位置如: 34 < arr[0] =101
//3. 需要將 arr[insertIndex]往后移動
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex]; //此時的數組為{101,101,119,1}
insertIndex--;
}
//當退出while循環(huán)時,說明插入的位置找到,需要 insertIndex +1 如: 34改為 134
arr[insertIndex + 1] = insertVal;
System.out.println("第一輪插入后的結果為:");
System.out.println(Arrays.toString(arr));
我們先來猜測下結果,我猜測第一次排序過后的數組為{34,101,119,1},多說無益,來看測試結果:
插入排序第一輪結果圖.png
從上述結果來看我們的猜測是正確的,接著看
- 第二次的排序過程:
//定義待插入的數和索引下標
insertVal = arr[2]; //這里也就是119
insertIndex = 2-1; //arr[2]前面數的下標
//簡單說明:
//1. insertIndex>=0 其主要的目的是為了防止在插入時候為了約束越界
//2. insertVal < arr[insertIndex]表示待插入的數還沒有找到插入的位置如: 34 < arr[] =101
//3. 需要將 arr[insertIndex]往后移動
while (insertIndex >=0 && insertVal < arr[insertIndex]){
arr[insertIndex +1] = arr[insertIndex]; //此時的數組為{101,101,119,1}
insertIndex --;
}
//當退出while循環(huán)時,說明插入的位置找到,需要 insertIndex +1 如: 34改為 134
arr[insertIndex + 1] = insertVal;
System.out.println("第二輪插入后的結果為:");
System.out.println(Arrays.toString(arr));
不猜了,直接看結果圖:
第二輪結果圖.png
-第三次過程:
//定義待插入的數和索引下標
insertVal = arr[3]; //這里也就是119
insertIndex = 3-1; //arr[2]前面數的下標
//簡單說明:
//1. insertIndex>=0 其主要的目的是為了防止在插入時候為了約束越界
//2. insertVal < arr[insertIndex]表示待插入的數還沒有找到插入的位置如: 34 < arr[] =101
//3. 需要將 arr[insertIndex]往后移動
while (insertIndex >=0 && insertVal < arr[insertIndex]){
arr[insertIndex +1] = arr[insertIndex]; //此時的數組為{101,101,119,1}
insertIndex --;
}
//當退出while循環(huán)時,說明插入的位置找到,需要 insertIndex +1 如: 34改為 134
arr[insertIndex + 1] = insertVal;
System.out.println("第三輪插入后的結果為:");
System.out.println(Arrays.toString(arr));
來看測試結果:
第三輪測試結果圖.png
通過上述過程我們完成了該元素的排序過程,我們來封裝下代碼:
//插入排序方法封裝
public static void insertSort(int [] arr){
int insertVal = 0;
int insertIndex = 0;
for (int i = 1; i <arr.length; i++) {
//逐步推導過程
//{101,34,119,1} -> 首先以{101}為有序列表,以{4,119,1}為無序列表
//將無序列表中的數往有序列表中添加
//定義待插入的數和索引下標
insertVal = arr[i]; //這里也就是34
insertIndex = i - 1; //arr[1]前面數的下標
//簡單說明:
//1. insertIndex>=0 其主要的目的是為了防止在插入時候為了約束越界
//2. insertVal < arr[insertIndex]表示待插入的數還沒有找到插入的位置如: 34 < arr[0] =101
//3. 需要將 arr[insertIndex]往后移動
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex]; //此時的數組為{101,101,119,1}
insertIndex--;
}
//當退出while循環(huán)時,說明插入的位置找到,需要 insertIndex +1 如: 34改為 134
if (insertIndex +1 != i) {
arr[insertIndex + 1] = insertVal;
}
System.out.println("第"+(i)+"輪插入后的結果為:");
System.out.println(Arrays.toString(arr));
}
最后一步我們來測試插入排序執(zhí)行10w數據的執(zhí)行時間,來看代碼:
/**
* 算法學習-插入排序
*/
public class InsertSort {
public static void main(String[] args) {
//int [] arr = {101,34,119,1};
//insertSort(arr);
//插入的時間復雜度測試
int [] arr = new int[100000];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int)(Math.random() * 100000); //隨機生成[0,100000)的數
}
Date date1 = new Date();
SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String format = dateFormat.format(date1);
System.out.println("排序前的時間為:"+format);
//進行排序
insertSort(arr);
Date date2 = new Date();
SimpleDateFormat dateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String format2 = dateFormat.format(date2);
System.out.println("排序后的時間為:"+format2);
}
來看測試結果圖:
執(zhí)行時間測試結果圖.png
多次執(zhí)行,發(fā)現10w數據插入排序算法只需要1s,當然可能跟計算機CPU有關系,我們發(fā)現插入排序執(zhí)行的效率要高于選擇排序和冒泡排序算法,那么關于插入排序的學習就到這里
