一. 直接插入排序

1. 概念

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

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

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

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

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

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

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

2. 實(shí)現(xiàn)原理

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

3. 實(shí)現(xiàn)步驟

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

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

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

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

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

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

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

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

(4). 將無序區(qū)間的第一個(gè)元素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的排列，此時(shí)，有序區(qū)間中是3、5、6、8，無序區(qū)間中還有9、2、1、7。

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

4. 編程實(shí)現(xiàn)

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

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

5. 總結(jié)

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

5.1 時(shí)間復(fù)雜度

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

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

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

5.2 空間復(fù)雜度

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

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

5.3 插入排序的適用場(chǎng)景

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

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

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

二. 快速排序

1. 概念

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

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

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

2. 實(shí)現(xiàn)思路

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

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

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

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

(4). 對(duì)左右兩個(gè)子數(shù)列分別重復(fù)上述過程，直到每個(gè)子數(shù)列中只包含一個(gè)元素則排序完成?？焖倥判虻暮诵乃枷刖褪窃诮o基準(zhǔn)元素找正確的位置。

3. 實(shí)現(xiàn)步驟

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

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

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

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

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

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

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

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

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

我們把上述的文字描述過程，做成對(duì)應(yīng)的示意圖，如下所示：

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

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

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

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

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

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

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

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

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

4. 編碼實(shí)現(xiàn)

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

public static void quickSort(int[] arr, int start, int end) {
    // 遞歸結(jié)束條件:start大于或等于end時(shí)
    if (start < end) {
        // 得到基準(zhǔn)元素位置
        int pivotIndex = partition(arr, start, end);
        // 根據(jù)基準(zhǔn)元素，分成兩部分進(jìn)行遞歸排序
        quickSort(arr, start, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, end);
    }
}
private static int partition(int[] arr, int start, int end) {
    // 取第1個(gè)位置的元素作為基準(zhǔn)元素
    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 指針?biāo)赶虻脑?
        arr[left] = arr[left] + arr[right] - (arr[right] = arr[left]);
    }
    // 將基準(zhǔn)元素與指針重合點(diǎn)所指的元素進(jìn)行交換
    arr[start] = arr[left];
    arr[left] = pivot;    
    return left;
}

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

三. 希爾排序

1. 概念

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

2. 實(shí)現(xiàn)步驟

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

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

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

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

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

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

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

(2). 第二輪排序，gap = 2，將數(shù)列分成2組。兩組的元素分別是[4，1，5，6，9]和[2，3，8，,7]。這兩個(gè)組分別執(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]，這個(gè)組執(zhí)行直接插入排序后結(jié)果為[1，2，3，4，5，6，7，8，9]，這個(gè)結(jié)果就是第三輪排序后得到的結(jié)果。此時(shí)排序完成，如下圖所示。

3. 編碼實(shí)現(xiàn)

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

public static void shellSort(int[] arr) {
    int loop = 0;
    //增量gap，并逐步縮小增量
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        //對(duì)一個(gè)步長區(qū)間進(jìn)行比較 [gap,arr.length)
        for (int i = gap; i < arr.length; i++) {
            //對(duì)步長區(qū)間中具體的元素進(jìn)行比較
            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é)

接下來我們?cè)侔严柵判虻膹?fù)雜度等情況進(jìn)行分析總結(jié)，如下：

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

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

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

四. 結(jié)語

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

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

最新評(píng)論