快速排序算法讲解及swift代码实现

菜小编

2018-9-10

数据结构与算法

快速排序算法被称之为20世纪十大算法之一，也是各大公司面试比较喜欢考察的算法。

快速排序算法讲解

快速排序的基本思想是：通过一趟排序将带排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

上述文字摘自《大话数据结构》

它的实现步骤为：

从数列中挑出一个元素（挑选的算法可以是随机，也可以作其他的优化），称为"基准"（pivot）。
重新对数组进行排序：所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面，相同的放两边。
递归地进行分区操作，继续把小于基准值元素的子数列和大于基准值元素的子数列排序。

从上面的描述可以看出，分区操作是快速排序中的核心算法。下面笔者结合实例来描述一下分区操作的过程。

首先拿到初始的数组：[5,4,9,1,3,6,7,8,2]

选择5作为pivot。
从剩下部分的两端开始：左侧1的标记为low，最右侧2的标记为high。
先看j：2 < 5 , 交换5和2，j不变：[2,4,9,1,3,6,7,8,5] ；
再看i：2 < 5 , i ++ ；4 < 5, i++；9 > 5，交换 9 和 5，i不变[2,4,5,1,3,6,7,8,9]。

代码实现

使用Swift的filter函数

因为在Swift中有一个数组的filter函数可以找出数组中符合某范围的一些数值，所以笔者先介绍一个会用该函数的简单的快速排序的实现：

func quickSort0<T: Comparable>(_ array: [T]) -> [T] {
    
    guard array.count > 1 else { return array }
    
    let pivot = array[array.count/2]
    let less = array.filter { $0 < pivot }
    let greater = array.filter { $0 > pivot }
    
    return quickSort0(less) + quickSort0(greater)
}
复制代码

不难看出这里面使用了递归：选中pivot以后，将数组分成了两个部分，最后将它们合并在一起。虽然这里面使用了Swift里面内置的函数来找出符合这两个个部分的元素，但是读者可以通过这个例子更好地理解快速排序的实现方式。

使用取index = 0 的partition函数

除了使用swift内置的filter函数，当然我们也可以自己实现分区的功能，通常使用的是自定义的partition函数。

func _partition(_ array: inout [Int], low: Int, high: Int) -> Int{

    var low       = low
    var high      = high

    let pivotValue = array[low]

    while low < high {

        while low < high && array[high] >= pivotValue {
            high -= 1
        }
        array[low] = array[high]
        
        while low < high && array[low] <= pivotValue {
            low += 1
        }
        array[high] = array[low]
    }

    array[low] = pivotValue
  
    return low
}
复制代码

从代码实现可以看出，最初在这里选择的pivotValue是当前数组的第一个元素。

然后从数组的最右侧的index逐渐向左侧移动，如果值大于pivotValue，那么index-1；否则直接将high与low位置上的元素调换；同样左侧的index也是类似的操作。

该函数执行的最终效果就是将最初的array按照选定的pivotValue前后划分。

那么_partition如何使用呢？

func quickSort1(_ array: inout [Int], low: Int, high: Int){
  
    guard array.count > 1 else { return }
    
    if low < high {        
        let pivotIndex = _partition(&array, low: low, high: high)
        quickSort1(&array, low: low, high: pivotIndex - 1)
        quickSort1(&array, low: pivotIndex + 1, high: high)
    }
    
}
复制代码

外层调用的quickSort1是一个递归函数，不断地进行分区操作，最终得到排好序的结果。

我们将上面实现的归并排序，使用swift内置函数的快速排序，以及自定义partition函数的快速排序的性能作对比：

merge sort...
merge sort time duration : 4.85s

quick sort...
quick sort0 time duration : 984ms //swift filter function
quick sort1 time duration : 2.64s //custom partition
复制代码

上面的测试用例是选择随机数组的，我们看一下测试用例为元素个数一致的基本有序的数组试一下：

merge sort...
merge sort time duration : 4.88s

quick sort...
quick sort0 time duration : 921ms
quick sort1 time duration : 11.3s
复制代码

虽然元素个数一致，但是性能却差了很多，是为什么呢？因为我们在分区的时候，pivot的index强制为第一个。那么如果这个第一个元素的值本来就非常小，那么就会造成分区不均的情况（前重后轻），而且由于是迭代操作，每次分区都会造成分区不均，导致性能直线下降。所以有一个相对合理的方案就是在选取pivot的index的时候随机选取。

使用随机选择pivotValue的partition函数

实现方法肯简单，只需在分区函数里将pivotValue的index随机生成即可：

func _partitionRandom(_ array: inout [Int], low: Int, high: Int) -> Int{
    
    let x      = UInt32(low)
    let y      = UInt32(high)
    
    let pivotIndex = Int(arc4random() % (y - x)) + Int(x)
    let pivotValue = array[pivotIndex] 
    
    ...
}
复制代码

现在用一个数组长度和上面的测试用例一致的基本有序的数组来测试一下随机选取pivotValue的算法：

merge sort...
merge sort time duration : 4.73s

quick sort...
quick sort0 time duration : 866ms
quick sort1 time duration : 15.1s  //fixed pivote index
quick sort2 time duration : 4.28s  //random pivote index
复制代码

我们可以看到当随机抽取pivot的index的时候，其运行速度速度是上面方案的3倍。

现在我们知道了3种快速排序的实现，都是根据pivotValue将原数组一分为二。但是如果数组中有大量的重复的元素，而且pivotValue很有可能落在这些元素里，那么显然上面这些算法对于这些可能出现多次于pivotValue重复的情况没有单独做处理。而为了很好解决存在与pivot值相等的元素很多的数组的排序，使用三路排序算法会比较有效果。

三路快速排序

三路快速排序将大于，等于，小于pivotValue的元素都区分开，我们看一下具体的实现。先看一下partition函数的实现：

func swap(_ arr: inout [Int],  _ j: Int, _ k: Int) {
    
    guard j != k else {
        return;
    }
    
    let temp = arr[j]
    arr[j] = arr[k]
    arr[k] = temp
}



func quickSort3W(_ array: inout [Int], low: Int, high: Int) {
    
    if high <= low { return }
    
    var lt = low       // arr[low+1...lt] < v
    var gt = high + 1  // arr[gt...high] > v
    var i  = low + 1   // arr[lt+1...i) == v
    
    let pivoteIndex = low
    let pivoteValue = array[pivoteIndex]
    
    while i < gt {
        
        if array[i] < pivoteValue {
          
            swap(&array, i, lt + 1)
            i += 1
            lt += 1
           
        }else if pivoteValue < array[i]{
       
            swap(&array, i, gt - 1)
            gt -= 1
            
        }else {
            i += 1
        }
    }
    
    swap(&array, low, lt)
    quickSort3W(&array, low: low, high: lt - 1)
    quickSort3W(&array, low: gt, high: high)
    
    
}


func quickSort3(_ array: inout [Int] ){
    
    quickSort3W(&array, low: 0, high: array.count - 1)
    
}
复制代码

主要看quickSort3W方法，这里将数组分成了三个区间，分别是大于，等于，小于pivote的值，对有大量重复元素的数组做了比较好的处理。

我们生成一个元素数量为500，最大值为5的随机数组看一下这些快速排序算法的性能：

quick sort1 time duration : 6.19s //fixed pivote index
quick sort2 time duration : 8.1s  //random pivote index
quick sort3 time duration : 4.81s //quick sort 3 way 
复制代码

可以看到三路快速排序（quick sort 3 way）在处理大量重复元素的数组的表现最好。

对于三路快速排序，我们也可以使用Swift内置的filter函数来实现:

func quicksort4(_ array: [Int]) -> [Int] {
    
    guard array.count > 1 else { return array }
    
    let pivot = array[array.count/2]
    let less = array.filter { $0 < pivot }
    let equal = array.filter { $0 == pivot }
    let greater = array.filter { $0 > pivot }
    
    return quicksort4(less) + equal + quicksort4(greater)
}
复制代码

以上，介绍完了快速排序在Swift中的5中实现方式。

THE END

归并排序算法讲解及swift代码实现

<<上一篇

JavaScript ES5 到 ES8 数组内容一次过

下一篇>>