排序算法(Swift实现)

简单选择排序

算法描述: 将初始序列A作为待排序序列,第一趟在A[0]~A[n-1]中找最小元素,与该序列的第一个元素交换,这样子序列A[0]有序,下一趟排序在待排序子序列A[1]~A[n-1]
中进行。第i趟排序在待排序子序列(A[i-1]~A[n-1])中,照最小元素,与该子序列中第一个元素A[i-1]交换。经过n-1趟排序后初始序列有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func swapAB(inout a:Int,inout _ b:Int){
let temp = a
a = b
b = temp
}

func selectSort(inout array:[Int] , n:Int){
for i in 0..<n-1{
var small = i
for var j = i+1 ; j < n ; j++ {
if array[j] < array[small]{
small = j
}
}
if i < small{
swapAB(&array[i], &array[small])
}
}
}

时间复杂度为 $ \theta(n^2) $

插入排序

算法描述: 对于少量元素的排序,插入排序是一个有效的算法。插入排序的方式类似平时打扑克牌的时候排序自己手中的扑克牌。开始时,我们左手中没有牌,桌上有洗好的扑克牌,我们抓取一张扑克牌并放入左手的正确位置。为了找到一张扑克牌的正确位置,我们从右到左将它与手中的每张牌进行比较,左手上的牌总是排序好的,而这些牌原来都是桌上牌堆中顶部的牌,当我们抓完牌时,左手中的牌自然是有顺序的。

1
2
3
4
5
6
7
8
9
10
11
12
func insertionSort(inout array:[Int]){
for var j=1;j<array.count;j++ { // n次
let key = array[j] // (n - 1)次

var i = j - 1; // (n - 1)次
while i >= 0 && array[i] > key{ // (n + 1)n / 2次 (最坏情况)
array[i+1] = array[i] // (n - 1)n / 2次 (最坏情况)
i = i - 1 // (n - 1)n / 2次 (最坏情况)
}
array[i+1]=key // (n - 1)次
}
}

$f(n) = n + n-1 + n-1 + (n+1)n/2 + (n-1)n + n-1$

$f(n) = an^2+bn+c$

时间复杂度为:$ \theta(n^2) $(最坏情况)

归并排序

算法描述 对于两堆已经分别排序好的扑克牌A1,A2,从上往下递增排列,分别比较两堆牌的顶层一张牌,将较小的牌放到第三堆A3里,再次比较A1和A2的最顶层的牌,较小的牌放到A3底部。依此类推,最后将剩下的牌一次放到A3底部。最后A3将得到一个排好序的扑克牌堆。实现归并排序;归并排序算法分为两步,第一步:先将原来的数据表分成排好序的子表,然后调用Merge对子表进行归并,使之成为有序表。归并排序过程如下图:

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
28
29
30
31
32
33
34
35
36
37
38
func merge(inout array:[Int],first:Int,mid:Int,last:Int){
var tempArray = Array<Int>()
var indexA = first
var indexB = mid
while indexA < mid && indexB < last {
if array[indexA] < array[indexB]{
tempArray.append(array[indexA])
indexA++
}else{
tempArray.append(array[indexB])
indexB++
}
}

while indexA < mid {
tempArray.append(array[indexA])
indexA++
}

while indexB < last{
tempArray.append(array[indexB])
indexB++
}
var index = 0
for item in tempArray{
array[first + index] = item
index++
}
}

func mergeSort(inout array:[Int],first:Int,last:Int){
if first+1 < last{
let mid = (first + last)/2
mergeSort(&array, first: first, last: mid)
mergeSort(&array, first: mid, last: last)
merge(&array, first: first, mid: mid, last: last)
}
}

时间复杂度为 $ \theta(nlgn) $

冒泡排序

算法描述: 冒泡排序是一种流行但低效的排序算法,作用是反复的交换相邻的未按次序排列的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
func bubbleSort(inout array:[Int],n:Int){
var i = n - 1
while i > 0{
var last = 0
for j in 0..<i{
if array[j+1] < array[j]{
swapAB(&array[j], &array[j+1])
last = j
}
i = last
}
}
}

时间复杂度$ \theta(n^2) $(最坏情况)

快速排序

算法描述: 设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。

一趟快速排序的算法是:

  • 设置两个变量i、j,排序开始的时候:i=0,j=N-1;
  • 以第一个数组元素作为关键数据,赋值给key,即key=A[0];
  • 从j开始向前搜索,即由后开始向前搜索(j–),找到第一个小于key的值A[j],将A[j]和A[i]互换;
  • 从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;
  • 重复第3、4步,直到i=j;(3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
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
28
29
30
func swapAB(inout a:Int,inout _ b:Int){
let temp = a
a = b
b = temp
}
func quickSort(inout array:[Int],low:Int,high:Int){
if low < high{
var l = low
var h = high
let key = array[low]
repeat{
repeat {
l++
}while l < high && array[l] < key

repeat{
h--
}while h >= low && array[h] > key

if l < h{
swapAB(&array[l], &array[h])
}
}while l < h
if low < h{
swapAB(&array[low], &array[h])
}
quickSort(&array, low: low, high: h)
quickSort(&array, low: h+1, high: high)
}
}

时间复杂度 $\theta(n^2) $(最坏情况)

平均时间复杂度为 $ \theta(nlgn) $

Lei.Pan wechat
subscribe to my blog by scanning my public wechat account
万一有人想不开呢?