正文

快速排序算法在Swift编程中的几种代码实现示例

︶ㄣSDDLL学院 メ
SDDLL学院V管理员 / 阅读
0705
快速排序是一种不稳定的排序,存在着优化空间,这里我们来看快速排序算法在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，不稳定排序

辅助空间

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
}

经典快排

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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)
}

测试代码:

?
1
2
3
4
5
6
7
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)")

快速排序算法在Swift编程中的几种代码实现示例

极简版本    

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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)