Swift中排序算法的簡單取舍詳解

更新時間：2018年03月14日 10:04:13 作者：Castie1

對于排序算法, 通常簡單的, 為大家所熟知的有, 選擇排序, 冒泡排序, 快速排序, 當(dāng)然還有哈希, 桶排序之類的, 本文僅比較最為常見的選擇, 冒泡和快排，文中通過示例代碼介紹的非常詳細，需要的朋友可以參考借鑒，下面來一起看看吧。

前言

對于iOS開發(fā)者來說, 算法的實現(xiàn)過程其實并不怎么關(guān)心, 因為只需要調(diào)用高級接口就可以得到系統(tǒng)最優(yōu)的算法, 但了解輪子背后的原理才能更好的取舍, 不是么?下面話不多說了，來一起看看詳細的介紹吧。

選擇排序

我們以[9, 8, 7, 6, 5]舉例.

[9, 8, 7, 6, 5]

第一次掃描, 掃描每一個數(shù), 如比第一個數(shù)小則交換, 直到找到最小的數(shù), 將其交換至下標0.

[8, 9, 7, 6, 5]
[7, 9, 8, 6, 5]
[6, 9, 8, 7, 5]
[5, 9, 8, 7, 6]

第二次掃描, 由于確定了第一個數(shù), 則從第二個數(shù)開始掃描, 邏輯同上取得次小的數(shù)交換至下標1.

[5, 8, 9, 7, 6]
[5, 7, 9, 8, 6]
[5, 6, 9, 8, 7]

第三次掃描, 跳過兩個數(shù), 從第三個數(shù)開始掃描, 并交換取得下標2.

[5, 6, 8, 9, 7]
[5, 6, 7, 9, 8]

第四次掃描, 套用上述邏輯取得下標3.

[5, 6, 7, 8, 9]

由于最后只有一位數(shù), 不需要交換, 則無需掃描.

了解了邏輯, 我們來看代碼該怎么寫;

func selectSort(list: inout [Int]) {
 let n = list.count
 for i in 0..<(n-1) {
 var j = i + 1
 for _ in j..<n {
  if list[i] > list[j] {
  list[i] ^= list[j]
  list[j] ^= list[i]
  list[i] ^= list[j]
  }
  j += 1
 }
 }
}

外層循環(huán)取從0掃描到n-1, i代表了掃描推進的次數(shù).

內(nèi)層循環(huán)從i+1, 掃描到最后一位, 逐個比較, 如果比i小則交換.

選擇排序(優(yōu)化)

上述我們通過了非常簡單的邏輯闡述了選擇排序, 果然, 算法沒有想象中難吧. 接下來, 我們來看看如何優(yōu)化這個排序算法.

我們同樣以[9, 8, 7, 6, 5]舉例.

[9, 8, 7, 6, 5]

第一次掃描, 和之前一樣掃描, 但只記住最小值的下標, 退出內(nèi)層循環(huán)時交換.

[5, 8, 7, 6, 9]

第二次掃描, 確定第一位最小值后推進一格, 邏輯同上進行交換.

[5, 6, 7, 8, 9]

我們可以明顯的看到優(yōu)化的效果, 交換的次數(shù)降低了, 因為我們不是每次交換數(shù)值, 而是用指針記錄后跳出內(nèi)層循環(huán)后進行交換.

我們來看下代碼該如何優(yōu)化:

func optimizationSelectSort(list: inout [Int]) {
 let n = list.count
 var idx = 0
 for i in 0..<(n - 1) {
 idx = i;
 var j = i + 1
 for _ in j..<n {
  if list[idx] > list[j] {
  idx = j;
  }
  j += 1
 }
 if idx != i {
  list[i] ^= list[idx]
  list[idx] ^= list[i]
  list[i] ^= list[idx]
 }
 }
}

通過idx記錄最小值的下標, 如果下標和當(dāng)前值不等則交換數(shù)值.

冒泡排序

接下來我們來看冒泡排序, 同樣以[9, 8, 7, 6, 5]為例.

[9, 8, 7, 6, 5]

第一次掃描, 同樣掃描每一個數(shù), 不同的是, 有兩個指針同時向前走, 如果n>n-1則交換. 確定最末值為最大值.

[8, 9, 7, 6, 5]
[8, 7, 9, 6, 5]
[8, 7, 6, 9, 5]
[8, 7, 6, 5, 9]

第二次掃描, 從頭進行掃描, 由于以確定最末尾為最大值, 則少掃描一位.

[7, 8, 6, 5, 9]
[7, 6, 8, 5, 9]
[7, 6, 5, 8, 9]

第三次掃描, 和上述邏輯相同.

[6, 7, 5, 8, 9]
[6, 5, 7, 8, 9]

第四次掃描, 得到排序完成的值.

[5, 6, 7, 8, 9]

上述可能不好理解, 多看幾遍應(yīng)該可以.

如果還是理解不能, 我們就來看看代碼吧;

func popSort(list: inout [Int]) {
 let n = list.count
 for i in 0..<n-1 {
 var j = 0
 for _ in 0..<(n-1-i) {
  if list[j] > list[j+1] {
  list[j] ^= list[j+1]
  list[j+1] ^= list[j]
  list[j] ^= list[j+1]
  }
  j += 1
 }
 }
}

外層循環(huán)同樣從0掃描到n-1, 這點不贅述.

內(nèi)層循環(huán)從頭也就是0掃描到n-1-i, 也就是每次掃描少掃一位, 應(yīng)為每次都會確定最末位為最大值.

冒泡排序(優(yōu)化)

冒泡排序的優(yōu)化就沒有選擇排序的優(yōu)化那么給力了, 還有可能產(chǎn)生負優(yōu)化, 慎用!!

這次我們用[5, 6, 7, 9, 8]來舉例.

--- scope of: popsort ---
[5, 6, 7, 9, 8]
[5, 6, 7, 8, 9]








--- scope of: opt_popsort ---
[5, 6, 7, 9, 8]
[5, 6, 7, 8, 9]

這個優(yōu)化并不是特別直觀, 最好運行我的源碼. 優(yōu)化來自于如果已經(jīng)排序完成則不用掃描空轉(zhuǎn). 上面的空行就是空轉(zhuǎn).

func optimizationPopSort(list: inout [Int]) {
 let n = list.count
 for i in 0..<n-1 {
  var flag = 0
  var j = 0
  for _ in 0..<(n-1-i) {
   if list[j] > list[j+1] {
    list[j] ^= list[j+1]
    list[j+1] ^= list[j]
    list[j] ^= list[j+1]
    flag = 1
   }
   j += 1
  }
  if flag == 0 {
   break
  }
 }
}

就是加了一個標志位來判斷是否跳出掃描.

快速排序

快速排序, 不是特別好舉例, 但是最重要的一個排序.

func quickSort(list: inout [Int]) {
 func sort(list: inout [Int], low: Int, high: Int) {
  if low < high {
   let pivot = list[low]
   var l = low; var h = high
   while l < h {
    while list[h] >= pivot && l < h {h -= 1}
    list[l] = list[h]
    while list[l] <= pivot && l < h {l += 1}
    list[h] = list[l]
   }
   list[h] = pivot
   sort(list: &list, low: low, high: l-1)
   sort(list: &list, low: l+1, high: high)
  }
 }
 sort(list: &list, low: 0, high: list.count - 1)
}

我們直接看代碼就能看出, 我們將下標0作為標尺, 進行掃描, 比其大的排右面, 比其小的排左邊, 用遞歸的方式進行排序而成, 由于一次掃描后同時進行了模糊排序, 效率極高.

排序取舍

我們將上述所有的排序算法和系統(tǒng)的排序進行了比較, 以10000個隨機數(shù)為例.

scope(of: "sort", execute: true) {
 scope(of: "systemsort", execute: true, action: {
  let list = randomList(10000)
  timing {_ = list.sorted()}
//  print(list.sorted())
 })
 
 scope(of: "systemsort2", execute: true, action: {
  let list = randomList(10000)
  timing {_ = list.sorted {$0 < $1}}
//  print(list.sorted {$0 < $1})
 })
 
 scope(of: "selectsort", execute: true, action: {
  var list = randomList(10000)
  timing {selectSort(list: &list)}
//  print(list)
 })

 scope(of: "opt_selectsort", execute: true, action: {
  var list = randomList(10000)
  timing {optimizationSelectSort(list: &list)}
//  print(list)
 })

 scope(of: "popsort", execute: true, action: {
  var list = randomList(10000)
  timing {popSort(list: &list)}
//  print(list)
 })

 scope(of: "opt_popsort", execute: true, action: {
  var list = randomList(10000)
  timing {optimizationPopSort(list: &list)}
//  print(list)
 })

 scope(of: "quicksort", execute: true, action: {
  var list = randomList(10000)
  timing {quickSort(list: &list)}
//  print(list)
 })
}

--- scope of: sort ---
--- scope of: systemsort ---
timing: 0.010432243347168
--- scope of: systemsort2 ---
timing: 0.00398015975952148
--- scope of: selectsort ---
timing: 2.67806816101074
--- scope of: opt_selectsort ---
timing: 0.431572914123535
--- scope of: popsort ---
timing: 3.39597702026367
--- scope of: opt_popsort ---
timing: 3.59421491622925
--- scope of: quicksort ---
timing: 0.00454998016357422

我們可以看到, 其中我寫的快排是效率最高的, 和系統(tǒng)的排序是一個數(shù)量級的, 而選擇比冒泡的效率要高, 而令人疑惑的是同樣是系統(tǒng)的排序加上{$0 < $1}比較規(guī)則, 效率會有數(shù)量級的提升.

現(xiàn)在大家知道如何選擇排序算法了么?

二分搜索

@discardableResult func binSearch(list: [Int], find: Int) -> Int {
 var low = 0, high = list.count - 1
 while low <= high {
  let mid = (low + high) / 2
  if find == list[mid] {return mid}
  else if (find > list[mid]) {low = mid + 1}
  else {high = mid - 1}
 }
 return -1;
}

@discardableResult func recursiveBinSearch(list: [Int], find: Int) -> Int {
 func search(list: [Int], low: Int, high: Int, find: Int) -> Int {
  if low <= high {
   let mid = (low + high) / 2
   if find == list[mid] {return mid}
   else if (find > list[mid]) {
    return search(list: list, low: mid+1, high: high, find: find)
   }
   else {
    return search(list: list, low: low, high: mid-1, find: find)
   }
  }
  return -1;
 }
 return search(list: list, low: 0, high: list.count - 1, find: find)
}

二分搜索的原理就不多說了, 就是折半折半再折半, 這種搜索算法的關(guān)鍵就是要有序, 所以配合上合適的排序算法才是最重要的!

源碼下載：github 或者本地下載

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，如果有疑問大家可以留言交流，謝謝大家對腳本之家的支持。

您可能感興趣的文章: