IT日常-演算法排序(插入排序)

前言

另一種基本演算法為:插入排序

排序演算法-插入排序

邏輯說明:

與泡沫排序不同的是:

1.第二層迴圈是利用第一層給的索引，做遞減的方式來把小於第一層迴圈索引內的數列先做排序。

2.隨著第一層迴圈新增的索引變數，在第二層迴圈中把每個新的數字加進來後再插入已經排序好的位置中。

範例陣列為:524613

第一層迴圈:

從陣列的索引變數: x 為基準，用comparedBox 儲存陣列[x]代表的值後，開始用第二層迴圈的值做對比移動

第二層迴圈:

透過小於comparedBox 的每個數字比較後把較大的數字一直往右移，把comparedBox 插入適合的索引位置的實作過程，可看以下範例了解實際交換的過程(以C#為範例)

程式碼範例:

public List<int> Sort(List<int> list) 
{ 
	for (var x = 1; x < list.Count ; x++) 
	{ 
		var y = x; 
		var comparedBox = list[x]; 
		while (y >= 1 && comparedBox < list[y-1]) 
		{ 
			list[y] = list[y-1]; 
			y--; 
		} 
		list[y] = comparedBox; 
	} 
	return list; 
}

結語

時間複雜度: O(n²)

空間複雜度: θ(1) (不需要額外的陣列去存資料)

參考資料

基礎演算法系列 — 你只會用 built-in function 來排序嗎

Algorithm 演算法排序筆記