經典排序算法（六） —— InsertionSort 插入排序

目錄

簡介

排序過程

實作

複雜度

插入排序的算法，同樣描述了一種簡單直覺的排序。

它的工作原理是：建構一個有序序列。對于未排序資料，在已排序序列中從後向前掃描，找到相應位置并插入。

因為需要雙重循環，是以時間複雜度均為O(n^2)。排序過程中，隻需要額外的常數空間，是以空間複雜度均為O(1)。