資料結構與算法系列 -- 快速排序算法

        快排利用的也是分治思想。乍看起來，它有點像歸并排序，但是思路其實完全不一樣

        快排的思想是這樣的：如果要排序數組中下标從 p 到 r 之間的一組資料，我們選擇 p 到 r 之間的任意一個資料作為 pivot（分區點）。        我們周遊 p 到 r 之間的資料，将小于 pivot 的放到左邊，将大于 pivot 的放到右邊，将 pivot 放到中間。經過這一步驟之後，數組 p 到 r 之間的資料就被分成了三個部分，前面 p 到 q-1 之間都是小于 pivot 的，中間是 pivot，後面的 q+1 到 r 之間是大于 pivot 的。

僞代碼如下：

//按照設定的 pivot,将下标 r 到 q 的元素分為兩部分，一部分小于 pivot，另外一部分大于 pivot,并傳回 新的分割點
int  partition(data,r,q){

    
}


void  quick_sort(data,r,q){
    if(r>=q)
      return
   
    int  p = partition(data,r,q)
    quick_sort(data,r,p-1)
    quick_sort(data,p+1,q)
   
}

void test(){

  quick_sort(0,data.length-1)
}
           

java 代碼:

public class SortTest {

    private void swap(int[] data,int i,int j){
           int tmp = data[i];
           data[i] = data[j];
           data[j] = tmp;
    }

    public void printArray(int[] data){
        for(int d:data){
            System.out.print(d+" ");
        }
        System.out.println();
    }


    /**
     * 快速排序
     */
    public int partition(int[] data,int r,int q){
        int pivot = q;
        int start = r;

        for(int j=r;j<q;j++){
            if(data[j]<data[pivot]){
                swap(data,start++,j);
            }

        }

        swap(data,start,pivot);

        return start;
    }

    public void quick_sort(int[] data,int r,int q){

        if(r>=q){
            return;
        }

        int pivot = partition(data,r,q);

        quick_sort(data,r,pivot-1);
        quick_sort(data,pivot+1,q);

    }

    @Test
    public void test5(){
        int[]  data = {55,76,34,66,22,31,13,25,90,87,56,65,66};

        //int[]  data = {6,7,8,9,1,2,3,4,5};
        //partition(data,0,data.length-1);

        quick_sort(data,0,data.length-1);
        printArray(data);

    }
}
           

結果：

13 22 25 31 34 55 56 65 66 66 76 87 90 
           

  分析：快速排序算法隻在交換時，耗費了常數的空間複雜度，因而是原地排序算法；

             其在 partition 函數中，交換時，會影響值相同元素的先後順序，因而是不穩定的算法；

             快速排序的在大部分情況下的時間複雜度都可以做到 O(nlogn)，隻有在極端情況下，才會退化到 O(n2)，且機率極低