使用java程式碼和偽代碼實作插入排序

插入排序介紹：

相信大部分人都打過撲克牌，許多人喜歡發一張牌就拿一張牌到手上，並且按順序來放好牌。開始時我們左手為空，牌在桌上。然後我們每次從桌子上拿走一張牌並將它插入左手中的位置。為了找到一張牌的正確位置，我們從右到左將它與已在手中的每張牌進行比較。

java相關免費影片教學推薦：java免費影片教學

#偽代碼：

INSERTION-SORT(A)	//A是数组
 for j = 2 to A.length
key = A[j]
//(将A[j]插入排序序列A[1..j-1])
i = j - 1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i - 1
A[i+1] = key

java程式碼：

//升序排序
public void InsertSortAscending(int[] A){
		for(int j = 1;j < A.length;j++){
			int key = A[j];
			//将A[j]插入排序序列A[1..j-1]
			int i = j - 1;
			while(i >= 0 && A[i] > key){
				A[j+1] = A[i];
				i = i - 1;
			}
			A[i+1] = key;
		}
}

下面我們來看一下插入排序的運行步驟

用數組A[2,4,7,1,3,6]來舉例子

每次for迴圈中，黃色的長方形是A[j]的值，在第7行的while循環中將它與其左邊的藍色的長方形中的值進行比較。藍色的箭頭指出陣列在第8行向右移動一個位置，黃色的箭頭指出第11行關鍵字被移到的地方。

第一次迴圈：如下圖：

第二次迴圈：如下圖所示：

注意：這裡A[2]大於A[1]，因為A[1]一定是大於A[0]的所以沒必要在比較A[2]與A[1]的大小。 while迴圈因不符合條件會退出。

第三次迴圈：如下圖：

#第四次迴圈：如下圖：

第五次迴圈：如下圖所示：

A陣列此時如圖所示：

第六次循環時j為6不滿足循環j

推薦java相關文章教學：java入門程式

以上是使用java程式碼和偽代碼實作插入排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！