《算法》学习——快速排序

前言

提前说明一下吧。
这篇文章只是记录自己学习《算法》——快速排序的过程，只会记录自己对算法实现过程的基本理解并不会对算法的时间成本等做详细的讨论。

快速排序简介

排序算法可能是应用最广泛的算法了，它的特点是简单、适用于不同的输入数据并且在一般的应用中比其他的排序算法要快。快速排序采用的也是分治思想，但是与归并排序不同的是快速排序是原地排序并不需要使用辅助数组能节省更多的内存资源。

基本算法

快速排序是将一个数组分成两个子数组，并将两个子数组独立的排序。数组的切分与归并排序有很大的不同，快速排序是找出一个元素作为基准，然后确定这个基准元素在数组中的位置，在这个过程中使基准左边的元素都不大于它右边的元素都不小于它。快速排序就是递归的调用切分的方法来完成排序的。

实现切分的方法

一般的策略是随意的去a[lo]作为切分的基准元素，然后从数组的左端开始向右扫描直到找到一个大于等于它的元素，再从数组的右端向左扫描直到找到一个小于等于它的元素。这两个元素即为没有排定的，交换他们的位置然后继续扫描。直到左右两个扫描的指针相遇。这时我们只需要将a[lo]与左边子数组最后的元素a[j]交换 j 即为切分的位置。

快排切分图.png

切分的代码实现

※注 exch为交换数组指定位置的元素，不再实现了

func partition(a:inout[Int],lo:Int,hi:Int) -> Int {
    var i = lo///左指针
    var j = hi+1///右指针
    let v = a[lo]///切分的基准元素
    while true {
        i = i + 1
        /**向右移动 i 指针直到a[i]大于等于v(基准元素)*/
        while a[i]<v {
            if i == hi {///防止越界
                break
            }
            i = i + 1
        }
        j = j - 1
        /**向左移动 j 指针 直到a[j]小于等于v*/
        while a[j]>v {
            if j == lo {///防止越界
                break
            }
            j = j - 1
        }
        /**i >= j 即是两个指针已经相遇了*/
        if i>=j {
            break
        }
      /**交换 i 与 j 使i左边的元素都小于基准元素，
          j右边的元素都大于基准元素 */
        exch(a: &a, i: i, j: j);
    }
    /**将基准元素与 j 交换位置，此时 基准元素a[lo]的位置排定
        j 即为切分位置*/
    exch(a: &a, i: lo, j: j);
    return j
}

排序算法的实现

切分的方法实现之后 我们就可以递归的调用切分方法来实现排序了。

func quickSort(a:inout[Int],lo:Int,hi:Int) -> Void {
    if lo>=hi {
        return
    }
    /**
    获取数组切分的位置，在切分过程中将切分基准元素的位置排定
    */
    let j = partition(a: &a, lo: lo, hi: hi);
    quickSort(a: &a, lo: lo, hi: j)
    quickSort(a: &a, lo: j+1, hi: hi)
}

现在就可以使用我们Swift版的快速排序来对数组进行排序了。

let N = 100
var a = [Int]()
for i in 0..<N {
    a.append(i)
}
a = a.shuffle()
quickSort(a: &a, lo: 0, hi: N-1)
print(a);

关于保持随机性

在上面的排序代码中，我们在调用快排方法quickSort之前数组a调用了自身的shuffle方法，这个方法的作用是将数组元素的顺序打乱。然而Swift中并没有为我们提供这样一个方法，下面贴上本人百度的方法。感兴趣的童鞋可以去学习下简书-Swift - Array 扩展 shuffle()，随机排序

extension Array {

    public func shuffle() -> Array {
        var list = self
        for index in 0..<list.count {
            let newIndex = Int(arc4random_uniform(UInt32(list.count-index))) + index
            if index != newIndex {
                swap(&list[index], &list[newIndex])
            }
        }
        return list
    }
    
}

※保持随机的重要性
快速排序最好的情况是每次都能将数组对半分。但是在切分不平衡时排序过程可能会变的极为低效。例如，第一次从最小的元素切分，第二次从第二小的元素切分。这就导致一个大子数组需要切分很多次。我们在快速排序之前将数组随机排序的原因就是要避免这种情况。

To be continued