快速排序

1，快速排序

首先任意選取一個資料（通常選用第一個資料）作為關鍵資料，然後将所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。

怎麼實作呢？---

它的關鍵在于完成一趟快排後，基準元素在哪個位置，每次都選取一個分割列的第一個元素作為基準元素，來尋找用它來分割排序列後它自己所處的位置，編寫一個

int  findPartition(data,min,max)方法，用于使用data[min]作為基準元素把data[min]到data[max]分割為兩個部分，并傳回分割以後基準元素自己所在的位置索引。

在主函數裡這樣來調用：

public static void quickSort(Comparable[] data,int min,int max) {

        int mid;

        if(min < max)

        {

            mid = findPartition(data,min,max);

            quickSort(data,min,mid-1);

            quickSort(data,mid+1,max);

        }

    }

了解遞歸過程：：：if(min < max)，實際上就是要将值列分割為單一的元素（遞歸的最深一層），在得到基準元素的位置min後，基準元素在數組中的位置就最終确定，剩下隻對左右兩側的分割列

排序：quickSort(data,min,mid-1); quickSort(data,mid+1,max);

下面來看最重要的實作部分，如何實作findPartition函數：

将第一個元素作為基準元素不要動，設兩個指針left和right，left從左往右移動尋找比基準元素大的數，right從右往左移動尋找比基準元素小的數，當它們都找到對應的left和right的位置時，交換

這兩個元素。重複這個過程，直到right < left.這時，除基準元素外，從min+1到right的元素都比基準元素小，left到max的元素都比基準元素大。形成了這樣一個序列：

基準元素（data[min]）  ....比基準元素小的......   data[right]    |    data[left]  ......比基準元素大的  

交換基準元素和data[right]即可得到  以基準元素為分割線的 左右兩個分割列。

這裡我把  排序遞歸的調用  與   分割值列和尋找分割位置（核心部分） 分開寫成兩個方法，為了顯得邏輯更加清楚。

完整代碼   ：

//快排:快排是一個遞歸的過程！！！！

    public static void quickSort(Comparable[] data,int min,int max) {

    //快排的支援方法

    public static int findPartition(Comparable[] data,int min,int max){

        int left,right;

        Comparable temp,partitionelement;

        left = min;right = max;

        partitionelement = data[min];//partitionelement 是data[min]的一個副本

        while(left < right)

            while(data[left].compareTo(partitionelement) <= 0 && left < right)

                left++;

            while(data[right].compareTo(partitionelement) > 0)

                right--;

            if(left < right)

            {

                temp = data[left];

                data[left] = data[right];

                data[right] =temp;

            }

        temp = data[min];

        data[min] = data[right];

        data[right] = temp;

        //錯錯誤的寫法，要的是把第一個元素和data[right]交換，而不是它的副本

        //temp = data[right];

        //data[right] = partitionelement;

        //partitionelement = temp;

        return right;

本文轉自農夫山泉别墅部落格園部落格，原文連結：http://www.cnblogs.com/yaowen/p/4476776.html，如需轉載請自行聯系原作者