【算法图文动画详解系列】QuickSort 快速排序算法

快排简介

快速排序（Quicksort）是对冒泡排序算法的一种改进。

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快排算法原理

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

(1) 首先设定一个分界值（pivot）：通过该分界值将数组分成左右两部分（partition）。

(2) Compare and Swap：将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

(3) Recursive：然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

(4) 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

动图演示快排原理：QuickSort Algorithm视频演示：

算法原理详解

快速排序（QuickSort ）是一个分治算法（Divide and Conquer）。它选择一个元素作为枢轴元素（pivot），并围绕选定的主元素对给定数组进行分区（partition）。快速排序有很多不同的版本，它们以不同的方式选择枢轴。

总是选择第一个元素作为 pivot。总是选择最后一个元素作为 pivot。随机选一个元素作为 pivot。选择中值作为 pivot。

QuickSort 中的关键步骤是 partition()。在数组中选择的一个元素为支点（pivot）, 把所有小于 pivot 的元素放到 pivot 左面, 大于 pivot 的放右边。这样数组 x[n] 会被划分成3个部分：

x[0] , ... , x[pivot - 1]

x[pivot]

x[pivot+1] , ... , x[n]

所有这应该是在线性时间内完成。

接下来，就是递归调用:

 quicksort(x, low, pivot - 1) quicksort(x, pivot + 1， high)

Pseudo Code for recursive QuickSort function

/* low  --> Starting index,  high  --> Ending index */void quickSort(arr[], low, high){    if (low < high)    {        /* pi is partitioning index, arr[pi] is now           at right place */        pi = partition(arr, low, high);        quickSort(arr, low, pi - 1);  // Before pi        quickSort(arr, pi + 1, high); // After pi    }}

Partition Algorithm

There can be many ways to do partition, following pseudo code adopts the method given in CLRS book.

The logic is simple, we start from the leftmost element and keep track of index of smaller (or equal to) elements as i. While traversing, if we find a smaller element, we swap current element with arr[i]. Otherwise we ignore current element.

Pseudo code for partition()

/* This function takes last element as pivot, places   the pivot element at its correct position in sorted    array, and places all smaller (smaller than pivot)   to left of pivot and all greater elements to right   of pivot */partition (arr[], low, high){    // pivot (Element to be placed at right position)    pivot = arr[high];       i = (low - 1)  // Index of smaller element and indicates the                    // right position of pivot found so far    for (j = low; j <= high- 1; j++)    {        // If current element is smaller than the pivot        if (arr[j] < pivot)        {            i++;    // increment index of smaller element            swap arr[i] and arr[j]        }    }    swap arr[i + 1] and arr[high])    return (i + 1)}

Illustration of partition()

arr[] = {10, 80, 30, 90, 40, 50, 70}Indexes:  0   1   2   3   4   5   6 low = 0, high =  6, pivot = arr[h] = 70Initialize index of smaller element, i = -1Traverse elements from j = low to high-1j = 0 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])i = 0 arr[] = {10, 80, 30, 90, 40, 50, 70} // No change as i and j                                      // are samej = 1 : Since arr[j] > pivot, do nothing// No change in i and arr[]j = 2 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])i = 1arr[] = {10, 30, 80, 90, 40, 50, 70} // We swap 80 and 30 j = 3 : Since arr[j] > pivot, do nothing// No change in i and arr[]j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])i = 2arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 and 40 Swappedj = 5 : Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j] i = 3 arr[] = {10, 30, 40, 50, 80, 90, 70} // 90 and 50 Swapped We come out of loop because j is now equal to high-1.Finally we place pivot at correct position by swappingarr[i+1] and arr[high] (or pivot) arr[] = {10, 30, 40, 50, 70, 90, 80} // 80 and 70 Swapped Now 70 is at its correct place. All elements smaller than70 are before it and all elements greater than 70 are afterit.

快排算法源代码Java 源代码

// Java implementation of QuickSortimport java.io.*;class QuickSort{    // A utility function to swap two elementsstatic void swap(int[] arr, int i, int j){    int temp = arr[i];    arr[i] = arr[j];    arr[j] = temp;}/* This function takes last element as pivot, placesthe pivot element at its correct position in sortedarray, and places all smaller (smaller than pivot)to left of pivot and all greater elements to rightof pivot */static int partition(int[] arr, int low, int high){        // pivot    int pivot = arr[high];        // Index of smaller element and    // indicates the right position    // of pivot found so far    int i = (low - 1);    for(int j = low; j <= high - 1; j++)    {                // If current element is smaller        // than the pivot        if (arr[j] < pivot)        {                        // Increment index of            // smaller element            i++;            swap(arr, i, j);        }    }    swap(arr, i + 1, high);    return (i + 1);}/* The main function that implements QuickSort        arr[] --> Array to be sorted,        low --> Starting index,        high --> Ending index*/static void quickSort(int[] arr, int low, int high){    if (low < high)    {                // pi is partitioning index, arr[p]        // is now at right place        int pi = partition(arr, low, high);        // Separately sort elements before        // partition and after partition        quickSort(arr, low, pi - 1);        quickSort(arr, pi + 1, high);    }}public static void main(String[] args){    int[] arr = { 10, 7, 8, 9, 1, 5 };    int n = arr.length;        quickSort(arr, 0, n - 1);}}// This code is contributed by Ayush Choudhary

Kotlin 源代码（优化版本）

package com.light.swordimport kotlin.random.Random/** * @author: Jack * 2021/4/28 下午2:34 * Like Merge Sort, QuickSort is a Divide and Conquer algorithm. * It picks an element as pivot and partitions the given array around the picked pivot. * There are many different versions of quickSort that pick pivot in different ways.Always pick first element as pivot.Always pick last element as pivot (implemented below)Pick a random element as pivot.Pick median as pivot.The key process in quickSort is partition(). Target of partitions is,given an array and an element x of array as pivot, put x at its correct position in sorted array,and put all smaller elements (smaller than x) before x,and put all greater elements (greater than x) after x.All this should be done in linear time. */fun quicksort(x: IntArray, low: Int, high: Int) {    // index boundary check    if (low >= high) return    // random select a pivot element    val pivotIndex = Random(1).nextInt(low, high)    // put the pivot element at head    swap(x, low, pivotIndex)    val pivotValue = x[low]    // boundary index i, elements on the left side of i are smaller than pivotValue    var i = low    (low + 1..high).forEach {        // x[j] comparing  pivotValue, find smaller than pivotValue,        // and put it on the left side of i position        val j = it        if (x[j] < pivotValue) {            swap(x, ++i, j)        }    }    // i should be the pivot index, so swap x[low],x[i]    swap(x, low, i)    // divide and conquer, recursive call    quicksort(x, low, i - 1)    quicksort(x, i + 1, high)}fun swap(x: IntArray, a: Int, b: Int) {    val temp = x[a]    x[a] = x[b]    x[b] = temp}fun main() {    val x = intArrayOf(7, 2, 1, 8, 6, 3, 5, 4)    quicksort(x, 0, x.size - 1)    println(x.joinToString { it.toString() })}

参考资料

1、《代码之美》Chapter 3：我从未编写过的最漂亮的代码（Jon Bentley）

2、QuickSort：

3、快速排序百科：