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

terry 2年前 (2023-09-27) 阅读数 68 #数据结构与算法

快速排序算法被称为20世纪十大算法之一，也是各大公司面试时最喜欢研究的算法。快速排序算法详解，那么就可以继续对这两条记录的部分进行排序，从而达到对整个序列进行排序的目的。

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

，实现步骤如下：

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

从上面的描述可以看出，分区操作是快速排序的基本算法。下面笔者通过例子来描述分区操作的过程。

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

选择5作为枢轴点
从两端开始：左边的 1 标记为低，右边的 2 标记为高。
先看j：2 [2,4,9,1,3,6,7,8,5]；
再次查看i：2 5，交换9和5，i保持不变[2,4,5,1,3,6,7,8,9]。

代码实现

使用Swift过滤函数

因为Swift有一个数组过滤函数，可以找到数组中匹配某个范围的某些值，所以作者先介绍一下这个函数使用的一个简单函数快速排序实现：

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)
}
复制代码

不，不难看出这里使用了递归：选择一个枢轴后，数组被分成两部分，最后合并在一起。虽然Swift的内置函数用于查找与这两部分匹配的元素，但读者可以通过这个例子更好地理解快速排序的实现。

使用index = 0的分区函数

除了使用Swift内置的过滤函数之外，我们当然可以自己实现分区函数，通常使用自定义的分区函数。

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是当前数组的第一个元素。

然后从数组最右边的索引逐渐向左移动。如果value大于pivotValue，则index-1；否则直接交换高低位元素；对左索引执行相同的操作。

该函数的最终结果是根据选定的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内置函数的快速排序和使用自定义分区函数的快速排序的性能：

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
复制代码

虽然元素数量相同，但性能要差得多。为什么？因为在进行分区时，旋转索引被强制放在第一位。如果第一个元素的值很小，就会造成分布不均匀（前面重，后面轻），而且由于这是一个迭代操作，每次分区都会造成分布不均匀，导致表现。因此，在选择旋转索引时一个相对合理的方案是随机选择。

使用随机选择一个pivotValue的分区函数

实现方法很简单，只需在分区函数中随机生成pivotValue索引即可：

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索引时，其运行速度比上述方案提高了3倍。

我们现在知道三种快速排序实现，它们都根据pivotValue将原始数组分成两部分。但如果数组有很多重复元素，并且pivotValue很可能在这些元素之中，那么显然上述算法不能处理pivotValue可能重复多次的情况。要解决具有逆值的数组排序问题，使用三向排序算法会更有效。

三向快速排序

三向快速排序将大于、等于和小于pivotValue 的元素分开。我们来看一个具体的实现。我们先看分区函数的实现：

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。这里将数组分为大于、等于和小于主值的三个区间。这是针对具有大量重复元素的数组完成的。更好的加工。

让我们生成一个元素数量为 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 
复制代码

您可以看到三路快速排序（quicksort 3 way）处理数组时许多重复的元素。最棒的表演。

对于三向快速排序，我们还可以使用Swift内置的过滤函数来实现：

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种快速排序实现方法。