演算法知識 - 快速排序 quick sort

quick sort 快速排序 介紹與實作原理

快速排序顧名思義就是快的排序嘛XD。平均時間複雜度為 \(O(n log n\)，算是平常大家會用的演算法之一

實作原理如下：

• 定義 L 與 R，分別是當前數列的最左邊 index 與最右邊的 index
• standard 為每次 quick_sort 的第一值，每個人可以定義如何選擇此數字。
  • 定義：x 為數值，數堆為 standard 左 or 右 邊的數值
  • 我們主要是想讓陣列從原本的 standard x x x x x x，透過程式碼運算後改成 x x x standard x x x，再讓 standard 的左右邊再進行一次 quick_sort。
  • 而我們交換的方式就是使用兩個指針 L and R，從 L 開始不斷往右找直到找出第一個值比 standard 還大；從 R 開始不斷往左找直到找出第一個值比 standard 還大
  • 找到後進行交換，之後重複上一點，直到 L、R 指針相遇
  • 其中 standard 的左邊一定比 standard 還小，standard 的右邊一定比 standard 還大
  • 因此要找出最適合此排序的 standard 會讓排序變得更輕鬆，否則如果選出過大的 standard 會使的分好的兩堆數量過於偏頗，如： ```x x x x x standard x ``，
• 之後將 standard 隔開的兩數堆在進行 quick_sort，直到 standard 的左右沒辦法在分堆(遇到邊界)

Insertion Sort 程式碼說明與應用

透過程式碼來進行說明相信會更好理解，以下我們示範從小到大排序

#include <iostream>
#include <bits/stdc++.h>

using namespace std; 
int num[] = {4,96,1546,13,48,34,77,48,31};
int num_size;


void output(){ //輸出排序
    for(int i = 0 ; i < num_size ; i++)
        cout << num[i] << ' ' ;
    cout << '\n' ;
}


void quick_sort(int L , int R  ){ //快速排序，L、R 此堆的左邊界、右邊界
    if(L > R) return ; //如果 L > R 表示這邊沒有數堆
    //standard 分堆的標準， l，r 當前數堆的左邊界、右邊界
    int standard = num[L] , l = L , r = R+1 ;
    while(1){ 
        //如果左邊界的數值，比 standard 大就跳出迴圈，因為我們找到要交換的 l，注意左右指針不可相遇 
        while(standard > num[++l] && R > l  ); 
        //如果右邊界的數值，比 standard 大就跳出迴圈，因為我們找到要交換的 r，注意左右指針不可相遇 
        while(standard < num[--r] && L < r );
        if(l >= r ) break; //如果左右指針相遇就離開迴圈
        swap(num[l] , num[r]); //對我們找到的 l 與 r 進行交換
        output();
    }
    swap(num[L] , num[r]); //我們會發現 num[L] 就是 standard，我們要將他換到兩數堆的中間，
    //也就是兩堆數值的交界點
    output(); //輸出排序
    quick_sort( L , r-1 ); //將左數堆進行 quick_sort
    quick_sort( r+1 , R); //將右數堆進行 quick_sort
}

int main()
{
    num_size = sizeof(num) / sizeof(num[0]);

    output();
    quick_sort(0, num_size-1);


    return 0;
}

心得

由於 C++ 已經有很多 sort 套件了，因此我在高中學會後我就再也沒有去複習這些知識。

剛好現在上課有用到那就來複習，順便把它寫出邏輯八！

程式執行結果