Will的部落格

快速排序(quickSort), 每次排序時設定一個基準點,

小於基準點的數字全放到基準點的左邊,

大於基準點的數字全放到基準點的右邊,

最差情況為O(N²), 平均時間複雜度為 O(NlogN)

#include <stdio.h>

int a[101], n;

void quickSort(int left, int right)
{
    int i, j, t, temp;
    if(left > right)
        return;
    
    temp = a[left]; //temp中存的是基準數
    i = left;
    j = right;
    
    while(i != j)
    {
        while(a[j] >= temp && i < j) //先從右往左找
            j--;
        
        while(a[i] <= temp && i < j) //再從左往右爪
            i++;
            
        if(i < j) //交換兩數在陣列中的位置
        {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    
    
    a[left] = a[i]; /*將基準數歸位*/
    a[i] = temp;
    
    quickSort(left,  i - 1); //繼續處理左邊區塊
    quickSort(i + 1, right); //繼續處理右邊區塊
}

int main(void)
{
    int i, t;
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    
    quickSort(1, n);
    
    for(int i = 1; i <= n; i++)
        printf("%d", a[i]);
    
    return 0;
}