快捷導(dǎo)航

快速排序的深入詳解以及java實現(xiàn)

更新時間：2013年07月03日 08:59:30 作者：

本篇文章是對java中的快速排序進行了詳細(xì)的分析介紹，需要的朋友參考下

快速排序作為一種高效的排序算法被廣泛應(yīng)用，SUN的JDK中的Arrays.sort 方法用的就是快排。
快排采用了經(jīng)典的分治思想（divide and conquer）：

Divide：選取一個基元X（一般選取數(shù)組第一個元素），通過某種分區(qū)操作（partitioning）將數(shù)組劃分為兩個部分：左半部分小于等于X，右半部分大于等于X。
Conquer： 左右兩個子數(shù)組遞歸地調(diào)用Divide過程。
Combine：快排作為就地排序算法（in place sort），不需要任何合并操作
可以看出快排的核心部分就是劃分過程（partitioning）,下面以一個實例來詳細(xì)解釋如何劃分?jǐn)?shù)組（圖取自于《算法導(dǎo)論》）
初始化：選取基元P=2，就是數(shù)組首元素。i=1,j=i+1=2 (數(shù)組下標(biāo)以1開頭)
循環(huán)不變量：2~i之間的元素都小于或等于P，i+1~j之間的元素都大于或等于P

循環(huán)過程：j從2到n，考察j位置的元素，如果大于等于P，就繼續(xù)循環(huán)。如果小于P，就將j位置的元素（不應(yīng)該出現(xiàn)在i+1~j這個區(qū)間）和i+1位置(交換之后仍在i+1~j區(qū)間)的元素交換位置，同時將i+1.這樣就維持了循環(huán)不變量（見上述循環(huán)不變量說明）。直到j(luò)=n，完成最后一次循環(huán)操作。
要注意的是在完成循環(huán)后，還需要將i位置的元素和數(shù)組首元素交換以滿足我們最先設(shè)定的要求（對應(yīng)圖中的第i步）。

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

復(fù)制代碼代碼如下:

public class QuickSort {
    private static void QuickSort(int[] array,int start,int end)
    {
        if(start<end)
        {
            int key=array[start];//初始化保存基元
            int i=start,j;//初始化i,j
            for(j=start+1;j<=end;j++)

                if(array[j]<key)//如果此處元素小于基元，則把此元素和i+1處元素交換，并將i加1，如大于或等于基元則繼續(xù)循環(huán)
                {
                    int temp=array[j];
                    array[j]=array[i+1];
                    array[i+1]=temp;
                    i++;
                }

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

        }

    }
    public static void main(String[] args)
    {
        int[] array=new int[]{11,213,134,44,77,78,23,43};
        QuickSort(array, 0, array.length-1);
        for(int i=0;i<array.length;i++)
        {
            System.out.println((i+1)+"th:"+array[i]);
        }
    }
}