快速排序的深入詳解以及java實現

　　快速排序作為一種高效的排序算法被廣泛應用SUN的JDK中的Arrayssort 方法用的就是快排
快排采用了經典的分治思想（divide and conquer）

Divide選取一個基元X（一般選取數組第一個元素）通過某種分區操作（partitioning）將數組劃分為兩個部分左半部分小於等於X右半部分大於等於X
Conquer 左右兩個子數組遞歸地調用Divide過程
Combine快排作為就地排序算法（in place sort）不需要任何合並操作
可以看出快排的核心部分就是劃分過程（partitioning）下面以一個實例來詳細解釋如何劃分數組（圖取自於《算法導論》）
初始化選取基元P=就是數組首元素i=j=i+= (數組下標以開頭)
循環不變量~i之間的元素都小於或等於Pi+~j之間的元素都大於或等於P

循環過程j 從到n考察j位置的元素如果大於等於P就繼續循環如果小於P就將j位置的元素（不應該出現在i+~j這個區間）和i+位置(交換之後仍在 i+~j區間)的元素交換位置同時將i+這樣就維持了循環不變量（見上述循環不變量說明）直到j=n完成最後一次循環操作
要注意的是在完成循環後還需要將i位置的元素和數組首元素交換以滿足我們最先設定的要求（對應圖中的第i步）

細 心的讀者可能會想到另一種更直白的分區方法即將基元取出存在另一相同大小數組中遇到比基元小的元素就存儲在數組左半部分遇到比基元大的元素就存儲在 數組右半部分這樣的操作復雜度也是線性的即Theta(n)但是空間復雜度提高了一倍這也是快排就地排序的優勢所在

復制代碼 代碼如下:
public class QuickSort {
    private static void QuickSort(int[] arrayint startint end)
    {
        if(start<end)
        {
            int key=array[start];//初始化保存基元
            int i=startj;//初始化ij
            for(j=start+;j<=end;j++)

                if(array[j]<key)//如果此處元素小於基元則把此元素和i+處元素交換並將i加如大於或等於基元則繼續循環
                {
                    int temp=array[j];
                    array[j]=array[i+];
                    array[i+]=temp;
                    i++;
                }

            }
            array[start]=array[i];//交換i處元素和基元
            array[i]=key;
            QuickSort(array start i);//遞歸調用
            QuickSort(array i+ end);

        }

    }
    public static void main(String[] args)
    {
        int[] array=new int[]{};
        QuickSort(array arraylength);
        for(int i=;i<arraylength;i++)
        {
            Systemoutprintln((i+)+"th:"+array[i]);
        }
    }
}

From:http://tw.wingwit.com/Article/program/Java/JSP/201311/20237.html