前言

冒泡 + 快排 + 歸并，這三種排序算法太過經(jīng)典，但又很容易忘了。雖然一開始接觸雀氏這些算法雀氏有些頭大，但時間長了也還好。主要是回憶這些算法干了啥很耗時間。

如果在筆試時要寫一個o(nlogn)的排序算法，如果不能立刻寫出 快排或者歸并，未免有些太浪費時間了。

故寫這篇文章用于記錄

tip: 一下內(nèi)容均實現(xiàn)升序排序

冒泡排序

所謂冒泡，就是每一輪都排出一個最大的元素，把他丟在末尾。

如上圖所示，5個元素的數(shù)組我們需要5輪遍歷，每次遍歷可以排出一個當前遍歷區(qū)域內(nèi)最大的元素

而確定最大元素的方法起始也很簡單。每一次遍歷，我們都和其前一個元素對比，也就是比較arr[j - 1]，arr[j]。如果 arr[j - 1] > arr[j]，則交換，否則不變。這樣的比較方式讓算法趨向于將大的元素向右邊送，直到將最大的元素送到最右側(cè)

當?shù)谝惠喤判蛲瓿珊?#xff0c;第二輪排序的范圍則被縮小。因為已知最大元素在最右側(cè)，那么無需遍歷最右側(cè)元素。

第三輪同理，無需遍歷倒數(shù)第二個元素。以此類推

import java.util.*;public class Main {public static void main(String[] args) {// 冒泡int N;Scanner sc = new Scanner(System.in);N = sc.nextInt();int[] arr = new int[N];for (int i = 0; i < N; ++i) {arr[i] = sc.nextInt();}// sort 核心for (int i = 0; i < N; ++i) {for (int j = 1; j < N - i; ++j) {if (arr[j - 1] > arr[j]) {int tmp = arr[j];arr[j] = arr[j - 1];arr[j - 1] = tmp;}}}// printfor (int i = 0; i < N; ++i) {System.out.print(arr[i]);if (i < N - 1) System.out.print(" ");}}
}

快速排序

所謂快速排序，和俄羅斯套娃很像。我們想要快速排序俄羅斯套娃，可以做如下操作：

1. 選出一個基準娃
2. 遍歷所有娃，小的放左邊，大的放右邊
3. 如果兩側(cè)的娃不用排序，則終止
4. 對基準娃左右兩側(cè)的娃娃們做1，2，3操作

快排也是類似的

不同的是，俄羅斯套娃是將別的元素擺放到基準娃的兩側(cè)；快排是通過交換左右兩側(cè)元素，定位到base的位置

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int[] arr = new int[N];for (int i = 0; i < N; ++i) {arr[i] = sc.nextInt();}// quickSortquickSort(arr, 0, N - 1);// printfor (int i = 0; i < N; ++i) {System.out.print(arr[i]);if (i < N - 1) System.out.print(" ");}}public static void quickSort(int[] arr, int lef, int rig) {if (lef >= rig) return;int base = arr[lef];int lp = lef, rp = rig;while (lp < rp) {// 右指針尋找到<base的數(shù)for (; rp > lp && arr[rp] >= base; --rp);arr[lp] = arr[rp];// 左指針尋找到>base的數(shù)for (; rp > lp && arr[lp] <= base; ++lp);arr[rp] = arr[lp];}arr[lp] = base;quickSort(arr, lef, lp - 1);quickSort(arr, lp + 1, rig);}
}

tip: 快排有一些注意點需要強調(diào)

1. 遞歸終止條件，快排起始也是遞歸，是遞歸就需要終止條件。本題遞歸的終止條件就是lef >= rig，排序范圍左側(cè)端點不在右側(cè)端點左邊
2. for (; rp > lp && arr[rp] >= base; --rp); 這個for相當于右側(cè)小人，尋找 小于 base的數(shù)。因為是尋找小于，因此循環(huán)條件是 >= base就一直尋找
3. 如果base是數(shù)組第一個元素，那么先走動的必須是右側(cè)小人。因為數(shù)組最左側(cè)元素，我們用base進行備份，先走右側(cè)小人覆蓋最左側(cè)元素不會丟失base信息

歸并排序

歸并排序就有點蛋疼了，雖然代碼極少（相對來說），但思維量如果不熟悉分治的情況下還是比較大的。

本文并非專業(yè)的介紹文章，感興趣的讀者可以詳細閱讀這篇文章

歸并排序大致思路如下：

1. 往死里拆分數(shù)組，具體拆分的方式就是對半拆
2. 當拆分到不能再拆，局部合并

其中，mergeSort干的任務是對lef ~ right范圍內(nèi)的數(shù)組歸并排序，merge屬于歸并排序中，并的部分。

因為遞歸的原因，上層遞歸棧merge數(shù)組，以mid為臨界區(qū)域，left ~ mid，mid + 1 ~ right這兩段數(shù)組，內(nèi)部元素都是局部遞增的。這個原因很簡單，因為遞歸的特性，回溯到上層棧，底層棧一定把功能實現(xiàn)好。

這有點類似于甩鍋，我排序全部數(shù)組太累了，于是找兩個小弟，一個歸并排序左邊，一個排序右邊。我不許用關(guān)心小弟怎么排序，我只需要知道，等小弟回來（回溯），我就只需要排序兩個有序數(shù)組

所以要實現(xiàn)merge的功能，起始就是對兩段有序數(shù)組進行排序

假設兩段數(shù)組分別是arr1, arr2（實際上只有arr，為了方便敘述，我們說成兩段）具體的排法是雙指針遍歷。

對于arr1, arr2。誰的元素大，誰就把元素按序存儲到tmp中。

import java.util.*;public class Main {private static int[] tmp;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int[] arr = new int[N];tmp = new int[N];for (int i = 0; i < N; ++i) {arr[i] = sc.nextInt();}// mergemergeSort(arr, 0, N - 1);// printfor (int i = 0; i < N; ++i) {System.out.print(arr[i]);if (i < N - 1)System.out.print(" ");}sc.close();}public static void mergeSort(int[] arr, int left, int right) {if (left < right) {int mid = (left + right) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, right);}}public static void merge(int[] arr, int left, int right) {int mid = (left + right) / 2;        int lp = left, rp = mid + 1, k = left;while (lp <= mid && rp <= right) {if (arr[lp] < arr[rp]) tmp[left++] = arr[lp++];else tmp[left++] = arr[rp++]; }while (lp <= mid) tmp[left++] = arr[lp++]; // 左區(qū)間沒迭代完while (rp <= right) tmp[left++] = arr[rp++]; // 右區(qū)間沒迭代完for (; k <= right; ++k) arr[k] = tmp[k]; // copy}
}

另外，值得一提的是，歸并是上述三種排序中最快的。冒泡，快排都沒有AC