摘要：交換器兩個數(shù)組中的元素比較排序過程中，一定會有元素的交換操作。如果數(shù)組的長度小于默認(rèn)值是的話，再判斷，如果數(shù)組長度小于值為的話，那么就會用插入排序，否則就會使用雙軸快速排序。回合結(jié)束后，最后的元素是整個數(shù)組最大的數(shù)。

今天來回顧一下簡單的排序思想，留作今后的復(fù)習(xí)和備份用。本篇是非常非?；A(chǔ)的，甚至都不會講實(shí)際項(xiàng)目真正能用的排序方法，譬如雙軸快速排序 。寫的不好請多多諒解。

想要解鎖更多新姿勢？請?jiān)L問http://blog.tengshe789.tech/

為了保持代碼的整潔，先創(chuàng)造好對數(shù)器和相關(guān)功能性函數(shù)。

兩個數(shù)組中的元素比較排序過程中，一定會有元素的交換操作。為了保持代碼的整潔，先寫出交換操作的函數(shù)。

public static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

自己編數(shù)組太麻煩了，讓他自己生產(chǎn)吧

public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

對數(shù)器其實(shí)就是一個絕對正確但是復(fù)雜度不好的方法。

public static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

說說Arrays.sort()的邏輯吧。數(shù)組進(jìn)入方法，先判斷。如果數(shù)組的長度小于QUICKSORT_THRESHOLD（默認(rèn)值是286）的話，再判斷，如果數(shù)組長度小于INSERTION_SORT_THRESHOLD(值為47)的話，那么就會用插入排序 ，否則就會使用雙軸快速排序。

如果大于286呢，它就會堅(jiān)持?jǐn)?shù)組的連續(xù)升序和連續(xù)降序性好不好，如果好的話就用歸并排序，不好的話就用快速排序。

比較兩個數(shù)組一不一樣~

public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

public static void printArray(int[] arr) {
   if (arr == null) {
      return;
   }
   for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
   }
   System.out.println();
}

public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

public static void main(String[] args) {
   int testTime = 500000;
   int maxSize = 100;
   int maxValue = 100;
   boolean succeed = true;
   for (int i = 0; i < testTime; i++) {
      int[] arr1 = generateRandomArray(maxSize, maxValue);
      int[] arr2 = copyArray(arr1);
      bubbleSort(arr1);
      comparator(arr2);
      if (!isEqual(arr1, arr2)) {
         succeed = false;
         break;
      }
   }
   System.out.println(succeed ? "牛逼，算法對了!" : "?!");

   int[] arr = generateRandomArray(maxSize, maxValue);
   printArray(arr);
   bubbleSort(arr);//測試的算法
   printArray(arr);
}

腦闊疼

冒泡排序算法的原理如下：

比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。此時(shí)這兩個數(shù)，永遠(yuǎn)是后面的數(shù)大。

第一回合將每一對相鄰元素做同樣的工作?；睾辖Y(jié)束后，最后的元素是整個數(shù)組最大的數(shù)。

第二回合...第n回合過程中，對除了最后一個元素重復(fù)以上的步驟。

public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int end = arr.length - 1; end > 0; end--) {//end最后的數(shù)
            for (int i = 0; i < e; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);//交換
                }
            }
        }
    }

時(shí)間復(fù)雜度：O(N2)

額外空間復(fù)雜度：O(1)

1.第一回合，將指針指向第一個元素，將第一個元素和剩余的元素比較，最小的元素放到一號位置。

2.第二回合...第n回合過程中，指針加一。對除了第一個元素重復(fù)以上的步驟。

public static void selectionSort(int[] arr) {
   if (arr == null || arr.length < 2) {
      return;
   }
   for (int i = 0; i < arr.length - 1; i++) {
      int minIndex = i;
      for (int j = i + 1; j < arr.length; j++) {
         minIndex = arr[j] < arr[minIndex] ? j : minIndex;
      }
      swap(arr, i, minIndex);
   }
}

時(shí)間復(fù)雜度：O(N2)

額外空間復(fù)雜度：O(1)

1.第一回合，比較第一個元素和第二個元素大小，大的放在第二個位置上

2.第二回合，將第三個元素與第二、第一個元素比較，大的放在第三個位置上

3.輪回

public static void insertionSort(int[] arr) {
   if (arr == null || arr.length < 2) {
      return;
   }
   for (int i = 1; i < arr.length; i++) {
      for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
         swap(arr, j, j + 1);
      }
   }
}

時(shí)間復(fù)雜度：O(N2)

額外空間復(fù)雜度：O(1)

堆其實(shí)就是完全二叉樹，看堆要首先知道大頂堆、小頂堆。

每個結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值，稱為大頂堆；或者每個結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值，稱為小頂堆。

大頂堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小頂堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

將待排序序列構(gòu)造成一個大頂堆（升序采用大頂堆，降序采用小頂堆），此時(shí)，整個序列的最大值就是堆頂?shù)母?jié)點(diǎn)。將其與末尾元素進(jìn)行交換，此時(shí)末尾就為最大值。然后將剩余n-1個元素重新構(gòu)造成一個堆，這樣會得到n個元素的次小值。如此反復(fù)執(zhí)行，便能得到一個有序序列了

public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //0-i之間生成大根堆這種結(jié)構(gòu)
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int size = arr.length;//定義數(shù)組大小，可以判斷是否越界
        swap(arr, 0, --size);
        while (size > 0) {
            heapify(arr, 0, size);
            swap(arr, 0, --size);
        }
    }
    //生成大根堆這種結(jié)構(gòu)
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {//如果我這個節(jié)點(diǎn)比父節(jié)點(diǎn)大
            swap(arr, index, (index - 1) / 2);//交換
            index = (index - 1) / 2;//回到父位置繼續(xù)
        }
    }
    //將數(shù)值小的元素往下沉
    public static void heapify(int[] arr, int index, int size) {
        int left = index * 2 + 1;
        while (left < size) {//左孩子在堆上，沒越界
            int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;//找出左右孩子中最大的數(shù)
            largest = arr[largest] > arr[index] ? largest : index;//和父比較
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;//回到較大節(jié)點(diǎn)
            left = index * 2 + 1;
        }
    }

如果只是建立堆的過程，時(shí)間復(fù)雜度為O(N)

時(shí)間復(fù)雜度O(N*logN)

額外空間復(fù)雜度O(1)

快速排序不是一種穩(wěn)定的排序算法，也就是說，多個相同的值的相對位置也許會在算法結(jié)束時(shí)產(chǎn)生變動。

假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

我先說說經(jīng)典快排的思路吧。

將數(shù)組分成兩部分，一部分是小于等于某個數(shù)的，一部分是大于等于某個數(shù)的。這兩部分初始指針在數(shù)組的左(L)右(R)兩頭，此時(shí)L和R分別是一個邊界點(diǎn)。

1.先定義less區(qū)域和more區(qū)域，代表比數(shù)組中某一個數(shù)更小更大的區(qū)域。初始less區(qū)域是L-1以左的部分，more區(qū)域是R以右的區(qū)域

2.第一回合，從數(shù)組左邊開始。若L指針指的節(jié)點(diǎn)值小于某個數(shù)值，less區(qū)域向右移動一個位置 swap(arr,++less,L++);，L節(jié)點(diǎn)位置+1準(zhǔn)備下一個回合；若它大于這個數(shù)值，more區(qū)域向左擴(kuò)張一格，然后將這個節(jié)點(diǎn)放到more區(qū)域swap(arr,--more,L++);，L節(jié)點(diǎn)位置+1準(zhǔn)備下一個回合；若他等于這個數(shù)值，什么也不管，只是L節(jié)點(diǎn)位置+1準(zhǔn)備下一個回合。

3.重復(fù)上述過程，得到了一個數(shù)組，他的L指針右邊時(shí)小于某個數(shù)的，R的右邊時(shí)大于某個數(shù)的。[L,R]這個區(qū)間是等于某個數(shù)的。

4.返回這個都是相同數(shù)的數(shù)組的左邊界、右邊界

5.不斷遞歸

經(jīng)典快排有一個弊端。左部分和右部分的規(guī)模不一樣或者有一個部分規(guī)模特別大，算法效率會變差。舉個栗子，如果我有個數(shù)組[1,1,3,4,7,6,1,2,1,5,1,7]，我指定的某個數(shù)字是7，那么那么排序后就變成了[1，1，1，1，1,2,3,4,5,6,7],經(jīng)典快排結(jié)束后只搞定了一個一個區(qū)間（<7的區(qū)間），復(fù)雜度就從理想狀態(tài)下的O（N）變成了O（N2）

然后就有了改進(jìn)后的隨機(jī)快排。

隨機(jī)快排比經(jīng)典快排多了一個選隨機(jī)數(shù)的過程 swap(arr, L + (int) (Math.random() * (R - L + 1)), R);。就是隨機(jī)生成某個數(shù)，這樣生成的區(qū)間雖然也會出現(xiàn)上述經(jīng)典快排的惡劣情況，但是此時(shí)的復(fù)雜度就從原來的惡劣事件變成了有概率惡劣事件，但總體期望是好的。這就變成了一個概率問題。

以下為隨機(jī)快排

//隨機(jī)快速排序
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr,int L,int R){
        if (L arr[R]){
                swap(arr,--more,L++);
            }else{
                L++;
            }
        }
        swap(arr,more,R);
        return new int[]{less+1,more-1};
    }

科學(xué)家數(shù)學(xué)證明，長期期望的時(shí)間復(fù)雜度為O(logN*N)

快速排序可以做到穩(wěn)定性問題，非常難，要知道的可以谷歌“01 stable sort” ，反正我不會。

1.和上題一樣，先定義左邊界L右邊界R數(shù)組中，然后定義一個中間值mid = (r-l)/2

2.遞歸，在邊界內(nèi)部不斷的找中間值mid

//歸并排序
public static void mergeSort(int[] arr){
    if (arr==null || arr.length <2){
        return;
    }
    mergeSort(arr,0,arr.length-1);
}

private static void mergeSort(int[] arr, int l, int r) {
    if (l == r){
        return;
    }
    int mid = l + ((r - l) >> 1); //(r-l)/2
    mergeSort(arr,l,mid);
    mergeSort(arr,mid+1,r);
    merge(arr, l, mid, r);
}

時(shí)間復(fù)雜度O(N*logN)

額外空間復(fù)雜度O(N)，歸并排序的額外空間復(fù)雜度可以變成O(1)，但是非常難，我沒花時(shí)間研究，要知道的可以谷歌“歸并排序 內(nèi)部緩存法”

這里的時(shí)間復(fù)雜度怎么算出來的呢？有一個master定理：

T(N) = a*T(N/b) + O(N^d)

其中 a >= 1 and b > 1 是常量，其表示的意義是n表示問題的規(guī)模，a表示遞歸的次數(shù)也就是生成的子問題數(shù)，b表示每次遞歸是原來的1/b之一個規(guī)模。 如下：

1) log(b,a) > d -> 復(fù)雜度為O(N^log(b,a))

2) log(b,a) = d -> 復(fù)雜度為O(N^d * logN)

3) log(b,a) < d -> 復(fù)雜度為O(N^d)

這里，歸并排序中b=2，a=2.

非基于比較的排序，與被排序的樣本的實(shí)際數(shù)據(jù)狀況很有關(guān)系，所以實(shí)際中并不經(jīng)常使用

1.找到一個數(shù)組中最大數(shù)的值

2.定義（最大數(shù)+1）個桶

3.將數(shù)組的數(shù)放到對應(yīng)編號相同的桶中，每放進(jìn)一個數(shù)，桶里面的數(shù)值加一

4.依次從小輸出這個桶，桶里的元素出現(xiàn)幾次就輸出幾個桶的編號

// only for 0~200 value
    public static void bucketSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        int[] bucket = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i]]++;
        }
        int i = 0;
        for (int j = 0; j < bucket.length; j++) {
            while (bucket[j]-- > 0) {
                arr[i++] = j;
            }
        }
    }

時(shí)間復(fù)雜度O(N)

額外空間復(fù)雜度O(N)