主定理顾瞻，主定理（英語：master theorem）提供了用漸近符號表示許多由分治法得到的遞推關系式的方法
在分治算法中德绿，分解荷荤、解決移稳、合并，使用遞歸解決一個個子問題再合并解決整體問題秒裕。對于此類算法的效率值袱蚓，可使用主定理推導確定几蜻。
主定理較為復雜喇潘，本文中提供一種簡化版本梭稚，以便理解：
關于主定理詳細推導，可自己畫遞歸樹推導弧烤。
上篇文章提到的歸并排序忱屑，每次均是將整體問題分為兩個子問題暇昂，數組不斷遞歸莺戒，到每個子問題規(guī)模為1急波，那么一共會遞歸lgN次。而合并子問題的效率為N澄暮，所以算法整體效率為NlgN名段。它對應了上圖中的示例1.
快速排序，快速排序是使用最廣泛的排序方法伸辟，高效麻惶，空間占用小信夫。
它的核心思想是窃蹋，選取關鍵值k忙迁，將數組中小于k的值放到k的左邊碎乃，大于k的數值放到k的右邊姊扔。再遞歸解決小于k段的排序和大于k段的排序。最終每個子問題規(guī)模為1梅誓，肯定就是有序的
核心代碼為：
public static int partition(int[] array, int p, int r){
int k = array[r];
int i = p - 1;
for (int j = p; j < r; j++) {
if (array[j] < k) {
i ++;
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
int temp = array[i + 1];
array[i + 1] = array[r];
array[r] = temp;
return i + 1;
}
partition方法，將數組分成三段梗掰，一段為小于k段嵌言，一段為大于k段及穗，一段為未排序段。當遍歷發(fā)現未排序段位置不對時埂陆，則將此值與大于k段值交換位置苛白，最終將k值插入合適位置
partition另外一種寫法
public static int partition2(int[] array, int p, int r){
int k = array[p];
int i = p;
int j = r;
while (i < j) {
while (i < j && array[j] > k) {
j--;
}
if (i < j) {
array[i] = array[j];
i ++;
}
while(i < j && array[i] < k){
i++;
}
if (i < j) {
array[j] = array[i];
j--;
}
}
array[i] = k;
return i;
}
partition2方法中產生一個冗余位置焚虱，數組中第一個元素已經被記錄在k中，所以第一個元素就是冗余元素鹃栽。從后開始遍歷躏率，如果某元素不在正確的位置上，則將此元素賦值到冗余位置上薇芝，之前的位置則成了新的冗余位置。
有了partition算法丰嘉，快排則非常簡單了夯到。
public static void quickSort(int[] array,int p, int r){
if (p < r) {
int q = partition(array, p, r);
quickSort(array, p, q - 1);
quickSort(array, q + 1, r);
}
}
從快排算法中可看出供嚎，快排算法包含三個方面峭状，將整體分成為2個n/2規(guī)模的子問題，同時再調用partition合并逼争，partition效率為N优床，所以對比上文中的主定理誓焦，可知快排的遞歸式為：
所以其效率為N*lgN。
特別注意：選取關鍵值k對整個算法非常重要杂伟，如果每次選中的值均為整個數組中最小的值移层，那么整體算法的效率將退化到n的平方赫粥。為了達到隨機目的，可在選取k時越平，采用隨機數方式频蛔，再將隨機等到的關鍵字調換位置到0或尾部。
本博中涉及的所有代碼均已上傳到github晦溪，歡迎訪問博主的github主頁
