2.5.Quick sort

• Introduction

  • 目前被認為效率最高的排序演算法(sorting algorithm)

  • 快速排序法也是利用divide and conquer,不斷地將資料分成兩部分以解決問題

  • 時間複雜度, 空間複雜度

    • 最佳時間複雜度：O(nlog n)

    • 平均時間複雜度：O(nlog n)

    • 最差時間複雜度：O(n2)

    • 空間複雜度：O(n)

  • 實作步驟:

    • 1.選擇序列中的一個數字為pivot(通常為最左邊的數字)

    • 2.將此序列中大於pivot的數字放到pivot右邊, 小於pivot的放到pivot左邊

    • 3.以pivot為中心, 將左半部與右半部各自進行步驟1~2

• 程式碼

void quicksort(int *data, int left, int right)
{
    if (left >= right){
        //function結束
        return;
    }
    //choose data[left] to be the pivot
    int pivot = data[left];
    int i = left + 1;
    int j = right;
    while (1){
        //找出大於pivort的數值
        while (i <= right){
            if (data[i] > pivot){
                break;
            }
            i = i + 1;
        }
        //找出大於pivort的數值
        while (j > left){
            if (data[j] < pivot){
                break;
            }
            j = j - 1;
        }
        //j會先結束while, 當i > j時跳出迴圈 
        if (i > j){
            break;
        }
        //將左右位置互換
        swap(&data[i], &data[j]);
    }
    //將左右位置互換
    swap(&data[left], &data[j]);
    quicksort(data, left, j - 1);
    quicksort(data, j + 1, right);    
}
void swap(int *a, int *b)
{
    int temp = *b;
    *b = *a;
    *a = temp;
}