快速排序算法

算法与数据结构

目录

  1. 简介
  2. 代码实现
  3. 性能分析

简介

快速排序（Quick Sort）是由图灵奖获得者Tony Hoare设计出来，被列为20世纪十大算法之一，以“快速”命名表明该算法在整体性能上是排序算法的王者。
核心思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。一趟排序过程示意图如下。

一趟排序中需要选择一个关键字，使得其左边的值都比它小，右边的值比它大 ，这个关键字称为枢轴（pivot），pivot取值越是位于中间其排序性能越好。

代码实现

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
fun quickSort(input: Array<Int>){
    quickSort(input)
}

fun quickSort(array: Array<Int>, _start: Int, _end: Int) {
    if (_start >= _end) {
        return
    }
    val pivot = partition(array, _start, _end)
    quickSort(array, _start, pivot - 1)
    quickSort(array, pivot + 1, _end)
}

fun partition(array: Array<Int>, _start: Int, _end: Int): Int {
    val pivot = array[_start] // pivot选第一个，可优化
    var start = _start
    var end = _end

    while (start < end) {
        while (end > start && array[end] >= pivot) {
            end--
        }
        array[start] = array[end]

        while (start < end && array[start] <= pivot) {
            start++
        }
        array[end] = array[start]
    }
    array[start] = pivot

    return start
}

性能分析

快速排序的时间性能取决于递归的深度，最优的情况是Partition每次都划分得比较均匀，如果排序n个关键字，其递归树的深度为$\lfloor log_2n+1\rfloor$，即仅需递归次$log_2n$，每次需要遍历整个序列，需要$O(n)$的时间，所以整个快速排序算法在最优的情况下时间复杂度为$O(nlogn)$。最坏的情况是一颗斜树，其深度为n，所以最坏的情况其时间复杂度为$O(n^2)$。平均的情况下，可以证明其数量级为$O(log_2n)$。由于其关键字比较和交换是跳跃式的，因此快速排序是一种不稳定的排序算法。