一. 直接插入排序

1. 概念

直接插入排序(Insertion Sort) ，顧名思義就是把未排序的元素一個一個地插入到有序的集合中，插入時把有序集合從后向前掃一遍，找到合適的插入位置。 為了讓大家更好地理解插入排序，小編通過一個簡單的例子給大家解釋一下插入排序的含義，我們以日常生活中的紙牌游戲為例：

一開始，上述紙牌是亂序狀態(tài)的，我們想辦法對上述紙牌進行排序操作。

(1). 第一次，將第一張牌8看做是已經(jīng)排好序的牌，右邊的5、3、9都是未排好序的。

(2). 第二次，將5插入到排好序的隊伍中，5比8小，放到8的前面。

(3). 第三次，將3也插入到排好序的隊伍中，3比5和8都小，所以放到5的前面。

(4). 第4次，將9也插入到排好序的隊伍中，9比其他牌都大，所以放在最后。

經(jīng)過以上幾個步驟，這樣所有的牌都排好序了。

2. 實現(xiàn)原理

插入排序的實現(xiàn)原理，其實就是將數(shù)列分成有序區(qū)間和無序區(qū)間兩個部分。初始時，有序區(qū)間中只有一個元素，即數(shù)列的第一個元素。然后從無序區(qū)間取出一個元素，插入到有序區(qū)間的末尾，新插入的元素要與有序區(qū)間的數(shù)據(jù)一一比較大小。如果該數(shù)據(jù)大于有序區(qū)間的最后一個數(shù)據(jù)，則不交換位置，直接插入到有序區(qū)間的末尾即可。如果該數(shù)據(jù)小于有序區(qū)間的最后一個數(shù)據(jù)，則需要換位，換位后該數(shù)據(jù)還要與前一位數(shù)據(jù)繼續(xù)比較大小，直到找到合適的位置才停止比較。

3. 實現(xiàn)步驟

根據(jù)上面的實現(xiàn)原理，壹哥再給大家梳理一下插入排序的實現(xiàn)步驟：

(1). 第1步：從數(shù)列的第2個元素開始抽取元素；

(2). 第2步：把它與左邊的第一個元素進行比較，如果左邊的第一個元素比它大，則繼續(xù)與左邊第二個元素比較下去，直到遇到小于等于它的元素，然后插到這個元素的右邊。

(3). 第3步：繼續(xù)選取第3、4....n個元素，重復步驟2，并選擇適當?shù)奈恢貌迦搿?/p>

現(xiàn)在，我們可以通過一個實際的例子演示插入排序的過程。例如有一個待排序數(shù)組[5，8，6，3，9，2，1，7]，插入排序步驟如下：

(1). 初始時，有序區(qū)間中只有5，無序區(qū)間中有8、6、3、9、2、1、7。

(2). 將無序區(qū)間的第一個元素8插入到有序區(qū)間的數(shù)列末尾，8和5比較大小，8比5大則無需交換位置。此時有序區(qū)間中的元素是5、8，無序區(qū)間中有6、3、9、2、1、7。

(3). 將無序區(qū)間的第一個元素6插入到有序區(qū)間的末尾，形成5、8、6的排列順序。6和左側(cè)的8比較大小，6比8小則換位；6再與5比較，6比5大則無需換位。最后有序區(qū)間中形成了5、6、8的排列。此時，無序區(qū)間中還有3、9、2、1、7。

(4). 將無序區(qū)間的第一個元素3插入到有序區(qū)間的末尾，形成5、6、8、3的排列順序。3和左側(cè)的8比較大小，3比8小則換位；3再與6比較大小，3比6小則繼續(xù)換位；3與5比較大小，3比5小繼續(xù)換位。最后形成3、5、6、8的排列，此時，有序區(qū)間中是3、5、6、8，無序區(qū)間中還有9、2、1、7。

(5). 然后依次類推，直到無序區(qū)間為空時，排序結(jié)束。最終排序的結(jié)果為：1、2、3、5、6、7、8、9。

4. 編程實現(xiàn)

接下來我們使用Java語言，對插入排序算法進行編程實現(xiàn)：

public static void insertionSort(int[] arr) {
    int loop = 0;
    int count = 0;
    //對數(shù)組進行遍歷
    for (int i = 0; i < arr.length; i++) {
        //第二個循環(huán)僅僅是將當前數(shù)據(jù)跟自己左邊的數(shù)字進行比較，如果小于左邊數(shù)字則交換位置，否則位置不變。
        for (int j = i; j > 0; j--) {
            count++;
            //此處使用break比使用if效率高，兩者在比較次數(shù)上有差別。
            if (arr[j] >= arr[j - 1]) break;
            // 前后兩個數(shù)據(jù)交換位置
            arr[j] = arr[j] + arr[j - 1] - (arr[j - 1] = arr[j]);
        }
    }
}

5. 總結(jié)

接下來我們把插入排序的特性總結(jié)一下。

5.1 時間復雜度

根據(jù)給定的數(shù)列的混亂程度，時間復雜度可做如下分析：

(1). 當數(shù)列本身是有序的，插入排序的時間復雜度是O(n)。原因是如果數(shù)列本身是有序，插入排序需要將每相鄰的兩個數(shù)字各比較一次，總共比較n-1次， 所以時間復雜度是O(n)。

(2). 當數(shù)列是無序的，最壞的情況下需要比較n(n-1)/2次，所以時間復雜度是O(n²)。

5.2 空間復雜度

(1). 插入排序是原地排序，其空間復雜度是O(1)。

(2). 插入排序中，無序區(qū)間的元素在插入到有序區(qū)間的過程中，是依次與左側(cè)的元素比較，如果兩個元素相等，則不交換位置。

5.3 插入排序的適用場景

(1). 一個有序的大數(shù)組中融入一個小數(shù)組，比如有序大數(shù)組[1, 2, 3, 4, 5, 6, 7, 8, 9}中融入一個小數(shù)組[0, 1]。

(2). 數(shù)組中只有幾個元素的順序不正確，或者說數(shù)組部分有序。

總結(jié)來說，插入排序是一種比較簡單直觀的排序算法，適用于處理數(shù)據(jù)量比較小或者部分有序的數(shù)列。

二. 快速排序

1. 概念

快速排序(Quick Sort) ，其是對冒泡排序的一種改進，該算法由霍爾(Hoare)在1962年提出。與冒泡排序一樣，快速排序也屬于交換排序算法，通過元素之間的比較和交換位置來達到排序的目的。

快速排序每次排序的時候設置一個基準點，將小于基準點的數(shù)全部放到基準點的左邊，將大于等于基準點的數(shù)全部放到基準點的右邊。這樣每次交換的時候就不會像冒泡排序一樣只能在相鄰的兩個數(shù)之間進行交換，交換的距離就得到提升?？焖倥判蛑容^快，因為相比冒泡排序，每次交換是跳躍式的。這樣總的比較和交換次數(shù)就少了，排序效率自然就提高了。

通過一趟排序，將要排序的數(shù)據(jù)分割成兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。快速排序算法的實現(xiàn)思路就是分治思想的應用。

2. 實現(xiàn)思路

快速排序基于遞歸的方式來實現(xiàn)，其實現(xiàn)思路如下：

(1). 選定一個合適的值(理想情況是選擇數(shù)列的中值最好，但為了實現(xiàn)方便一般都是選擇數(shù)列的第一個值)，稱為“基準元素”(pivot)。

(2). 基于基準元素，將數(shù)列分為兩部分，較小的分在左邊，較大的分在右邊。

(3). 第一輪下來，這個基準元素的位置一定在最終位置上。

(4). 對左右兩個子數(shù)列分別重復上述過程，直到每個子數(shù)列中只包含一個元素則排序完成。快速排序的核心思想就是在給基準元素找正確的位置。

3. 實現(xiàn)步驟

接下來壹哥通過一個示例來講解快速排序的步驟。假設現(xiàn)在有一個亂序數(shù)組[5，8，6，3，9，2，1，7]，我們使用快速排序算法進行排序。首選要選擇一個元素作為基準元素，在此例中，我們可以選擇首元素5作為基準元素。接下來進行元素的交換，具體步驟如下：

(1). 選定基準元素5，同時設置兩個指針分別為left和right，分別指向最左側(cè)元素5、最右側(cè)元素7。移動和比較的規(guī)則是：

• 從right指針的位置開始，讓指針指向的元素和基準元素做比較。right指針指向的數(shù)據(jù)如果小于基準元素，則right指針停止移動；切換至left指針，否則right指針繼續(xù)向左移動。
• 輪到left指針移動時，讓left指針指向的元素與基準元素做比較。將left指針指向的數(shù)據(jù)和基準元素做比較。left指向的元素數(shù)據(jù)如果大于基準元素，則left指針停止移動，否則left指針繼續(xù)向右移動。
• 將left和right指針指向的元素交換位置。

(2). right指針先開始，right指針當前指向的數(shù)據(jù)是7，由于7>5，right指針繼續(xù)左移，指向到1，由于1<5，停止在1的位置。

• 輪到left指針。由于left開始指向的是基準元素5，所以left右移1位，指向到8。由于8>5，所以left指針停下
• 接下來，left和right指向的元素進行交換。此時形成數(shù)列為[5, 1, 6, 3, 9, 2, 8, 7]

(3). 重新切換到right指針，指針向左移動，right指針指向到2。由于2<5，right指針停止在2的位置。

• 輪到left指針，指針右移1位，指向到6，由于6>5，所以left指針停下。
• 接下來，left和right所指向的元素進行交換。此時形成數(shù)列為[5, 1, 2, 3, 9, 6, 8, 7]。

(4). 重新切換到right指針，指針向左移動。right指針指向到9，由于9>5，right指針繼續(xù)左移，指向到3，由于3<5，則right指針停止在3的位置。

• 輪到left指針，指針右移1位，指向到3，此時right指針和left指針重疊在一起。
• 接下來，將pivot元素5與重疊點的元素3進行交換，此時形成數(shù)列為[3, 1, 2, 5, 9, 6, 8, 7]。第一輪排序結(jié)束。

我們把上述的文字描述過程，做成對應的示意圖，如下所示：

第一輪排序結(jié)束后，本輪的基準元素5的位置，就是最終排序后所在的位置。接下來，我們采用遞歸的方式，分別對基準元素5左側(cè)的前半部分[3, 1, 2]進行排序，再對元素5右側(cè)的后半部分[9, 6, 8, 7]進行排序，如下圖所示：

(1). 基準元素5的前半部分[3, 1, 2]，以3為基準元素，經(jīng)過排序，結(jié)果為[2, 1, 3]。本輪下來，本輪的基準元素3的位置就是其最終位置。

(2). 上輪基準元素3左側(cè)的隊列[2, 1]，以2為基準元素排序，排序結(jié)果為[1, 2]。本輪下來，本輪的基準元素2的位置就是其最終位置。

(3). 上輪基準元素2左側(cè)只剩下元素1，1就是自己的基準元素。這樣元素1的最終位置就確定了。

(4). 基準元素5的后半部分[9, 6, 8, 7]，以9為基準元素進行排序，結(jié)果為：[7, 6, 8, 9]，本輪下來，本輪的基準元素9的位置就是其最終位置。

(5). 上輪基準元素9左側(cè)的隊列[7, 6, 8]，以7為基準元素進行排序，結(jié)果為[6, 7, 8]。本輪下來，本輪的基準元素7的位置就是其最終位置。

(6). 上輪基準元素7左側(cè)只剩下6，6就是自己的基準元素。這樣元素6的最終位置就確定了。

(7). 基準元素7右側(cè)只剩下8，8就是自己的基準元素。這樣元素8的最終位置就確定了。

(8). 此時基準元素5、3、2、1、9、7、6、8都找到其正確的位置，則排序結(jié)束。

4. 編碼實現(xiàn)

接下來我們使用Java語言對快速排序算法進行代碼實現(xiàn)：

public static void quickSort(int[] arr, int start, int end) {
    // 遞歸結(jié)束條件:start大于或等于end時
    if (start < end) {
        // 得到基準元素位置
        int pivotIndex = partition(arr, start, end);
        // 根據(jù)基準元素，分成兩部分進行遞歸排序
        quickSort(arr, start, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, end);
    }
}
private static int partition(int[] arr, int start, int end) {
    // 取第1個位置的元素作為基準元素
    int pivot = arr[start];
    int left = start;
    int right = end;
    while (left < right) {
        //right指針左移
        while (left < right && arr[right] >= pivot) right--;
        //left指針右移
        while (left < right && arr[left] <= pivot) left++;
        if (left >= right) break;
        //交換left和right 指針所指向的元素
        arr[left] = arr[left] + arr[right] - (arr[right] = arr[left]);
    }
    // 將基準元素與指針重合點所指的元素進行交換
    arr[start] = arr[left];
    arr[left] = pivot;    
    return left;
}

這里使用了兩個方法quickSort和partition實現(xiàn)快速排序算法的邏輯，其核心思路與前文描述一致，先找到一個元素作為基準元素，然后再分開進行排序。

三. 希爾排序

1. 概念

希爾排序(Shell’s Sort) ，該算法是插入排序的一種，又稱“縮小增量排序”(Diminishing Increment Sort) ，希爾排序是Shell在1959年提出的。希爾排序是基于直接插入排序進行改進而形成的排序算法。它是直接插入排序算法的一種更高效的改進版本。直接插入排序本身還不夠高效，插入排序每次只能將數(shù)據(jù)移動一位。當有大量數(shù)據(jù)需要排序時，會需要大量的移位操作。但是插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率很高，幾乎可以達到線性排序的效率。所以，如果能對數(shù)據(jù)進行初步排列達到基本排序，然后再用插入排序就會大大提高排序效率。希爾排序正是基于此思路而形成的。

2. 實現(xiàn)步驟

希爾排序的步驟簡述如下：

(1). 把元素按步長gap分組，gap的數(shù)值其實就是分組的個數(shù)。gap的起始值為數(shù)列長度的一半，每循環(huán)一輪gap減為原來的一半。

(2). 對每組元素采用直接插入排序算法進行排序。

(3). 隨著步長逐漸減小，組就越少，組中包含的元素就越多。

(4). 當步長值減小到1時，整個數(shù)據(jù)合成一組，最后再對這一組數(shù)列用直接插入排序進行最后的調(diào)整，最終完成排序。

我們以無序數(shù)列[5，8，6，3，9，2，1，7，,4]為例，詳細介紹希爾排序的步驟：

(1). 第一輪排序，gap = length/2 = 4，即將數(shù)組分成4組。四組元素分別為[5，9，4]、[8，2]、[6，1]、[3，,7]。對四組元素分別進行排序結(jié)果為：[4，5，9]、[2，8]、[1，6]、[3，7]。將四組排序結(jié)果進行合并，得到第一輪的排序結(jié)果為：[4，2，1，3，5，8，6，7，9]。如下圖所示。

(2). 第二輪排序，gap = 2，將數(shù)列分成2組。兩組的元素分別是[4，1，5，6，9]和[2，3，8，,7]。這兩個組分別執(zhí)行直接插入排序后的結(jié)果為[1，4，5，6，9]和[2，3，7，8]。將兩組合并后的結(jié)果為[1，2，4，3，5，7，6，8，9]，如下圖所示。

(3). 第三輪排序，gap = 1，數(shù)組就變成了一組。 該組的元素是[1，2，4，3，5，7，6，8，9]，這個組執(zhí)行直接插入排序后結(jié)果為[1，2，3，4，5，6，7，8，9]，這個結(jié)果就是第三輪排序后得到的結(jié)果。此時排序完成，如下圖所示。

3. 編碼實現(xiàn)

接下來我們用代碼對希爾排序進行編程實現(xiàn)：

public static void shellSort(int[] arr) {
    int loop = 0;
    //增量gap，并逐步縮小增量
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        //對一個步長區(qū)間進行比較 [gap,arr.length)
        for (int i = gap; i < arr.length; i++) {
            //對步長區(qū)間中具體的元素進行比較
            for (int j = i - gap; j >= 0; j -= gap) {
                //System.out.println("j=" + j);
                if (arr[j] <= arr[j + gap]) break;
                //換位
                arr[j] = arr[j] + arr[j + gap] - (arr[j + gap] = arr[j]);
            }
        }
    }
}

4. 總結(jié)

接下來我們再把希爾排序的復雜度等情況進行分析總結(jié)，如下：

(1). 希爾排序的時間復雜度與增量(即步長gap)的選取有關(guān)。例如，當增量為1時，希爾排序退化成了直接插入排序，此時最壞情況時間復雜度為O(n²)。而具有增量的希爾排序的平均時間復雜度為O(n^1.3)，希爾排序最好情況時間復雜度是O(n)。

(2). 希爾排序的空間復雜度是O(1)。

(3). 直接插入排序是穩(wěn)定的，不會改變相同元素的相對順序。 但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂。也就是說，對于相同的兩個數(shù)，可能分在不同的組中而導致它們的順序發(fā)生變化，所以希爾排序是不穩(wěn)定的。

四. 結(jié)語

至此，我們我們已經(jīng)向大家介紹了冒泡排序、選擇排序、插入排序、快速排序、希爾排序等五種經(jīng)典的排序算法。除此以外，還有堆排序、歸并排序、桶排序、計數(shù)排序等一些經(jīng)典的排序算法。大家會發(fā)現(xiàn)，我們介紹排序算法的步驟和過程都是相同的，基本都包含算法概念、思想和原理、算法步驟，以及編碼實現(xiàn)等幾個部分。在本篇的最后，我們給大家總結(jié)出經(jīng)典的排序算法的對比和總結(jié)，我們從時間復雜度、空間復雜度、穩(wěn)定性等幾個方面進行橫向總結(jié)。

以上就是Java排序算法之直接插入、快排和希爾排序詳解的詳細內(nèi)容，更多關(guān)于Java直接插入、快排和希爾排序的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論