本文作者:心月

快速排序法排序過程圖解

心月IT博客 2019-03-22
摘要:快速排序(Quicksort)是對冒泡排序的一種改進,它由C A R Hoare在1962年提出。它的基本思想是:通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分的所有數據都要小,然后再按此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數據變成有序序列。

    快速排序的核心思想是:通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分的所有數據都要小,然后再按此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數據變成有序序列。

下面我們用圖解的方式來演示這個排序過程:

    假設下面這個數組是待排序數組:

(6, 1, 2, 7, 9, 3, 4, 5, 10, 8)

    按照快速排序的思想,首先得把這組數分成相互獨立的兩部分,其中一部分比中的數比另一部分的數都小。如何實現這一步呢?

    方法其實很簡單:首先選取待排序數組的第一個數為基準數,也就是6,然后分別從初始序列“(6, 1, 2, 7, 9, 3, 4, 5, 10, 8)”兩端開始“探測”。先從右往左找一個小于6的數,再從左往右找一個大于6的數,然后交換他們。這里可以用兩個變量i和j,分別指向序列最左邊和最右邊。我們為這兩個變量起個好聽的名字“哨兵i”和“哨兵j”。剛開始的時候讓哨兵i指向序列的最左邊(即i=1),指向數字6。讓哨兵j指向序列的最右邊(即j=10),指向數字8。

快速排序過程圖解

    首先哨兵j開始出動。因為此處設置的基準數是最左邊的數,所以需要讓哨兵j先出動,這一點非常重要(請自己想一想為什么)。哨兵j一步一步地向左挪動(即j--),直到找到一個小于6的數停下來。接下來哨兵i再一步一步向右挪動(即i++),直到找到一個數大于6的數停下來。最后哨兵j停在了數字5面前,哨兵i停在了數字7面前。

快速排序過程圖解

    現在交換哨兵i和哨兵j所指向的元素的值。交換之后的序列為(6, 1, 2, 5, 9, 3, 4, 7, 10, 8)。

    接下來開始哨兵j繼續向左挪動(再友情提醒,每次必須是哨兵j先出發)。他發現了4(比基準數6要小,滿足要求)之后停了下來。哨兵i也繼續向右挪動的,他發現了9(比基準數6要大,滿足要求)之后停了下來。此時再次進行交換,交換之后的序列為(6, 1, 2, 5, 4, 3, 9, 7, 10, 8)。

快速排序過程圖解

    哨兵j繼續向左挪動,他發現了3(比基準數6要小,滿足要求)之后又停了下來。哨兵i繼續向右移動,糟啦!此時哨兵i和哨兵j相遇了,哨兵i和哨兵j都走到3面前。說明此時“探測”結束。3比6小所以我們將基準數6和3進行交換。交換之后的序列為(3, 1, 2, 5, 4, 6, 9, 7, 10, 8)。

快速排序圖解

    此時第一趟排序結束,我們已經把待排序數組分成了以6為基準,左邊一列序列,右邊一序列,左邊序列的數比右邊序列的數都小。不過此時左右兩部分中的數各自的排序仍然是混亂的,還有繼續排序。

    快速排序的排序過程已經通過上面的圖解講解清楚了,接下來左右兩部分的數據繼續按照快速排序的方式來排序。

    其中左邊的序列是(3, 1, 2, 5, 4),按照上面的排序圖解哨兵j停下來的時候在2上面,哨兵i停下來的時候在5的上面,但此時哨兵i已經跑過哨兵j到他前面去了,所以此時不應該在把兩個哨兵所對應的數交換,而應該把我們的基準數3和2交換,所以此時左側的序列經過一次快速排序后變成了這樣(2, 1, 3, 5, 4)。

    右側的序列經過一次快速排序后變成了這樣(8, 7, 9, 10)。

    合并基準數6以及左右兩側的序列:

(2, 1 || 3 || 5, 4  ||| 6 |||  8, 7 || 9 || 10)

對于排序仍然混亂的部分繼續以快速排序進行排序,最終的排序應該是這樣的

(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

    細心的同學可能已經發現,快速排序的每一輪處理其實就是將這一輪的基準數歸位,直到所有的數都歸位為止,排序就結束了。下面上個霸氣的圖來描述下整個算法的處理過程。

快速排序過程圖解

    快速排序之所比較快,因為相比冒泡排序,每次交換是跳躍式的。每次排序的時候設置一個基準點,將小于等于基準點的數全部放到基準點的左邊,將大于等于基準點的數全部放到基準點的右邊。這樣在每次交換的時候就不會像冒泡排序一樣每次只能在相鄰的數之間進行交換,交換的距離就大的多了。因此總的比較和交換次數就少了,速度自然就提高了。當然在最壞的情況下,仍可能是相鄰的兩個數進行了交換。因此快速排序的最差時間復雜度和冒泡排序是一樣的都是O(N2),它的平均時間復雜度為O(NlogN)。


不同程序語言實現快速排序的代碼示例:

//PHP
<?php
/**
 * 快速排序
 * @author chaselxu
 */
function qs($a, $s=0, $e=null) {
    if($e === null) {
        $e = count($a);
    }
    if($s >= $e) {
        return $a;
    }
     
    $j = $e-1; 
    $i = $s;
    $n = $a[$s];
    //$ac = $a;
    for(; $j>$i; $j--) {
        if($a[$j] < $n) {
            $t = $a[$i];
            $a[$i] = $a[$j];
            $a[$j] = $t;
            for($i++;$i<$j;$i++) {
                if($a[$i] > $n) {
                    $t = $a[$j];
                    $a[$j] = $a[$i];
                    $a[$i] = $t;
                    break;
                }
            }
        }
    }
    //printf("\n[%s], %s ~ %s [%s] %s-%s-%s", implode($ac, ','), $s, $e, implode($a, ','), $i, $j, $e);
    qs(&$a, $s, $i);
    qs(&$a, $i+1, $e);
    return $a;
}
$n = mt_rand(10000000, 99999999);
$n = '7,3,2,8,7,2,0,2';//trim(preg_replace('/(\d)/', '$1,', $n), ',');
$n = explode(',', $n);
echo "\n".implode($n, ',');
echo "\n".implode(qs($n), ',');
#C++
#include <iostream>
 
using namespace std;
 
void Qsort(int a[], int low, int high)
{
    if(low >= high)
    {
        return;
    }
    int first = low;
    int last = high;
    int key = a[first];/*用字表的第一個記錄作為樞軸*/
 
    while(first < last)
    {
        while(first < last && a[last] >= key)
        {
            --last;
        }
 
        a[first] = a[last];/*將比第一個小的移到低端*/
 
        while(first < last && a[first] <= key)
        {
            ++first;
        }
         
        a[last] = a[first];    
/*將比第一個大的移到高端*/
    }
    a[first] = key;/*樞軸記錄到位*/
    Qsort(a, low, first-1);
    Qsort(a, first+1, high);
}
int main()
{
    int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};
 
    Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*這里原文第三個參數要減1否則內存越界*/
 
    for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    {
        cout << a[i] << "";
    }
     
    return 0;
}/*參考數據結構p274(清華大學出版社,嚴蔚敏)*/
#C
void sort(int *a, int left, int right)
{
    if(left >= right)/*如果左邊索引大于或者等于右邊的索引就代表已經整理完成一個組了*/
    {
        return ;
    }
    int i = left;
    int j = right;
    int key = a[left];
     
    while(i < j)                               /*控制在當組內尋找一遍*/
    {
        while(i < j && key <= a[j])
        /*而尋找結束的條件就是,1,找到一個小于或者大于key的數(大于或小于取決于你想升
        序還是降序)2,沒有符合條件1的,并且i與j的大小沒有反轉*/ 
        {
            j--;/*向前尋找*/
        }
         
        a[i] = a[j];
        /*找到一個這樣的數后就把它賦給前面的被拿走的i的值(如果第一次循環且key是
        a[left],那么就是給key)*/
         
        while(i < j && key >= a[i])
        /*這是i在當組內向前尋找,同上,不過注意與key的大小關系停止循環和上面相反,
        因為排序思想是把數往兩邊扔,所以左右兩邊的數大小與key的關系相反*/
        {
            i++;
        }
         
        a[j] = a[i];
    }
     
    a[i] = key;/*當在當組內找完一遍以后就把中間數key回歸*/
    sort(a, left, i - 1);/*最后用同樣的方式對分出來的左邊的小組進行同上的做法*/
    sort(a, i + 1, right);/*用同樣的方式對分出來的右邊的小組進行同上的做法*/
                       /*當然最后可能會出現很多分左右,直到每一組的i = j 為止*/
}
//JavaScript
const quickSort = (array) => {
 const sort = (arr, left = 0, right = arr.length - 1) => {
  if (left >= right) {//如果左邊的索引大于等于右邊的索引說明整理完畢
   return
  }
 let i = left
 let j = right
 const baseVal = arr[j] // 取無序數組最后一個數為基準值
 while (i < j) {//把所有比基準值小的數放在左邊大的數放在右邊
  while (i < j && arr[i] <= baseVal) { //找到一個比基準值大的數交換
   i++
  }
  arr[j] = arr[i] // 將較大的值放在右邊如果沒有比基準值大的數就是將自己賦值給自己(i 等于 j)
  while (j > i && arr[j] >= baseVal) { //找到一個比基準值小的數交換
   j--
 }
  arr[i] = arr[j] // 將較小的值放在左邊如果沒有找到比基準值小的數就是將自己賦值給自己(i 等于 j)
 }
 arr[j] = baseVal // 將基準值放至中央位置完成一次循環(這時候 j 等于 i )
 sort(arr, left, j-1) // 將左邊的無序數組重復上面的操作
 sort(arr, j+1, right) // 將右邊的無序數組重復上面的操作
 }
 const newArr = array.concat() // 為了保證這個函數是純函數拷貝一次數組
 sort(newArr)
 return newArr
}
//JAVA
class Quick
{
 public void sort(int arr[],int low,int high)
 {
 int l=low;
 int h=high;
 int povit=arr[low];
 
 while(l<h)
 {
 while(l<h&&arr[h]>=povit)
 h--;
 if(l<h){
 int temp=arr[h];
 arr[h]=arr[l];
 arr[l]=temp;
 l++;
 }
 
 while(l<h&&arr[l]<=povit)
 l++;
 
 if(l<h){
 int temp=arr[h];
 arr[h]=arr[l];
 arr[l]=temp;
 h--;
 }
 }
 print(arr);
 System.out.print("l="+(l+1)+"h="+(h+1)+"povit="+povit+"\n");
 if(l-1>low)sort(arr,low,l-1);
 if(h+1<high)sort(arr,h+1,high);
 }
}
 
 
/*//////////////////////////方式二////////////////////////////////*/
更高效點的代碼:
public<TextendsComparable<?superT>>
T[]quickSort(T[]targetArr,intstart,intend)
{
inti=start+1,j=end;
Tkey=targetArr[start];
SortUtil<T>sUtil=newSortUtil<T>();
 
if(start=end)return(targetArr);
 
 
/*從i++和j--兩個方向搜索不滿足條件的值并交換
*
*條件為:i++方向小于key,j--方向大于key
*/
while(true)
{
while(targetArr[j].compareTo(key)>0)j--;
while(targetArr[i].compareTo(key)<0&&i<j)i++;
if(i>=j)break;
sUtil.swap(targetArr,i,j);
if(targetArr[i]==key)
{
j--;
}else{
i++;
}
}
 
/*關鍵數據放到‘中間’*/
sUtil.swap(targetArr,start,j);
 
if(start<i-1)
{
this.quickSort(targetArr,start,i-1);
}
if(j+1<end)
{
this.quickSort(targetArr,j+1,end);
}
 
returntargetArr;
}
 
 
/*//////////////方式三:減少交換次數,提高效率/////////////////////*/
private<TextendsComparable<?superT>>
voidquickSort(T[]targetArr,intstart,intend)
{
inti=start,j=end;
Tkey=targetArr[start];
 
while(i<j)
{
/*按j--方向遍歷目標數組,直到比key小的值為止*/
while(j>i&&targetArr[j].compareTo(key)>=0)
{
j--;
}
if(i<j)
{
/*targetArr[i]已經保存在key中,可將后面的數填入*/
targetArr[i]=targetArr[j];
i++;
}
/*按i++方向遍歷目標數組,直到比key大的值為止*/
while(i<j&&targetArr[i].compareTo(key)<=0)
/*此處一定要小于等于零,假設數組之內有一億個1,0交替出現的話,而key的值又恰巧是1的話,那么這個小于等于的作用就會使下面的if語句少執行一億次。*/
{
i++;
}
if(i<j)
{
/*targetArr[j]已保存在targetArr[i]中,可將前面的值填入*/
targetArr[j]=targetArr[i];
j--;
}
}
/*此時i==j*/
targetArr[i]=key;
 
/*遞歸調用,把key前面的完成排序*/
this.quickSort(targetArr,start,i-1);
 
 
/*遞歸調用,把key后面的完成排序*/
this.quickSort(targetArr,j+1,end);
 
}
#Python3
def quick_sort(data):    
    """快速排序"""    
    if len(data) >= 2:  # 遞歸入口及出口        
        mid = data[len(data)//2]  # 選取基準值,也可以選取第一個或最后一個元素        
        left, right = [], []  # 定義基準值左右兩側的列表        
        data.remove(mid)  # 從原始數組中移除基準值        
        for num in data:            
            if num >= mid:                
                right.append(num)            
            else:                
                left.append(num)        
        return quick_sort(left) + [mid] + quick_sort(right)    
    else:        
        return data
 
# 示例:
array = [2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12]
print(quickSort(array))
# 輸出為[1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10, 12, 15, 15, 17]


文章版權及轉載聲明:

作者:心月 本文地址:http://www.eojird.tw/algorithm/209.html發布于 2019-07-01
文章轉載或復制請以超鏈接形式并注明出處心月IT博客

分享到:
贊(

發表評論

快捷輸入:

    評論列表 (有 0 條評論,人圍觀)參與討論