【算法圖文動畫詳解系列】QuickSort 快速排序算法

快排簡介

快速排序(Quicksort)是對冒泡排序算法的一種改進(jìn)。

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小勤婚,然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序,整個(gè)排序過程可以遞歸進(jìn)行,以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列瘾婿。

快排算法原理

快速排序算法通過多次比較和交換來實(shí)現(xiàn)排序,其排序流程如下:

(1) 首先設(shè)定一個(gè)分界值(pivot):通過該分界值將數(shù)組分成左右兩部分(partition)烤咧。
(2) Compare and Swap:將大于或等于分界值的數(shù)據(jù)集中到數(shù)組右邊偏陪,小于分界值的數(shù)據(jù)集中到數(shù)組的左邊。此時(shí)煮嫌,左邊部分中各元素都小于或等于分界值笛谦,而右邊部分中各元素都大于或等于分界值。
(3) Recursive:然后昌阿,左邊和右邊的數(shù)據(jù)可以獨(dú)立排序饥脑。對于左側(cè)的數(shù)組數(shù)據(jù),又可以取一個(gè)分界值懦冰,將該部分?jǐn)?shù)據(jù)分成左右兩部分灶轰,同樣在左邊放置較小值,右邊放置較大值刷钢。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理笋颤。
(4) 重復(fù)上述過程,可以看出闯捎,這是一個(gè)遞歸定義椰弊。通過遞歸將左側(cè)部分排好序后许溅,再遞歸排好右側(cè)部分的順序。當(dāng)左秉版、右兩個(gè)部分各數(shù)據(jù)排序完成后贤重,整個(gè)數(shù)組的排序也就完成了。

動圖演示快排原理:

QuickSort Algorithm視頻演示:

https://video.kuaishou.com/short-video/3xytg4s3xviab3u

算法原理詳解

快速排序(QuickSort )是一個(gè)分治算法(Divide and Conquer)清焕。它選擇一個(gè)元素作為樞軸元素(pivot)并蝗,并圍繞選定的主元素對給定數(shù)組進(jìn)行分區(qū)(partition)〗胀祝快速排序有很多不同的版本滚停,它們以不同的方式選擇樞軸。

  1. 總是選擇第一個(gè)元素作為 pivot粥惧。
  2. 總是選擇最后一個(gè)元素作為 pivot键畴。
  3. 隨機(jī)選一個(gè)元素作為 pivot。
  4. 選擇中值作為 pivot突雪。

QuickSort 中的關(guān)鍵步驟是 partition()起惕。在數(shù)組中選擇的一個(gè)元素為支點(diǎn)(pivot), 把所有小于 pivot 的元素放到 pivot 左面, 大于 pivot 的放右邊。這樣數(shù)組 x[n] 會被劃分成3個(gè)部分:

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

所有這應(yīng)該是在線性時(shí)間內(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

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末辰狡,一起剝皮案震驚了整個(gè)濱河市锋叨,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌搓译,老刑警劉巖悲柱,帶你破解...
    沈念sama閱讀 211,743評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異些己,居然都是意外死亡豌鸡,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,296評論 3 385
  • 文/潘曉璐 我一進(jìn)店門段标,熙熙樓的掌柜王于貴愁眉苦臉地迎上來涯冠,“玉大人,你說我怎么就攤上這事逼庞∩吒” “怎么了?”我有些...
    開封第一講書人閱讀 157,285評論 0 348
  • 文/不壞的土叔 我叫張陵,是天一觀的道長派任。 經(jīng)常有香客問我砸逊,道長,這世上最難降的妖魔是什么掌逛? 我笑而不...
    開封第一講書人閱讀 56,485評論 1 283
  • 正文 為了忘掉前任师逸,我火速辦了婚禮,結(jié)果婚禮上豆混,老公的妹妹穿的比我還像新娘篓像。我一直安慰自己,他們只是感情好皿伺,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,581評論 6 386
  • 文/花漫 我一把揭開白布员辩。 她就那樣靜靜地躺著,像睡著了一般鸵鸥。 火紅的嫁衣襯著肌膚如雪奠滑。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 49,821評論 1 290
  • 那天脂男,我揣著相機(jī)與錄音养叛,去河邊找鬼。 笑死宰翅,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的爽室。 我是一名探鬼主播汁讼,決...
    沈念sama閱讀 38,960評論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼阔墩!你這毒婦竟也來了嘿架?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 37,719評論 0 266
  • 序言:老撾萬榮一對情侶失蹤啸箫,失蹤者是張志新(化名)和其女友劉穎耸彪,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體忘苛,經(jīng)...
    沈念sama閱讀 44,186評論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡蝉娜,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,516評論 2 327
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了扎唾。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片召川。...
    茶點(diǎn)故事閱讀 38,650評論 1 340
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖胸遇,靈堂內(nèi)的尸體忽然破棺而出荧呐,到底是詐尸還是另有隱情,我是刑警寧澤,帶...
    沈念sama閱讀 34,329評論 4 330
  • 正文 年R本政府宣布倍阐,位于F島的核電站概疆,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏峰搪。R本人自食惡果不足惜届案,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,936評論 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望罢艾。 院中可真熱鬧楣颠,春花似錦、人聲如沸咐蚯。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,757評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽春锋。三九已至矫膨,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間期奔,已是汗流浹背侧馅。 一陣腳步聲響...
    開封第一講書人閱讀 31,991評論 1 266
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留呐萌,地道東北人馁痴。 一個(gè)月前我還...
    沈念sama閱讀 46,370評論 2 360
  • 正文 我出身青樓,卻偏偏與公主長得像肺孤,于是被迫代替她去往敵國和親罗晕。 傳聞我的和親對象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,527評論 2 349

推薦閱讀更多精彩內(nèi)容

  • 什么是快速排序赠堵? 摘自漫畫算法: 同冒泡排序一樣小渊,快速排序也屬于交換排序,通過元素之間的比較和交換位置來達(dá)到排序的...
    花逝97閱讀 803評論 0 1
  • n:數(shù)據(jù)規(guī)模茫叭; 穩(wěn)定:兩個(gè)相等的值在排序前后相對位置是否改變酬屉,如果不會改變則成為穩(wěn)定,反之為不穩(wěn)定揍愁; 排序方式:內(nèi)...
    undefined汪少閱讀 842評論 0 49
  • 以下文章來源于后端技術(shù)指南針 呐萨,作者后端技術(shù)指南針 1.寫在前面 今天一起來學(xué)習(xí)一下:快速排序及其優(yōu)化 和 STL...
    立0911閱讀 417評論 0 0
  • 快速排序(QuickSort),又稱為劃分交換排序(partition-exchange sort),其實(shí)這個(gè)名字...
    Zentopia閱讀 2,029評論 1 7
  • 1.選擇數(shù)組中的一個(gè)元素 2.進(jìn)行一次Partition,將數(shù)組分為小于該元素和大于該元素的兩個(gè)部分 3.分別在兩...
    Nostalgia1024閱讀 1,170評論 0 1