分而治之(又稱D&C)

書中舉了一個例子，假設你是農場主，有一塊土地，如圖所示:

?

你要將這塊地均勻分成方塊，且分出的方塊要盡可能大。

?

?

從圖上看，顯然是不符合預期結果的。

那么如何將一塊地均勻分成方塊，并確保分出的方塊是最大的呢？使用D&C策略。

(1)D&C算法是遞歸的;
(2)使用D&C解決問題的過程包括兩個步驟:
a.找出基線條件，這種條件必須盡可能簡單;
b.不斷將問題分解(或者說縮小規模)，直到符合基線條件;

就如何保證分出的方塊是最大的呢？《算法圖解》中的快速排序一章提到了歐幾里得算法。

什么是歐幾里得算法?
歐幾里得算法又稱輾轉相除法，是指用于計算兩個正整數a,b的最大公約數。
應用領域有數學和計算機兩個方面。

舉個代碼例子說一下歐幾里得算法:

package cn.pratice.simple;public class Euclid {public static void main(String[] args) {int m = 63;int n = 18;int remainer = 0;while(n!=0) {remainer = m % n;m = n;n = remainer;}System.out.println(m);} }

?

最終的結果是9，正好63和18的最大公因數也是9.
其中也體現著分而治之的思想。記住，分而治之并非可用于解決問題的算法而是一種解決問題的思路。

再舉個例子說明，如圖所示:

?

需要將這些數字相加，并返回結果，使用循環很容易完成這種任務，以Java為例:

?

package cn.pratice.simple;public class Euclid {public static void main(String[] args) {int []num = new int[] {2,4,6};int total = 0;for (int i = 0; i < num.length; i++) {total += num[i];}System.out.println(total);} }

快速排序

快速排序是一種常用的排序算法，比選擇排序快的多。
代碼示例如下(快速排序):

package cn.pratice.simple;public class QuickSort {//聲明靜態的 getMiddle() 方法，該方法需要返回一個 int 類型的參數值，在該方法中傳入 3 個參數public static int getMiddle(int[] list,int low,int high) {int tmp = list[low];//數組的第一個值作為中軸(分界點或關鍵數據)while(low<high) {while(low<high && list[high]>tmp) {high--;}list[low] = list[high];//比中軸小的記錄移到低端while(low<high&&list[low]<tmp) {low++;}list[high]=list[low];//比中軸大的記錄移到高端 }list[low] = tmp;//中軸記錄到尾return low;}//創建靜態的 unckSort() 方法，在該方法中判斷 low 參數是否小于 high 參數，如果是則調用 getMiddle() 方法，將數組一分為二，并且調用自身的方法進行遞歸排序public static void unckSort(int[] list,int low,int high) {if(low<high) {int middle = getMiddle(list,low,high);//將list數組一分為二unckSort(list,low,middle-1);//對低字表進行遞歸排序unckSort(list,middle+1,high);//對高字表進行遞歸排序 }}//聲明靜態的 quick() 方法，在該方法中判斷傳入的數組是否為空，如果不為空，則調用 unckSort() 方法進行排序public static void quick(int[] str) {if(str.length>0) {//查看數組是否為空unckSort(str,0,str.length-1);}}//測試public static void main(String[] args) {int[] number = {13,15,24,99,14,11,1,2,3};System.out.println("排序前:");for (int i : number) {System.out.print(i+" ");}quick(number);System.out.println("\r排序后:");for (int i : number) {System.out.print(i+" ");}} }

此示例來自Java數組排序：Java快速排序（Quicksort）法

沒有什么比代碼示例來的直接痛快。

再談大O表示法

快速排序的獨特之處在于，其速度取決于選擇的基準值。

常見的大O運行時間圖，如下:

?

上述圖表中的時間是基于每秒執行10次操作計算得到的。這些數據并不準確，這里提供它們只是想讓你對這些運行時間的差別有大致認識。實際上，計算機每秒執行的操作遠遠不止10次。 在該節中，作者說合并排序比選擇排序要快的多。合并排序，用數學公式表示為O(n log n)，而選擇排序為O(n的2次方)。
合并代碼排序例子如下:

package cn.pratice.simple;import java.util.Arrays;public class MergeSort {private static void mergeSort(int[] original) {if (original == null) {throw new NullPointerException("The array can not be null !!!");}int length = original.length;if (length > 1) {int middle = length / 2;int partitionA[] = Arrays.copyOfRange(original, 0, middle);// 拆分問題規模int partitionB[] = Arrays.copyOfRange(original, middle, length);// 遞歸調用 mergeSort(partitionA);mergeSort(partitionB);sort(partitionA, partitionB, original);}}private static void sort(int[] partitionA, int[] partitionB, int[] original) {int i = 0;int j = 0;int k = 0;while (i < partitionA.length && j < partitionB.length) {if (partitionA[i] <= partitionB[j]) {original[k] = partitionA[i];i++;} else {original[k] = partitionB[j];j++;}k++;}if (i == partitionA.length) {while (k < original.length) {original[k] = partitionB[j];k++;j++;}} else if (j == partitionB.length) {while (k < original.length) {original[k] = partitionA[i];k++;i++;}}}private static void print(int[] array) {if (array == null) {throw new NullPointerException("The array can not be null !!!");}StringBuilder sb = new StringBuilder("[");for (int element : array) {sb.append(element + ", ");}sb.replace(sb.length() - 2, sb.length(), "]");System.out.println(sb.toString());}public static void main(String[] args) {long startTime = System.currentTimeMillis(); //獲取開始時間int original[] = new int[] { 13,15,24,99,14,11,1,2,3 };for (int i = 0; i < original.length; i++) {System.out.print(original[i]+" ");}mergeSort(original);print(original);long endTime = System.currentTimeMillis(); //獲取結束時間 System.out.println("程序運行時間：" + (endTime - startTime) + "ms"); //輸出程序運行時間 } }

此示例來自
java實現合并排序算法

比較快速排序與合并排序

還是以上面的代碼例子為例:
快速排序代碼例子，如下:

public static int getMiddle(int[] list,int low,int high) {int tmp = list[low];//數組的第一個值作為中軸(分界點或關鍵數據)while(low<high) {while(low<high && list[high]>tmp) {high--;}list[low] = list[high];//比中軸小的記錄移到低端while(low<high&&list[low]<tmp) {low++;}list[high]=list[low];//比中軸大的記錄移到高端 }list[low] = tmp;//中軸記錄到尾return low;}//創建靜態的 unckSort() 方法，在該方法中判斷 low 參數是否小于 high 參數，如果是則調用 getMiddle() 方法，將數組一分為二，并且調用自身的方法進行遞歸排序public static void unckSort(int[] list,int low,int high) {if(low<high) {int middle = getMiddle(list,low,high);//將list數組一分為二unckSort(list,low,middle-1);//對低字表進行遞歸排序unckSort(list,middle+1,high);//對高字表進行遞歸排序 }}//聲明靜態的 quick() 方法，在該方法中判斷傳入的數組是否為空，如果不為空，則調用 unckSort() 方法進行排序public static void quick(int[] str) {if(str.length>0) {//查看數組是否為空unckSort(str,0,str.length-1);}}//測試public static void main(String[] args) {long startTime = System.currentTimeMillis(); //獲取開始時間int[] number = { 13,15,24,99,14,11,1,2,3,2,32,4321,432,3,14,153,23,42,12,34,15,312,12,43,3214,43214,43214,43214,12,2432,12,34,24,4532,1234};quick(number);for (int i : number) {System.out.print(i+" ");}long endTime = System.currentTimeMillis(); //獲取結束時間 System.out.println("程序運行時間：" + (endTime - startTime) + "ms"); //輸出程序運行時間 } }

輸出結果，如圖:

半天看不到輸出結果，而程序仍在運行中。如果將數組中的元素還原為原來那幾個，則很快看到結果。

合并代碼例子，如下:

package cn.pratice.simple;import java.util.Arrays;public class MergeSort {private static void mergeSort(int[] original) {if (original == null) {throw new NullPointerException("The array can not be null !!!");}int length = original.length;if (length > 1) {int middle = length / 2;int partitionA[] = Arrays.copyOfRange(original, 0, middle);// 拆分問題規模int partitionB[] = Arrays.copyOfRange(original, middle, length);// 遞歸調用 mergeSort(partitionA);mergeSort(partitionB);sort(partitionA, partitionB, original);}}private static void sort(int[] partitionA, int[] partitionB, int[] original) {int i = 0;int j = 0;int k = 0;while (i < partitionA.length && j < partitionB.length) {if (partitionA[i] <= partitionB[j]) {original[k] = partitionA[i];i++;} else {original[k] = partitionB[j];j++;}k++;}if (i == partitionA.length) {while (k < original.length) {original[k] = partitionB[j];k++;j++;}} else if (j == partitionB.length) {while (k < original.length) {original[k] = partitionA[i];k++;i++;}}}private static void print(int[] array) {if (array == null) {throw new NullPointerException("The array can not be null !!!");}StringBuilder sb = new StringBuilder("[");for (int element : array) {sb.append(element + ", ");}sb.replace(sb.length() - 2, sb.length(), "]");System.out.println(sb.toString());}public static void main(String[] args) {long startTime = System.currentTimeMillis(); //獲取開始時間int original[] = new int[] { 13,15,24,99,14,11,1,2,3,2,32,4321,432,3,14,153,23,42,12,34,15,312,12,43,3214,43214,43214,43214,12,2432,12,34,24,4532,1234};for (int i = 0; i < original.length; i++) {System.out.print(original[i]+" ");}mergeSort(original);print(original);long endTime = System.currentTimeMillis(); //獲取結束時間 System.out.println("程序運行時間：" + (endTime - startTime) + "ms"); //輸出程序運行時間 } }

輸出結果，如圖:

通過兩者對比，我們很容易得出合并排序比快速排序快。

參考這個合并排序和快速排序執行時間比較

作者通過實驗得出一個結論:當數據量較小的時候，快速排序比合并排序運行時間要短，運行時間短就表示快，但是當數據量大的時候，合并排序比快速排序運行時間要短。
由此通過我上述的代碼實驗和該文章作者試驗，可證實這個結論。

轉載于:https://www.cnblogs.com/youcong/p/10957896.html

總結

以上是生活随笔為你收集整理的算法图解之快速排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。