數據結構與演算法幫你記之——歸併排序和快速排序

歸併排序和快速排序是面試常考的兩大排序，兩者平均時間複雜度均可以達到O(nlogn)。接下來將記錄一下這兩種排序的動圖原理顯示以及代碼的記憶方式。

歸併排序

一、動圖展示

動圖原文鏈接：https://blog.csdn.net/qq_36442947/article/details/81612870

二、做法及思路

在Java中，萬物皆對象。因此我們可以嘗試以面向對象的思想來進行編寫。

•  定義一個類MergeSort，併為其添加私有成員變數arr數組和數組長度arrayLength，當然，也需要添加必要的getset方法;
• 定義public的mergeSort方法作為向外提供的排序介面，這個方法主要實現：判斷數組是否為空，以及MSort函數的調用；
• 定義一個private的mSort方法作為正式開始，這個方法主要實現：將數組不斷拆分到不可拆為止，最後再將拆完的單個元素數組合併為兩個元素、四個元素等等。。。從動圖可以看到這個過程是迴圈往複的，因此可以考慮採用遞歸來實現，邊界條件就是開始角標小於結束角標；
• 定義一個merge方法專門用來將兩個小單元進行合併，合併的思路就像上面圖片那樣，這裡我們需要新建一個中間數組用來存放合併後的結果：
  • 一前一後有兩個指針，分別指向待合併兩部分的開頭；
  • 當前一個指向的元素更小時，令前一個元素賦值給中間數組tmp，前一個的指針向後移動；
  • 同樣的，當後一個指向的元素更小時，令後一個元素賦值給tmp，後一個指針也++；
  • 我們知道，這樣做並不能保證兩個數組同時完成自己的任務，因此最終一定會剩下左右其中一個數組還沒有全部放入tmp，這個時候就對沒有操作完的數組的剩餘部分全部放到tmp中；
  • 最後，我們並不想直接返回這個中間數組，因此需要將中間數組賦值給我們類中的arr數組。

過程還是較多的，但其中很大部分都是很容易想到的。上面說的難免有遺漏，可以看註釋：

 1 public class MergeSort {
 2     private int[] arr;
 3 
 4     private int arrayLength;
 5 
 6     public MergeSort(int arr[]){
 7         this.arr = arr;
 8         setArrayLength();
 9     }
10     public void setArr(int[] arr) {
11         this.arr = arr;
12         setArrayLength();
13     }
14 
15     public int[] getArr() {
16         return arr;
17     }
18 
19     public void setArrayLength() {
20         if(arr!=null)
21             this.arrayLength = arr.length;
22     }
23 
24     public void mergeSort(){
25         if(arr!=null){
26             int[] temp = new int[arrayLength];
27             mSort(0, arr.length-1, temp);
28         }
29         else{
30 //            throw new RuntimeException();
31             System.out.println("待排序數組為空");
32         }
33     }
34     /*保證共用一個temp，節省記憶體*/
35     private void mSort(int start, int end, int[] temp){
36         int center;
37         if(start<end){
38             center = (start+end)/2;
39             mSort(start, center, temp);
40             mSort(center+1, end, temp);
41             merge(start, center, end, temp);
42         }
43     }
44     /*left: the begin of left
45     * right: the end of right
46     * center: the end of left*/
47     private void merge(int leftSt, int center, int right, int[] temp){
48         int tmpPos = leftSt;
49         int rightSt = center+1;
50         while(leftSt<=center && rightSt<=right){
51             if(arr[leftSt]<arr[rightSt]){
52                 temp[tmpPos++]=arr[leftSt++];
53             }
54             else{
55                 temp[tmpPos++]=arr[rightSt++];
56             }
57         }
58         while(leftSt<=center){
59             temp[tmpPos++]=arr[leftSt++];
60         }
61         while(rightSt<=right){
62             temp[tmpPos++]=arr[rightSt++];
63         }
64 //向arr轉移tmp存儲的數組，這裡要註意：上面的操作已經打亂了left的位置，所以只能使用未被打亂的right角標，然後倒著賦值
65         for(int i=0; i<right-leftSt+1; i++, right--){
66             arr[right] = temp[right];
67         }
68     }
69 
70     public void printarr(){
71         for(int i=0; i<arrayLength; i++){
72             System.out.print(arr[i]+" ");
73         }
74     }
75 }

可以看到除了我們自己添加的一些非重要代碼，正式的歸併排序代碼僅有三十行左右。