Java排序算法知多少
今天阿粉就來談一下這個 Java 中的各種排序的算法，因為之前遇到了一個面試高級開發，結果竟然出了一個 九九乘法表的題，阿粉當時聽完讀者說的，瞬間就明白是什么意思了，這感覺有點忽悠人，但是實際上卻是面試官想要考察你的排序算法的事了，也有可能是真的無聊。
排序算法
什么是排序算法，實際上這個沒有太多的說法，意思表達清楚就可以了，所謂排序，就是一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減地排列起來的操作。
排序算法的種類可以說是比較的多樣化了，對時間，對空間的效率，不同的排序算法的優缺點是不一樣的，有些是用時間換空間的，有些是拿空間換時間的，今天阿粉就來一一列舉一下。
冒泡排序
什么是冒泡排序呢?
冒泡排序就是依次比較相鄰的兩個數，將小數放在前面，大數放在后面。
就像一個泡泡，一個泡泡一樣，直接往起漂。
冒泡排序就是依次比較相鄰的兩個數，將小數放在前面，大數放在后面。
實際上比較的過程就是這個樣子的：
第一次比較：
首先比較第1個和第2個數，將小數放前面，大數放后面，然后比較第2個數和第3個數，小數放前面，大數放后面，然后一直比較到最后，這樣，最大的一個數就放到了最后面了。
第二次比較：
首先比較第1個和第2個數，將小數放前面，大數放后面，然后比較到倒數第二個數，然后第二次比較結束，這樣在最后一個位置的就是最大的，然后倒數第二個位置的是第二大的數。
然后一直這樣往下執行，第三次就是來取第三個數，這樣依次循環，這樣說大家肯定都是能理解的，假設需要排序的序列的個數是n，則需要經過n-1輪，最終完成排序。在第一輪中，比較的次數是n-1次，之后每輪減少1次。
我們接下來使用代碼來實現一下：
- public static void main(int[] a) {
- int temp;
- //需要比較n-1輪
- for (int i = 0; i < a.length-1; i++) {
- //根據a.length-i-1，每輪需要比較的次數逐輪減少1次
- for (int j = 0; j < a.length-i-1 ; j++) {
- //相鄰數進行比較，符合條件進行替換
- if (a[j] > a[j+1]) {
- temp = a[j];
- a[j] = a[j+1];
- a[j+1] = temp;
- }
- }
- }
- }
插入排序
插入排序的種類比較多
- 直接插入排序
- 二分插入排序
- 希爾排序
這些排序方式全都是屬于插入式排序的，
我們先來看看直接插入排序：
- 比較的過程是這個樣子的，數組的第二個數據開始往前比較，即一開始用第二個數和他前面的一個比較，如果 符合條件則讓他們交換位置。
- 假如我們給定一個數組，我們要按照從小到大排序，數組為 [3,1,4,6,5,17,12,11] 這時候，第一步就是拿著 1 和 3 進行比較，如果 1 小于 3 ，這個時候，就把 1 和 3 換個位置，[1,3,4,6,5,17,12,11] .
接下來再用第三個數和第二個比較，符合則交換，但是此處還得繼續往前比較 ，就是用 4 和 3 和 1 分別去比較，然后一直這么重復下去。直到把所有的數據都排列完之后，就得到了我們想要的結果，我們來寫個代碼看看是什么樣子的。
- public static void basal(int[] array) {
- // 從第二項開始
- if (array == null || array.length < 2) {
- return;
- }
- for (int i = 1; i < array.length; i++) {
- int cur = array[i];
- // cur 落地標識，防止待插入的數最小
- boolean flag = false;
- // 倒序遍歷，不斷移位
- for (int j = i - 1; j > -1; j--) {
- if (cur < array[j]) {
- array[j + 1] = array[j];
- }else {
- array[j + 1] = cur;
- flag = true;
- break;
- }
- }
- if (!flag) {
- array[0] = cur;
- }
- }
- }
- }
既然我們之前都說了，插入排序的方法有很多種，那么我們也得說說其他的插入排序，然后在看看他們都有什么不同的地方，大家說對不對呢?
既然我們剛才都說了排序每次都要講數組后移，但是我們之前的判斷條件上卻是可以優化出來的，這樣優化優化的就衍生出來了其他的不同的插入排序，接下來我們就來看看這個二分查找插入排序。
二分查找法插入排序
優化直接插入排序的核心在于：快速定位當前數字待插入的位置。在一個有序數組中查找一個給定的值，最快的方法無疑是二分查找法，至少在阿粉的心中如果想到優化的時候肯定是第一時間選擇的就是可不可以使用二分查找法呢?
我們先來看看代碼實現，然后再看看他有什么缺點，為啥有很多人都不選擇使用二分查找插入排序。
- // 利用系統自帶的二分查找法，定位插入位置
- // 不穩定排序
- public static void optimized(int[] array) {
- if (array == null || array.length < 2) {
- return;
- }
- for (int i = 1; i < array.length; i++) { int cur = array[i];
- int[] sorted = Arrays.copyOf(array, i);
- int index = Arrays.binarySearch(sorted,cur); if (index < 0) {
- index = -(index + 1);
- }
- for (int j = i - 1; j > index - 1; j--) {
- array[j + 1] = array[j];
- }
- array[index] = cur;
- }
- }
在這其中，阿粉使用了系統自帶的Arrays，然后進行了二分查找插入排序，為什么這么用呢?在JDK中提供了 Arrays.binarySearch()，方法的入參需要將有序數組傳遞進去 來進行實現，為什么不用這種方法呢?
假如在排序之前，有兩個數相等，但是在排序結束之后，它們兩個有可能改變順序這就是說明該排序算法具有不穩定性。這就是大家所說的穩定性。
既然都有這種不穩定的排序，那是不是就應該存在穩定的排序呢?對沒錯，就是有，那么什么是穩定的排序呢?對，大家沒有想錯，冒泡排序就是穩定排序，因為冒泡排序只在相鄰元素大小不符合要求時才調換他們的位置,它并不改變相同元素之間的相對順序, 因此它是穩定的排序算法。
既然我們剛才說了這個排序中還有希爾排序，我們再來看看希爾排序。
希爾排序
說實話，阿粉第一次知道這個排序的時候，就想說，是不是一個叫做希爾的人改進的，結果，發現還真是，希爾排序，又叫做((縮小增量排序)，因 D.L.Shell 于 1959 年提出而得名，實際上應該叫做Shell's Sort。
希爾排序是先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。
實際上就相當于先進行了一個簡單的分組，將待排序數組按照步長gap進行分組，然后將每組的元素利用直接插入排序的方法進行排序;每次再將gap折半減小，循環上述操作;當gap=1時，利用直接插入，完成排序。
代碼實現是這個樣子的
- public static void sort(int[] a) {
- int length = a.length;
- int h = 1;
- while (h < length / 3) h = 3 * h + 1;
- for (; h >= 1; h /= 3) {
- for (int i = 0; i < a.length - h; i += h) {
- for (int j = i + h; j > 0; j -= h) {
- if (a[j] < a[j - h]) {
- int temp = a[j];
- a[j] = a[j - h];
- a[j - h] = temp;
- }
- }
- }
- }
- }
選擇排序
選擇排序(Selection sort)是一種簡單直觀的排序算法。
這個就比較簡單了，為什么這么說，是因為他就是直接從未排序的序列中去找最小或者最大的元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小(大)元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
實際上和冒泡排序在想法上有一丟丟的相似，但是就是不一樣。
我們看看代碼是否實現：
- public static void sort(int[] a) {
- for (int i = 0; i < a.length; i++) {
- int min = i;
- //選出之后待排序中值最小的位置
- for (int j = i + 1; j < a.length; j++) {
- if (a[j] < a[min]) {
- min = j;
- }
- }
- //最小值不等于當前值時進行交換
- if (min != i) {
- int temp = a[i];
- a[i] = a[min];
- a[min] = temp;
- }
- }
- }
既然阿粉都給大家列出了這幾種排序，那么我們又回到一個問題上來了，排序這么多，怎么選擇，為什么選擇，這就又涉及到了時間復雜度和空間復雜度上面了，要么用空間換時間，要么用時間換空間。
總結
冒泡排序
平均時間復雜度 最好情況 最壞情況 空間復雜度 O(n²) O(n) O(n²) O(1)
直接插入排序
平均時間復雜度 最好情況 最壞情況 空間復雜度 O(n²) O(n²) O(n²) O(1)
二分查找排序
平均時間復雜度 最好情況 最壞情況 空間復雜度 O(n²) O(n²) O(n²) O(1)
希爾排序
平均時間復雜度 最好情況 最壞情況 空間復雜度 O(nlog2 n) O(nlog2 n) O(nlog2 n) O(1)
選擇排序
平均時間復雜度 最好情況 最壞情況 空間復雜度 O(n²) O(n²) O(n²) O(1)
今天的排序就說到這里了，你學會了么?
