算法思想
插入排序的方式類似平時打撲克牌的時候排序自己手中的撲克牌。開始時，我們左手中沒有牌，桌上有洗好的撲克牌，我們抓取一張撲克牌并放入左手的正確位置。為了找到一張撲克牌的正確位置，我們從右到左將它與手中的每張牌進行比較，左手上的牌總是排序好的，而這些牌原來都是桌上牌堆中頂部的牌，當我們抓完牌時，左手中的牌自然是有順序的。
之所以叫插入排序，不是為別的，正是因為該算法的核心就是將無序的元素插入排好序的部分。
插入排序的核心思想即在于劃分已排序和未排序，將每個待排序的元素逐個與已排序的元素比較，找出恰當的插入位置，插入元素，循環操作至結束
這里是一張插入排序的使用流程，在寫代碼前先感受一下。
我們以一維數組作為待排序的數據源，整個數組的以第一個待排序的元素為分水嶺，前半部分為已排好序的，后半部分是等待排序的； 開始排序時，從第二個元素開始循環開始，由于需要記錄當前待排序的元素，我們引入一個變量記錄分水嶺的下標，也就是下面源碼內的變量i； 比較的過程比較直接，從分水嶺往前，逐一比較值的大小，沒找到需要插入的位置時向后移動元素，知道找到位置插入元素；
實現代碼
1.由小到大排序：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
func insertionSortBigger(var array: Array<Int>) -> Array<Int>{ for(var j = 1 ; j<array.count ; j++){//從第二個開始向前對比插入 let key = array[j] //記錄要比較的值 var i = j-1 while(i>=0 && array[i]>key){//如果key較小，那么現有的位置向后移，為key空出位置 array[i+1] = array[i] //移位 i-- } array[i+1] = key } return array} |
2.由大到小排序：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
func insertionSortSmaller(var array: Array<Int>) -> Array<Int>{ for(var j = 1 ; j<array.count ; j++){//從第二個開始向前對比插入 let key = array[j] //記錄要比較的值 var i = j-1 while(i>=0 && array[i]<key){//如果key較大，那么現有的位置向后移，為key空出位置 array[i+1] = array[i] //移位 i-- } array[i+1] = key } return array} |
