美文网首页
iOS 快速排序(Quick Sort)

iOS 快速排序(Quick Sort)

作者: 下班不写程序 | 来源:发表于2022-09-26 19:02 被阅读0次

algo

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。
本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法。
基本思想是, 通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

算法过程描述
  1. 从数列中挑出一个元素,称为 “基准”(pivot);
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

如果要排序数组中下标从 p 到 r 之间的一组数据,我们选择 p 到 r 之间的任意一个数据作为 pivot (分区点), 我们遍历 p 到 r 之间的数据,将小于 pivot 的放到左边,将大于 pivot 的放到右边,将 pivot 放到中间。经过这一步骤之后,数组 p 到 r 之间的数据就被分成了三个部分,前面 p 到 q-1 之间都是小于 pivot 的,中间是 pivot,后面的 q+1 到 r 之间是大于 pivot 的。


逻辑演示

剩下, 可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据,直到区间缩小为 1,就说明所有的数据都有序了。

动图演示
quickSort.gif
复杂度

用大O表示法,忽略常量、低阶和常数系数。

时间复杂度为:最坏O(n²), 最好O(nlogn)
空间复杂度为:并未开辟额外空间, 所以为O(1)
稳定性: 不稳定

代码实现(Swift)
var numbers = [6,8,7,6,3,5,9,4]
func quickSort(numbers: inout [Int], leftIndex: Int, rightIndex: Int) {

    if leftIndex >= rightIndex {
        return
    }

    var i = leftIndex;
    var j = rightIndex;

    // 记录比较基准数
    var pivot = numbers[i]

    while i < j {

        // 首先从右边j开始查找比基准数小的值
        while i < j && numbers[j] >= pivot {
            // 如果比基准数大,不需要做什么操作, 接续往前查找
            j -= 1
        }
        
        // 如果比基准数小,则将查找到的小值调换到i的位置
        numbers[i] = numbers[j]

        print("\n\(numbers) bigger change \(j)th to \(i)th")
        
        // 当在右边查找到一个比基准数小的值时,就从i开始往后找比基准数大的值
        while i < j && numbers[i] <= pivot {
            // 如果比基准数小,不需要做什么操作, 接续往后查找
            i += 1
        }
        // 如果比基准数大,则将查找到的大值调换到j的位置
        numbers[j] = numbers[i]
        
        print("\n\(numbers) smaller change \(i)th to \(j)th")
    }
    
    // 比较一次之后, 将基准数放到正确位置
    numbers[i] = pivot;
    
    print("\n\(numbers)")
    
    /**** 递归排序 ***/
    // 排序基准数左边的
    quickSort(numbers: &numbers, leftIndex: leftIndex, rightIndex: i-1)
    // 排序基准数右边的
    quickSort(numbers: &numbers, leftIndex: i+1, rightIndex: rightIndex)
}

quickSort(numbers: &numbers, leftIndex: 0, rightIndex: numbers.count-1)
print(numbers)

终端打印结果:

[4, 8, 7, 6, 3, 5, 9, 4] bigger change 7th to 0th

[4, 8, 7, 6, 3, 5, 9, 8] smaller change 1th to 7th

[4, 5, 7, 6, 3, 5, 9, 8] bigger change 5th to 1th

[4, 5, 7, 6, 3, 7, 9, 8] smaller change 2th to 5th

[4, 5, 3, 6, 3, 7, 9, 8] bigger change 4th to 2th

[4, 5, 3, 6, 3, 7, 9, 8] smaller change 4th to 4th

[4, 5, 3, 6, 6, 7, 9, 8]

[3, 5, 3, 6, 6, 7, 9, 8] bigger change 2th to 0th

[3, 5, 5, 6, 6, 7, 9, 8] smaller change 1th to 2th

[3, 5, 5, 6, 6, 7, 9, 8] bigger change 1th to 1th

[3, 5, 5, 6, 6, 7, 9, 8] smaller change 1th to 1th

[3, 4, 5, 6, 6, 7, 9, 8]

[3, 4, 5, 6, 6, 7, 9, 8] bigger change 2th to 2th

[3, 4, 5, 6, 6, 7, 9, 8] smaller change 2th to 2th

[3, 4, 5, 6, 6, 7, 9, 8]

[3, 4, 5, 6, 6, 7, 9, 8] bigger change 5th to 5th

[3, 4, 5, 6, 6, 7, 9, 8] smaller change 5th to 5th

[3, 4, 5, 6, 6, 7, 9, 8]

[3, 4, 5, 6, 6, 7, 8, 8] bigger change 7th to 6th

[3, 4, 5, 6, 6, 7, 8, 8] smaller change 7th to 7th

[3, 4, 5, 6, 6, 7, 8, 9]
[3, 4, 5, 6, 6, 7, 8, 9]
  • 稳定性

如果数组中有两个相同的元素,比如测试的序列numbers: (6,8,7,6,3,5,9,4),在经过第一次分区操作之后,两个 6 的相对先后顺序就会改变。所以,快速排序并不是一个稳定的排序算法

  • 快速排序的性能分析

最好的情况下, 选择的 pivot 都很合适,正好能将大区间对等地一分为二。这时快排的时间复杂度递推求解公式跟归并是相同的。即为O(nlogn)。

最坏的情况下, 有序数组中, 每次选择最后一个元素作为 pivot,那每次分区得到的两个区间都是不均等的。我们需要进行大约 n 次分区操作,才能完成快排的整个过程。每次分区我们平均要扫描大约 n/2 个元素,快排的时间复杂度就从 O(nlogn) 退化成了 O(n2).

T(n) 在大部分情况下的时间复杂度都可以做到 O(nlogn),只有在极端情况下,才会退化到 O(n2)。

回目录:常用的排序算法

结语

路漫漫其修远兮,吾将上下而求索~

作者简书

作者掘金

作者GitHub

.End

相关文章

网友评论

      本文标题:iOS 快速排序(Quick Sort)

      本文链接:https://www.haomeiwen.com/subject/qenwortx.html