ep004_插入排序的實作和改進

一、基本思路

插入排序的基本思路是把n個待排序的元素看成一個有序清單和一個無序清單，一開始有序清單隻有一個元素，無序清單有n-1個元素，排序過程每次從無序清單中拿出第一個數與前面的有序表中的元素進行大小比較，并且将這個元素插入到有序清單中的适當位置，使之成為新的有序清單。

顧名思義簡而言之就是把前面已經排好序的元素看成一個清單，再把剩下的元素看成一個新的清單，每次把剩下元素的第一個元素插入到有序清單中合适的位置，知道第n個元素。

二、圖解

下面給出一個圖解事例，幫助大家了解。

三、代碼實作

了解了上面的思路分析和圖解事例之後，用Java實作算法很簡單。

//插入排序
	public static void insertSort(int[] arr) {
		int insertVal = 0;
		int insertIndex = 0;

		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
			//這裡我們判斷是否需要指派
			if(insertIndex + 1 != i) {
				arr[insertIndex + 1] = insertVal;
			}
	}
           

四、總結和優化

由此看出，插入排序的時間複雜度是（n^2）

但是如果後面的元素比較小時，比如下面（4、2、5、7、1）這個待排序數列，1在最後面，後移的次數明顯增多，對算法的效率會有影響，需要進行優化，其實優化有就是所謂的希爾排序，下一章将講解希爾排序。