快排簡介
快速排序（Quicksort）是對冒泡排序算法的一種改進(jìn)。
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。
快排算法原理
快速排序算法通過多次比較和交換來實現(xiàn)排序，其排序流程如下：
(1) 首先設(shè)定一個分界值（pivot）：通過該分界值將數(shù)組分成左右兩部分（partition）。
(2) Compare and Swap：將大于或等于分界值的數(shù)據(jù)集中到數(shù)組右邊，小于分界值的數(shù)據(jù)集中到數(shù)組的左邊。此時，左邊部分中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值。
(3) Recursive：然后，左邊和右邊的數(shù)據(jù)可以獨立排序。對于左側(cè)的數(shù)組數(shù)據(jù)，又可以取一個分界值，將該部分?jǐn)?shù)據(jù)分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理。
(4) 重復(fù)上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側(cè)部分排好序后，再遞歸排好右側(cè)部分的順序。當(dāng)左、右兩個部分各數(shù)據(jù)排序完成后，整個數(shù)組的排序也就完成了。
動圖演示快排原理：
QuickSort Algorithm視頻演示：
https://video.kuaishou.com/short-video/3xytg4s3xviab3u
算法原理詳解
快速排序（QuickSort ）是一個分治算法（Divide and Conquer）。它選擇一個元素作為樞軸元素（pivot），并圍繞選定的主元素對給定數(shù)組進(jìn)行分區(qū)（partition）。快速排序有很多不同的版本，它們以不同的方式選擇樞軸。
- 總是選擇第一個元素作為 pivot。
- 總是選擇最后一個元素作為 pivot。
- 隨機選一個元素作為 pivot。
- 選擇中值作為 pivot。
QuickSort 中的關(guān)鍵步驟是 partition()。在數(shù)組中選擇的一個元素為支點（pivot）, 把所有小于 pivot 的元素放到 pivot 左面, 大于 pivot 的放右邊。這樣數(shù)組 x[n] 會被劃分成3個部分：
x[0] , ... , x[pivot - 1]
x[pivot]
x[pivot+1] , ... , x[n]
所有這應(yīng)該是在線性時間內(nèi)完成。
接下來，就是遞歸調(diào)用:
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] = 70
Initialize index of smaller element, i = -1
Traverse elements from j = low to high-1
j = 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 same
j = 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 = 1
arr[] = {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 = 2
arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 and 40 Swapped
j = 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 swapping
arr[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 than
70 are before it and all elements greater than 70 are after
it.
快排算法源代碼
Java 源代碼
// Java implementation of QuickSort
import java.io.*;
class QuickSort{
// A utility function to swap two elements
static 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, 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 */
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 源代碼（優(yōu)化版本）
package com.light.sword
import 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：https://www.geeksforgeeks.org/quick-sort/
3、快速排序百科：https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/369842
