排序算法(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
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) $

comments powered by Disqus
Built with Hugo
Theme Stack designed by Jimmy