視頻+圖文+影片 詳解插入排序(輕松易理解系列)

• 一、視頻講解插入排序
• 二、插入排序的思想
• 三、插入排序的影片演示及思路分析
  • 影片演示：
  • 思路分析：以7,3,22,15,8為例
    • 第一次排序：拿出無序表中的第1個元素3，與有序表的元素7進行比較
    • 第二次排序：拿出無序表中的第1個元素22，與有序表的元素3,7進行比較
    • 第三次排序：拿出無序表中的第1個元素15，與有序表的元素3,7,22進行比較
    • 第四次排序：拿出無序表中的第1個元素8，與有序表的元素3,7,15,22進行比較
• 四、插入排序的代碼+代碼優化+代碼詳解
  • 代碼--————多個while回圈分別控制排序：
  • 結果：
  • 優化代碼--————for回圈嵌套while回圈控制排序：
  • 優化分析：
  • 代碼：
  • 結果：
  • 代碼詳解（優化版本）:以7,3,22,15,8為例
    • 第一次排序時:
    • 第二次排序時:
    • 第三次排序時:
    • 第四次排序時:

一、視頻講解插入排序

點擊這里去B站觀看視頻~~

二、插入排序的思想

• 把n個待排序的元素看成是一個有序表和一個無序表
• 第一輪排序時，有序表中只含一個元素，無序表中包含n-1個元素
• 排序程序中，每次從無序表中取出第一個元素，去和有序表中的每個元素進行比較
• 找到適合自己的位置并插入，使自己成為有序表

三、插入排序的影片演示及思路分析

影片演示：

橙色的數字：有序表中的數字
粉色的數字：每輪無序表的第一個數
綠色的數字：有序表中需與無序表粉色數字進行比較的數

思路分析：以7,3,22,15,8為例

為了便于理解代碼，在這里我們需用兩個變數：

• insertValue：每輪排序中無序表中的第一個數字即待插入的數
• insertIndex：從此陣列下標開始，為insertValue找合適的位置 【下標需要大于等于0的條件要遵守】

第一次排序：拿出無序表中的第1個元素3，與有序表的元素7進行比較

原始陣列：7,3,22,15,8

• 3<7,所以arr[0]=7需要向后移一位，即arr[1]=7
• 此時3找到合適的位置【即下標為0的位置】，進行插入，

排序結果： 3,7,22,15,8

第二次排序：拿出無序表中的第1個元素22，與有序表的元素3,7進行比較

原始陣列：3,7,22,15,8

• 22>7,所以22不需要移動，
• 此時22所在的位置就是其合適的位置【即下標為2的位置】，

排序結果： 3,7,22,15,8

第三次排序：拿出無序表中的第1個元素15，與有序表的元素3,7,22進行比較

原始陣列：3,7,22,15,8

• 15<22,所以arr[2]=22需要向后移一位，即arr[3]=22
• 而15>7，所以此時15找到合適的位置【即下標為2的位置】，進行插入，

排序結果： 3,7,15,22,8

第四次排序：拿出無序表中的第1個元素8，與有序表的元素3,7,15,22進行比較

原始陣列：3,7,15,22,8

• 8<22,所以arr[3]=22需要向后移一位，即arr[4]=22
• 8<15,所以arr[2]=15需要向后移一位，即arr[3]=15
• 而8>7，所以此時8找到合適的位置【即下標為2的位置】，進行插入，

排序結果： 3,7,15,22,8

四、插入排序的代碼+代碼優化+代碼詳解

代碼--————多個while回圈分別控制排序：

package Sort;

import java.util.Arrays;

public class InsertSort {

	public static void main(String[] args) {
		int arr[] = { 7, 3, 22, 15, 8 };
		int insertValue = https://www.cnblogs.com/Qpgshare/p/0; //（無序表的第一個值）待插入的值
		int insertIndex = 0; //從這里開始查找待插入值的下標

		 //第一次排序
		insertValue = 3;
		insertIndex = 1-1;
		while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
			arr[insertIndex + 1] = arr[insertIndex]; //將7后移一個位置,arr[1]=7
			insertIndex--;
		}
		 //退出while回圈，待插入的數的下標確定
		arr[insertIndex + 1] = insertValue;
		System.out.println("第一次排序的結果為："+Arrays.toString(arr));
		
		 //第二次排序
				insertValue = https://www.cnblogs.com/Qpgshare/p/22;
				insertIndex = 2-1;
				while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
					arr[insertIndex + 1] = arr[insertIndex];
					insertIndex--;
				}
				 //退出while回圈，待插入的數的下標確定
				arr[insertIndex + 1] = insertValue;
				System.out.println("第二次排序的結果為："+Arrays.toString(arr));
				
				 //第三次排序
				insertValue = https://www.cnblogs.com/Qpgshare/p/15;
				insertIndex = 3-1;
				while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
					arr[insertIndex + 1] = arr[insertIndex]; //將22后移一個位置,arr[3]=22
					insertIndex--;
				}
				 //退出while回圈，待插入的數的下標確定
				arr[insertIndex + 1] = insertValue;
				System.out.println("第三次排序的結果為："+Arrays.toString(arr));
				
				 //第四次排序
				insertValue = https://www.cnblogs.com/Qpgshare/p/8;
				insertIndex = 4-1;
				while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
					//將22后移一個位置即arr[4]=22;15也后移一個位置即arr[3]=15
					arr[insertIndex + 1] = arr[insertIndex]; 
					insertIndex--;
				}
				 //退出while回圈，待插入的數的下標確定
				arr[insertIndex + 1] = insertValue;
				System.out.println("第四次排序的結果為："+Arrays.toString(arr));

	}

}

結果：

優化代碼--————for回圈嵌套while回圈控制排序：

優化分析：

根據下表紅色資料部分，我們可以看出：

• 可以用一個for回圈嵌套在while回圈外，控制1-4的變化

代碼：

package Sort;

import java.util.Arrays;

public class InsertSort {

	public static void main(String[] args) {
		int arr[] = { 7, 3, 22, 15, 8 };
		int insertValue = https://www.cnblogs.com/Qpgshare/p/0; //（無序表的第一個值）待插入的值
		int insertIndex = 0; //從這里開始查找待插入值的下標
		for (int i = 1; i < arr.length; i++) {
			insertValue = arr[i];
			insertIndex = i - 1;
			while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
				arr[insertIndex + 1] = arr[insertIndex]; 
				insertIndex--;
			}
			 //退出while回圈，待插入的數的下標確定
			if (insertIndex + 1 != i) {//如果insertIndex + 1 != i說明此數在正確位置上不用交換
				arr[insertIndex + 1] = insertValue;
			}
			System.out.println("第" + i + "次排序的結果為：" + Arrays.toString(arr));
		}
	}

}

結果：

代碼詳解（優化版本）:以7,3,22,15,8為例

第一次排序時:

• i=1,1<arr.length=5
• insertValue=arr[i]=arr[1]=3,
• insertIndex=i-1=1-1=0
• insertIndex=0且insertValue=https://www.cnblogs.com/Qpgshare/p/3 滿足while回圈的條件while (insertIndex >= 0 && insertValue < arr[insertIndex])進入while回圈

while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
				arr[insertIndex + 1] = arr[insertIndex]; 
				insertIndex--;
			}

• arr[insertIndex+1]=arr[insertIndex]即將原來arr[1]=3換為現在的arr[1]=7

  7,3,22,15,8 -->7,3,22,15,8 --> 3,7,22,15,8

• insertIndex--后InsertIndex=-1
  不滿足while回圈條件，退出while回圈，待插入數：3的位置找到即arr[0]=3

• 因為此時insertIndex=-1，滿足if (insertIndex + 1 != i)進入if分支陳述句

if (insertIndex + 1 != i) {//如果insertIndex + 1 != i說明此數在正確位置上不用交換
				arr[insertIndex + 1] = insertValue;
			}

• 所以arr[insertIndex+1]=insertValue 即arr[0]=3

• 輸出第一次排序的結果：3,7,22,15,8 --> 3,7,22,15,8

第二次排序時:

• i=2,2<arr.length=5
• insertValue=arr[i]=arr[2]=22,
• insertIndex=i-1=2-1=1
• insertIndex=1但insertValue=https://www.cnblogs.com/Qpgshare/p/22>arr[insertIndex]=7
  不滿足while回圈的條件while (insertIndex >= 0 && insertValue < arr[insertIndex])不進入while回圈

while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
				arr[insertIndex + 1] = arr[insertIndex]; 
				insertIndex--;
			}

3,7,22,15,8 --> 3,7,22,15,8

• 因為此時insertIndex=1，不滿足if (insertIndex + 1 != i)不進入if分支陳述句

if (insertIndex + 1 != i) {//如果insertIndex + 1 != i說明此數在正確位置上不用交換
				arr[insertIndex + 1] = insertValue;
			}

• 所以本次排序不發生交換

• 輸出第二次排序的結果：3,7,22,15,8 --> 3,7,22,15,8

第三次排序時:

• i=3,3<arr.length=5
• insertValue=arr[i]=arr[1]=3,
• insertIndex=i-1=3-1=2
• insertIndex=2且insertValue=https://www.cnblogs.com/Qpgshare/p/15 滿足while回圈的條件while (insertIndex >= 0 && insertValue < arr[insertIndex])進入while回圈

while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
				arr[insertIndex + 1] = arr[insertIndex]; 
				insertIndex--;
			}

• arr[insertIndex+1]=arr[insertIndex]即將原來arr[3]=15換為現在的arr[3]=22

  3,7,22,15,8 --> 3,7,22,15,8 --> 3,7,22,22,8

• insertIndex--后InsertIndex=1但insertValue=https://www.cnblogs.com/Qpgshare/p/15>arr[insertIndex]=arr[1]=7

  3,7,22,22,8 --> 3,7,22,22,8

  不滿足while回圈條件，退出while回圈，待插入數：15的位置找到即arr[2]=15

• 因為此時insertIndex=1，滿足if (insertIndex + 1 != i)進入if分支陳述句

if (insertIndex + 1 != i) {//如果insertIndex + 1 != i說明此數在正確位置上不用交換
				arr[insertIndex + 1] = insertValue;
			}

3,7,22,22,8 --> 3,7,15,22,8

• 所以arr[insertIndex+1]=insertValue 即arr[2]=15

• 輸出第三次排序的結果：3,7,15,22,8

第四次排序時:

• i=4,4<arr.length=5
• insertValue=arr[i]=arr[4]=8,
• insertIndex=i-1=4-1=3
• insertIndex=3且insertValue=https://www.cnblogs.com/Qpgshare/p/8 滿足while回圈的條件while (insertIndex >= 0 && insertValue < arr[insertIndex])進入while回圈

while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
				arr[insertIndex + 1] = arr[insertIndex]; 
				insertIndex--;
			}

• arr[insertIndex+1]=arr[insertIndex]即將原來arr[3]=22換為現在的arr[4]=22

  3,7,15,22,8 --> 3,7,15,22,8 --> 3,7,15,22,22

• insertIndex--后InsertIndex=2且insertValue=https://www.cnblogs.com/Qpgshare/p/8 滿足while回圈條件，進入while回圈，

• arr[insertIndex+1]=arr[insertIndex]即將原來arr[3]=22換為現在的arr[3]=15

  3,7,15,22,22 --> 3,7,15,22,22 --> 3,7,15,15,22

• insertIndex--后InsertIndex=1但insertValue=https://www.cnblogs.com/Qpgshare/p/8>arr[insertIndex]=arr[1]=7
  不滿足while回圈條件，退出while回圈，待插入數：8的位置找到即arr[2]=8

• 因為此時insertIndex=1，滿足if (insertIndex + 1 != i)進入if分支陳述句

if (insertIndex + 1 != i) {//如果insertIndex + 1 != i說明此數在正確位置上不用交換
				arr[insertIndex + 1] = insertValue;
			}

3,7,15,15,22 --> 3,7,8,15,22

• 所以arr[insertIndex+1]=insertValue 即arr[2]=8

• 輸出第四次排序的結果：3,7,8,15,22

到此插入排序就講解完了~~

標籤：其他

上一篇：第11屆藍橋杯省賽模擬 單詞加密

下一篇：N皇后問題 回溯非遞回演算法 C++實作2