排序算法練習-雙路快速排序

介紹

快速排序介紹

算法思路

雙路快排的主要差別在于對元素的劃分(Partiton)上。

• 以升序為例，選擇一個标定元素 e ，劃分成比 e 小的元素都在 e 左邊，比 e 大的元素都在 e 右邊。
• 分别從元素表的兩端周遊，當兩個索引的元素都不滿足條件，交換元素的位置，直到周遊完。
• 最後，讓标定的元素與小于它的最後一個元素交換。

代碼實作

#include<bits/stdc++.h>
#include<ctime>
using namespace std;

template<class T>
int partition2(T arr[], int l, int r) {
    //随機選擇标定位置，降低出現壞情況的機率
    swap(arr[l], arr[rand() % (r-l+1) + l]);
    //arr[l+1...i) < arr[l] < arr(j...r]
    int i = l+1;
    int j = r;
    while(true) {
        //不能寫成arr[i] <= arr[l]，會導緻遞歸樹的不平衡大幅降低效率
        while(i <= r && arr[i] < arr[l]) i++; 
        while(j >= l+1 && arr[j] > arr[l]) j--;
        if(i > j) 
            break;
        else 
            swap(arr[i], arr[j]);
        i++;
        j--;
    }
    swap(arr[l], arr[j]);
    return j;
}

template<class T>
void _quickSort(T arr[], int l, int r) {
    if(l >= r) 
        return;
    //對arr[l...r]進行劃分
    int p = partition2(arr, l, r);
    //對arr[l...p-1]進行排序
    _quickSort(arr, l, p-1);
    //對arr[p+1...r]進行排序
    _quickSort(arr, p+1, r);
}

template<class T>
void quickSort(T arr[], int n) {
    srand(time(NULL));
    //對arr[0...n-1]進行排序
    _quickSort(arr, 0, n-1);
}

int main(int argc, char const *argv[])
{
    // 測試
    int arr[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    quickSort(arr, 10);
    for(int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}
           

最後

• 由于部落客水準有限，難免有疏漏之處，歡迎讀者批評指正！