快捷導(dǎo)航

簡單理解插入排序算法及Swift版的代碼示例

更新時(shí)間：2016年07月06日 11:11:36 作者：yoyo

插入排序算法可以在已排序的序列中將要插入的元素和原有元素保持有序,這里我們來簡單理解插入排序算法及Swift版的代碼示例,需要的朋友可以參考下

算法思想
插入排序的方式類似平時(shí)打撲克牌的時(shí)候排序自己手中的撲克牌。開始時(shí)，我們左手中沒有牌，桌上有洗好的撲克牌，我們抓取一張撲克牌并放入左手的正確位置。為了找到一張撲克牌的正確位置，我們從右到左將它與手中的每張牌進(jìn)行比較，左手上的牌總是排序好的，而這些牌原來都是桌上牌堆中頂部的牌，當(dāng)我們抓完牌時(shí)，左手中的牌自然是有順序的。
之所以叫插入排序，不是為別的，正是因?yàn)樵撍惴ǖ暮诵木褪菍o序的元素插入排好序的部分。
插入排序的核心思想即在于劃分已排序和未排序，將每個(gè)待排序的元素逐個(gè)與已排序的元素比較，找出恰當(dāng)?shù)牟迦胛恢?，插入元素，循環(huán)操作至結(jié)束
這里是一張插入排序的使用流程，在寫代碼前先感受一下。

201676110656609.jpg (735×185)

我們以一維數(shù)組作為待排序的數(shù)據(jù)源，整個(gè)數(shù)組的以第一個(gè)待排序的元素為分水嶺，前半部分為已排好序的，后半部分是等待排序的；開始排序時(shí)，從第二個(gè)元素開始循環(huán)開始，由于需要記錄當(dāng)前待排序的元素，我們引入一個(gè)變量記錄分水嶺的下標(biāo)，也就是下面源碼內(nèi)的變量i；比較的過程比較直接，從分水嶺往前，逐一比較值的大小，沒找到需要插入的位置時(shí)向后移動(dòng)元素，知道找到位置插入元素；

201676110724690.png (507×157)

實(shí)現(xiàn)代碼
1.由小到大排序：

func insertionSortBigger(var array: Array<Int>) -> Array<Int>{
  for(var j = 1 ; j<array.count ; j++){//從第二個(gè)開始向前對比插入
    let key = array[j] //記錄要比較的值
    var i = j-1
    while(i>=0 && array[i]>key){//如果key較小，那么現(xiàn)有的位置向后移，為key空出位置
      array[i+1] = array[i] //移位
      i--
    }
    array[i+1] = key
  }
  return array
}

2.由大到小排序：

func insertionSortSmaller(var array: Array<Int>) -> Array<Int>{
  for(var j = 1 ; j<array.count ; j++){//從第二個(gè)開始向前對比插入
    let key = array[j] //記錄要比較的值
    var i = j-1
    while(i>=0 && array[i]<key){//如果key較大，那么現(xiàn)有的位置向后移，為key空出位置
      array[i+1] = array[i] //移位
      i--
    }
    array[i+1] = key
  }
  return array
}

您可能感興趣的文章: