快速排序是一種基于分治思想的排序算法 它主要分為以下幾步

1、一個(gè)數(shù)組按切分元素分成兩個(gè)數(shù)組，一個(gè)數(shù)組是大于切分元素的，另一個(gè)數(shù)組是小于切分元素的，

2、然后將這兩個(gè)部分按上面的思路獨(dú)立排序。

3、并將有序的子數(shù)組歸并 得到一個(gè)完整的數(shù)組。

這中間的關(guān)鍵就在于切分。

public class Quick {

       private static void sort(Comparable[] a, int l0, int l1) {

              // TODO Auto-generated method stub

              if(l0 > l1) return;   //做基本的判斷

              int l2=partition(a,l0,l1);  //調(diào)用方法實(shí)現(xiàn)按切分 得到最終a所在位置

              sort(a,l0,l2-1);   //排序比a小的數(shù)組

              sort(a,l2 1,l1);   //排序比a大的數(shù)組

       }

       private static int partition(Comparable[] a, int l0, int l1) {  //定義切分方法

              int i=l0;   int j=l1 1; //定義左右指針

              Comparable  v=a[0];  //獲得切分元素

              while(true){   掃描左右

                     while(less(a[ i],v))  if(i==l1)  break;

//調(diào)用 less方法做判斷a[i] 和v 直到a[i]大于v時(shí) 或者 i 到數(shù)組末尾時(shí)才停止

                     while(less(v,a[j--])) if(j==l0)  break;

//調(diào)用 less方法做判斷a[j] 和v 直到a[j]小于v時(shí) 或者 i 到數(shù)組頭時(shí)才停止

                     if(i>j)  break;   //做判斷  如果作為切分調(diào)出循環(huán)

                     exch(a,i,j);   調(diào)用exch（）方法來吧a[i]和a[j] 交換位置

              }

              exch(a,l0,j);   //調(diào)用exch（）方法 將v放入正確的位置

              return j;

       }

}

復(fù)雜度 NlgN 空間復(fù)雜度 lgN 其運(yùn)行效率與切分元素值有關(guān)  一把在排序之前先隨機(jī)整個(gè)數(shù)組。 快速排序也是最快的通用排序算法。

分治，字面上的解釋是“分而治之”，就是把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題。所以他有三個(gè)要點(diǎn)

1、劃分步：把輸入的問題劃分為k個(gè)子問題，并盡量使這k個(gè)子問題的規(guī)模大致相同

2、治理步：調(diào)用處理方法來處理問題。

3、組合步：組合步把各個(gè)子問題的解組合起來。

在快速排序中將一個(gè)數(shù)組按切分元素分成兩個(gè)數(shù)組就是在不同的劃分步。然后將這兩個(gè)部分按上面的思路獨(dú)立排序  這就是治理步。 最后將所有的子數(shù)組歸并到一個(gè)數(shù)組 就是組合步。