[[440899]]

今天阿粉就來(lái)談一下這個(gè) Java 中的各種排序的算法，因?yàn)橹坝龅搅艘粋€(gè)面試高級(jí)開(kāi)發(fā)，結(jié)果竟然出了一個(gè) 九九乘法表的題，阿粉當(dāng)時(shí)聽(tīng)完讀者說(shuō)的，瞬間就明白是什么意思了，這感覺(jué)有點(diǎn)忽悠人，但是實(shí)際上卻是面試官想要考察你的排序算法的事了，也有可能是真的無(wú)聊。

排序算法

什么是排序算法，實(shí)際上這個(gè)沒(méi)有太多的說(shuō)法，意思表達(dá)清楚就可以了，所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減地排列起來(lái)的操作。

排序算法的種類(lèi)可以說(shuō)是比較的多樣化了，對(duì)時(shí)間，對(duì)空間的效率，不同的排序算法的優(yōu)缺點(diǎn)是不一樣的，有些是用時(shí)間換空間的，有些是拿空間換時(shí)間的，今天阿粉就來(lái)一一列舉一下。

冒泡排序

什么是冒泡排序呢?

冒泡排序就是依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。

就像一個(gè)泡泡，一個(gè)泡泡一樣，直接往起漂。

冒泡排序就是依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。

實(shí)際上比較的過(guò)程就是這個(gè)樣子的：

第一次比較：

首先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放前面，大數(shù)放后面，然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，小數(shù)放前面，大數(shù)放后面，然后一直比較到最后，這樣，最大的一個(gè)數(shù)就放到了最后面了。

第二次比較：

首先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放前面，大數(shù)放后面，然后比較到倒數(shù)第二個(gè)數(shù)，然后第二次比較結(jié)束，這樣在最后一個(gè)位置的就是最大的，然后倒數(shù)第二個(gè)位置的是第二大的數(shù)。

然后一直這樣往下執(zhí)行，第三次就是來(lái)取第三個(gè)數(shù)，這樣依次循環(huán)，這樣說(shuō)大家肯定都是能理解的，假設(shè)需要排序的序列的個(gè)數(shù)是n，則需要經(jīng)過(guò)n-1輪，最終完成排序。在第一輪中，比較的次數(shù)是n-1次，之后每輪減少1次。

我們接下來(lái)使用代碼來(lái)實(shí)現(xiàn)一下：

public static void main(int[] a) { 
        int temp; 
        //需要比較n-1輪 
        for (int i = 0; i < a.length-1; i++) { 
            //根據(jù)a.length-i-1，每輪需要比較的次數(shù)逐輪減少1次 
            for (int j = 0; j < a.length-i-1 ; j++) { 
                //相鄰數(shù)進(jìn)行比較，符合條件進(jìn)行替換 
                if (a[j] > a[j+1]) { 
                    temp = a[j]; 
                    a[j] = a[j+1]; 
                    a[j+1] = temp; 
                } 
            } 
        } 
    } 
     

插入排序

插入排序種類(lèi)比較多

• 直接插入排序
• 二分插入排序
• 希爾排序

這些排序方式全都是屬于插入排序的，

我們先來(lái)看看直接插入排序：

比較的過(guò)程是這個(gè)樣子的，數(shù)組的第二個(gè)數(shù)據(jù)開(kāi)始往前比較，即一開(kāi)始用第二個(gè)數(shù)和他前面的一個(gè)比較，如果 符合條件則讓他們交換位置。

假如我們給定一個(gè)數(shù)組，我們要按照從小到大排序，數(shù)組為 [3,1,4,6,5,17,12,11] 這時(shí)候，第一步就是拿著 1 和 3 進(jìn)行比較，如果 1 小于 3 ，這個(gè)時(shí)候，就把 1 和 3 換個(gè)位置，[1,3,4,6,5,17,12,11] .

接下來(lái)再用第三個(gè)數(shù)和第二個(gè)比較，符合則交換，但是此處還得繼續(xù)往前比較 ，就是用 4 和 3 和 1 分別去比較，然后一直這么重復(fù)下去。直到把所有的數(shù)據(jù)都排列完之后，就得到了我們想要的結(jié)果，我們來(lái)寫(xiě)個(gè)代碼看看是什么樣子的。

public static void basal(int[] array) { 
 // 從第二項(xiàng)開(kāi)始 
    if (array == null || array.length < 2) { 
            return; 
        } 
        for (int i = 1; i < array.length; i++) { 
            int cur = array[i]; 
            // cur 落地標(biāo)識(shí)，防止待插入的數(shù)最小 
            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; 
            } 
        } 
    } 
} 

既然我們之前都說(shuō)了，插入排序的方法有很多種，那么我們也得說(shuō)說(shuō)其他的插入排序，然后在看看他們都有什么不同的地方，大家說(shuō)對(duì)不對(duì)呢?

既然我們剛才都說(shuō)了排序每次都要講數(shù)組后移，但是我們之前的判斷條件上卻是可以?xún)?yōu)化出來(lái)的，這樣優(yōu)化優(yōu)化的就衍生出來(lái)了其他的不同的插入排序，接下來(lái)我們就來(lái)看看這個(gè)二分查找插入排序。

二分查找法插入排序

優(yōu)化直接插入排序的核心在于：快速定位當(dāng)前數(shù)字待插入的位置。在一個(gè)有序數(shù)組中查找一個(gè)給定的值，最快的方法無(wú)疑是二分查找法，至少在阿粉的心中如果想到優(yōu)化的時(shí)候肯定是第一時(shí)間選擇的就是可不可以使用二分查找法呢?

我們先來(lái)看看代碼實(shí)現(xiàn)，然后再看看他有什么缺點(diǎn)，為啥有很多人都不選擇使用二分查找插入排序。

// 利用系統(tǒng)自帶的二分查找法，定位插入位置 
   // 不穩(wěn)定排序 
  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; 
      } 
 } 

在這其中，阿粉使用了系統(tǒng)自帶的Arrays，然后進(jìn)行了二分查找插入排序，為什么這么用呢?在JDK中提供了 Arrays.binarySearch()，方法的入?yún)⑿枰獙⒂行驍?shù)組傳遞進(jìn)去 來(lái)進(jìn)行實(shí)現(xiàn)，為什么不用這種方法呢?

假如在排序之前，有兩個(gè)數(shù)相等，但是在排序結(jié)束之后，它們兩個(gè)有可能改變順序這就是說(shuō)明該排序算法具有不穩(wěn)定性。這就是大家所說(shuō)的穩(wěn)定性。

既然都有這種不穩(wěn)定的排序，那是不是就應(yīng)該存在穩(wěn)定的排序呢?對(duì)沒(méi)錯(cuò)，就是有，那么什么是穩(wěn)定的排序呢?對(duì)，大家沒(méi)有想錯(cuò)，冒泡排序就是穩(wěn)定排序，因?yàn)槊芭菖判蛑辉谙噜徳卮笮〔环弦髸r(shí)才調(diào)換他們的位置,它并不改變相同元素之間的相對(duì)順序, 因此它是穩(wěn)定的排序算法。

既然我們剛才說(shuō)了這個(gè)插排序中還有希爾排序，我們?cè)賮?lái)看看希爾排序。

希爾排序

說(shuō)實(shí)話(huà)，阿粉第一次知道這個(gè)排序的時(shí)候，就想說(shuō)，是不是一個(gè)叫做希爾的人改進(jìn)的，結(jié)果，發(fā)現(xiàn)還真是，希爾排序，又叫做((縮小增量排序)，因 D.L.Shell 于 1959 年提出而得名，實(shí)際上應(yīng)該叫做Shell's Sort。

希爾排序是先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。

實(shí)際上就相當(dāng)于先進(jìn)行了一個(gè)簡(jiǎn)單的分組，將待排序數(shù)組按照步長(zhǎng)gap進(jìn)行分組，然后將每組的元素利用直接插入排序的方法進(jìn)行排序;每次再將gap折半減小，循環(huán)上述操作;當(dāng)gap=1時(shí)，利用直接插入，完成排序。

代碼實(shí)現(xiàn)是這個(gè)樣子的。

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)是一種簡(jiǎn)單直觀(guān)的排序算法。

這個(gè)就比較簡(jiǎn)單了，為什么這么說(shuō)，是因?yàn)樗褪侵苯訌奈磁判虻男蛄兄腥フ易钚』蛘咦畲蟮脑?，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小(大)元素，然后放到已排序序列的末尾。以此類(lèi)推，直到所有元素均排序完畢。

實(shí)際上和冒泡排序在想法上有一丟丟的相似，但是就是不一樣。

我們看看代碼實(shí)現(xiàn)：

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; 
            } 
        } 
        //最小值不等于當(dāng)前值時(shí)進(jìn)行交換 
        if (min != i) { 
            int temp = a[i]; 
            a[i] = a[min]; 
            a[min] = temp; 
        } 
    } 
} 

既然阿粉都給大家列出了這幾種排序，那么我們又回到一個(gè)問(wèn)題上來(lái)了，排序這么多，怎么選擇，為什么選擇，這就又涉及到了時(shí)間復(fù)雜度和空間復(fù)雜度上面了，要么用空間換時(shí)間，要么用時(shí)間換空間。

總結(jié)

冒泡排序

直接插入排序

二分查找排序

希爾排序

選擇排序 

今天的排序就說(shuō)到這里了，你學(xué)會(huì)了么?