疾速排序算法在Swift編程中的幾種代碼完成示例

疾速排序算法在Swift編程中的幾種代碼完成示例。本站提示廣大學習愛好者：（疾速排序算法在Swift編程中的幾種代碼完成示例）文章只能為提供參考，不一定能成為您想要的結果。以下是疾速排序算法在Swift編程中的幾種代碼完成示例正文

總所周知 疾速排序由於排序效率在同為O(N*logN)的幾種排序辦法中效率較高，因而常常被采用。
根本原理是:
數組a = [1,3,5,7,6,4,2]
1 選定一個 基准 a[0]
2 把比 a[0]小的放右邊，比a[0]大的放左邊. 中綴遞歸假如少於兩個數字 則不執行。
3 然後再辨別對兩邊 執行 1，2，3操作。
對疾速排序 的 想法
1 在待排序元素 大局部是有序的狀況下， 速度 十分很快。
2 在最差的狀況下，速度就很慢了。 相當於冒泡了
3 所以 快排的 優化， 定基准 十分重要，例如待排序是有序的，基准定在兩頭，xiao'lv
4 時間復雜度為nlogn，不波動排序

輔佐空間

func quickSort(data:[NSInteger])->[NSInteger]{
  if data.count<=1 {
    return data
  }

  var left:[NSInteger]=[]
  var right:[NSInteger]=[]
  let pivot:NSInteger=data[data.count-1]
  for index in 0..<data.count-1 {
    if data[index]<pivot {
      left.append(data[index])
    }else{
      right.append(data[index])
    }
  }

  var result=quickSort(left)
  result.append(pivot)
  let rightResult=quickSort(right)
  result.appendContentsOf(rightResult)
  return result
}

經典快排

func partition(inout data:[NSInteger],low:NSInteger,high:NSInteger) -> NSInteger {

  let root = data[high]
  var index = low
  for i in low...high {
    if data[i]<root {
      if i != index {
        swap(&data[i], &data[index])
      }
      index = index+1
    }
  }

  if high != index {
    swap(&data[high], &data[index])
  }
  return index
}

func quickSort(inout data:[NSInteger],low:NSInteger,high:NSInteger) -> Void {
  if low>high {
    return
  }
  let sortIndex = partition(&data, low: low, high: high)
  quickSort(&data, low: low, high: sortIndex-1)
  quickSort(&data, low: sortIndex+1, high: high)
}

測試代碼:

var data:[NSInteger] = [1,2,3,2,4,8,9,10,19,0]
var result=quickSort(data)
print("FlyElephant方案1:-\(result)")

var arr:[NSInteger] = [10,3,17,8,5,2,1,9,5,4]
quickSort(&arr, low: 0, high: arr.count-1)
print("FlyElephant方案2:-\(arr)")

極簡版本    

 import UIKit
   extension Array {
     var decompose : (head: Element, tail: [Element])? {
       return (count > 0) ? (self[0], Array(self[1..<count])) : nil
     }
   }

   func qsortDemo(input: [Int]) -> [Int] {
     if let (pivot, rest) = input.decompose {
       let lesser = rest.filter { $0 < pivot }//這裡是小於於pivot基數的分紅一個數組
       let greater = rest.filter { $0 >= pivot }//這裡是大於等於pivot基數的分紅一個數組
       return qsortDemo(lesser) + [pivot] + qsortDemo(greater)//遞歸 拼接數組
     } else {
       return []
     }
   }

   var a:[Int] = [1,2,4,6,2,4,3,7,8]
   qsortDemo(a)