【Day23】[演算法]-插入排序法Insertion Sort

插入排序法(Insertion Sort)，原理是逐一将原始资料加入已排序好资料中，并逐一与已排序好的资料作比较，找到对的位置插入。例如:已有2笔排序好资料，将第3笔资料与前面已排序好的2笔资料作比较，找到对的位置插入，再将第4笔资料与前面已排序好的3笔资料作比较，找到对的位置插入，以此类推。

下面利用40 30 60 50 20由小到大排序。

n=5
第2回合与1个数比较，比1次，n-4次
第3回合在2个数比较，比2次，n-3次
第3回合在2个数比较，比3次，n-2次
第4回合在1个数比较，比4次，n-1次

(n-1) + (n-2) + .... + 1 = n(n-1) / 2
平均时间复杂度为: O(n²)

JavaScript

let data = [8,6,10,5,3,9,2,7,4,1]

function InsertSort(array) {
  for (let i = 1; i < array.length; i++) {
    let target = i; 
    for (let j = i - 1; j >= 0; j--) {
      if (array[target] < array[j]) {
        [array[target], array[j]] = [array[j], array[target]]
        target = j;
      } 
    }
  }
  return array;
}
console.log(InsertSort(data))//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Python

#Insertion Sort
data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

def InsertionSort(data):
    n = len(data)
    for i in range(n-1):
        key = data[i+1]
        j = i
        while j >=0 and key < data[j] :
                data[j+1] = data[j]
                j -= 1
        data[j+1] = key
    return data
        
print(InsertionSort(data))
#[23, 23, 29, 34, 55, 66, 67, 78, 78, 79, 88, 89, 92, 96, 96, 100]