插入排序法是將陣列中未排序的元素,逐一與排序好的資料作比較。它的時間複雜度是 (O(n^2))。
使用哪種資料結構:Array
arr <- an unsorted array of integers
let len be the length of arr
for i (1 t0 len-1) do
key = arr[i]
j = i-1
while j>=0 && key<arr[j]
arr[j+1] = arr[j]
j--
end while
arr[j+1] = key
end for
debugger
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let key = arr[i] // 第一個未排序的元素
let j = i-1 // 已排序元素的控制器
console.log(key)
while (j>=0 && key<arr[j]) { // 移動出正確位置
arr[j+1] = arr[j]
console.log(arr)
j--
}
arr[j+1] = key // 插入未排序元素
console.log(arr)
}
}
insertionSort([8, 9, 2, 5, 1])