简单选择排序
算法描述： 将初始序列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
39
|
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) $