Skip to content

快速排序

快速排序

什么是快速排序

不论是选择排序还是冒泡排序，其时间复杂度都较高，都达到了 O(n²)。如果数据规模没有很大的数据内容，那么使用以上排序就足够了。 但是一旦要做大量的数据的排序，这个效率是无法满足需求的。所以便设计出了一个非常优雅高效的排序算法——快速排序。 快速排序采用了分治的思想，将待排序序列划分成两个子序列，一个小于基准值的子序列和一个大于基准值的子序列，并递归地对这两个子序列进行排序。

快速排序的优点

  1. 时间复杂度低：O(nlogn)的时间内完成对序列的排序，适用于处理大规模数据。
  2. 快速排序还是许多其他排序算法的基础，例如归并排序和堆排序等。

快速排序的应用场景

  • C 语言中的 qsort。

快速排序的实现思路

快排的实现同样依赖分而治之，需要从分而治之的角度去理解快排。

  1. 找出快排的基线条件。
  2. 不断将问题分解，直到符合基线条件。 1. 从数组选一个元素，通常这个元素为基准值。 2. 找到比基准值大的元素和比基准值小的元素，进行分区。 3. 此时两个子数组是一个无序状态，如何对子数组进行排序呢？重复以上的操作即可。

找出快排的基线条件

要完成这一点非常简单，因为对于排序算法来说，最简单的数组就是不需要排序的数组。所以当数组为空，或者只包含一个元素的时候，递归结束。

if len(array)<2:
    return array

不断将问题分解，直到符合基线条件

  1. 从数组选一个元素，通常这个元素为基准值。

uml diagram

使用 Python 实现:

# 选择第一个元素为基准值。
pivot = arr[0]
  1. 找到比基准值大的元素和比基准值小的元素，进行分区。

uml diagram

如果使用 Python 实现：

left = []
right = []
for i in range(1, len(arr)):
    if arr[i] <= pivot:
        left.append(arr[i])
    else:
        right.append(arr[i])
  1. 此时两个子数组是一个无序状态，如何对子数组进行排序呢？重复以上的操作即可。
return quicksort(left) + [pivot] + quicksort(right)

快排的实现（Python）

def quicksort(arr):
    # 基线条件
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = []
    right = []
    for i in range(1, len(arr)):
        if arr[i] <= pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    return quicksort(left) + [pivot] + quicksort(right)

快排的实现（Java）

实现的逻辑：

public class Sort {

    private void swap(int[] list, int i,int j){
        // 交换操作
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }
    public int partion(int[] list, int low , int high){
        // 选定基准值
        // [5,1,3,2,6]
        int pivot = list[low];
        // 指针
        int i = low;
        for(int j=1; j<=high; j++){
            if(list[j] < pivot){
                i++;
                swap(list, i, j);
            }
        }
        // 循环结束之后， 分区已经结束，只剩基准值还没有动
        swap(list,low, i);
        // 分区的返回值为基准值所对应的索引位置。
        return i;
    }
    public void quickSort(int[] list, int low, int high){
        // 基线条件
        if(low>=high){
            return;
        }
        // 分区逻辑的实现
        int pivot_index = partion(list, low, high);
        ///========递归条件
        // 左边的数组做递归
        quickSort(list, low, pivot_index-1);
        // 右边的数组做递归
        quickSort(list, pivot_index+1,high);
    }
}

测试用例：

class SortTest {

    @Test
    void quickSort() {

        Sort sort = new Sort();
        int [] list = {5,1,3,6,2};
        sort.quickSort(list, 0, list.length-1);
        int [] sortedList = {1,2,3,5,6};
        assertEquals(Arrays.toString(sortedList), Arrays.toString(list));
    }
}

快排的时间复杂度

在快排实现的过程中，以下这段代码的时间复杂度确定为 O(n)：

for i in range(1, len(arr)):
    if arr[i] <= pivot:
        left.append(arr[i])
    else:
        right.append(arr[i])

接下来，需要计算的是，这段循环的代码一共执行了几次，也就是递归了几次，即可得到一个总的时间复杂度。

在这个过程里面，我们会发现具体递归几次，完全和选中的基准值息息相关，举个例子：

以数组[1,2,3,4,5,6,7,8]为例：

  1. 如果基准值选为 1。代表需要递归 7 次，这就是最坏的时间复杂度。

快排最糟情况

  1. 如果基准值选为 4。代表需要递归 3 次，这就是最好的时间复杂度。

快排最优情况

这个时间复杂度的结论是如何得出的呢？现在来看看栈的第一层。将一个元素用作基准值，并将其他的元素划分到两个子数组中。这涉及数组中的全部8个元素，因此该操作的时间为O(n)。在调用栈的第一层，涉及全部8个元素，但实际上，在调用栈的每层都涉及O(n)个元素。

最糟情况下快排每层都涉及O(n)个元素

最好情况下快排每层都涉及O(n)个元素

所以每层所需的时间都为O(n)，那么主要区别就是在层数上面了（也就是递归的次数）。

  • 最好的情况： O(logn)
  • 最坏的情况： O(n)

但是通常无法确定快排每次选中的基准是最好还是最坏，有多种可能的情况。所以快排的最好时间复杂度为 O(nlogn)， 最坏时间复杂度为O(n²)。

相关题目

数组中的第K个最大元素