六、快速排序法(Quick Sort)是排序演算中的一種，處理過程是先選擇一個資料為基準點，所有 比基準點小的元素放在左邊，比基準點大的元素放在右邊，之後再反覆對基準點左右兩邊 的數列執行相同的處理，直到數列只剩一個數值或沒有數值時即完成排序。請撰寫一函式 QuickSort()，將傳入的一維陣列利用快速排序法，由小至大排序陣列元素。（20 分）

詳解 (共 3 筆)

詳解 提供者：111郵專一，地特四資訊正取

使用C語言，程式碼如下

void swap(int *x,int *y){
    int temp=*x;
    *x=*y;
    *y=temp;
}

int partition(int a[],int left,int right){
    int i,j,pivot;
    i=left;
    pivot=a[i];
    for(j=i+1;j<=right;j++){
        if(pivot>=a[j]){
            i++;  //指在比pivot大的陣列上// 
            swap(a[i],a[j]);
        }
    }
    a[left]=a[i];
    a[i]=pivot;
    return i;
}

void quick_sort(int a[],int left,int right){
    int mid;
    if(left<right){
        mid=partition(a,left,right);
        quick_sort(a,left,mid-1);
        quick_sort(a,mid+1,right);
    }
}
    


int main() { 
    int n[] = {23,3,12,36,5,11,22,64};
    int length=sizeof(n)/sizeof(n[0]);
    
    quick_sort(n,0,7);
    
    
    for(int z=0;z<length;z++)    {
         printf("%d,",n[z]);
    }
};

詳解 提供者：yuC邀請碼196783
C++版本提供參考
6704c633b78f5.jpg
6704c52e6bd07.jpg
詳解 提供者：Fourier
順便把每次排序結果給印出來，給剛學資料結構的的人可以對照參考順便理解過程如何運作，輸出結果在底下
程序有問題麻煩請指教

#include <iostream>
using namespace std;
 
template <typename T, size_t size>    //為了印出每次排序結果要呼叫size所以先建個template
 
void quicksort(T (&array)[size], int left, int right)
{
    if (left < right)
    {
        int i, j, pivot;
        i = left;
        j = right;
        pivot = array[(i+j)/2];
        while (1)
        {
            while (array[i] < pivot && i<right)
            {
                i++;
            }
            while (array[j] > pivot && j>left)
            {
                j--;
            }
            if (i >= j)
                break;
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            cout << "當前排序:";           //印出每次排序的結果供參考
            for (int k = 0; k < size; k++)
            {
                cout << array[k] << " ";
            }
            cout << endl;
        }
        quicksort(array, left, i-1);
        quicksort(array, i + 1, right);
    }
}
 
int main()
{
    int data[10] = {2, 3, 4, 5, 1, 6, 0, 8, 9, 7};
    quicksort(data, 0, 9);
    return 0;
}
 
輸出結果:
6700e82c9cd6f.jpg