一：排序的概念及引入

1.1 排序的概念

• 排序：所謂排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。

• 穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

• 內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。
• 外部排序：數(shù)據(jù)元素太多不能同時放在內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序。

1.2常見的排序算法

常見的排序算法有七種，分別是直接插入排序，希爾排序，選擇排序，堆排序，冒泡排序，快速排序，歸并排序

下面我們對這些排序進(jìn)行一 一講解。

二：插入排序

2.1 直接插入排序

直接插入排序是一種簡單的插入排序法，其基本思想是：

把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。實際中我們玩撲克牌時，就用了插入排序的思想。

插入排序是一種簡單直觀的排序算法。它的原理是將待排序的元素逐個插入到已排序序列的適當(dāng)位置，從而形成一個有序序列。

該算法的工作原理如下：

1. 從第二個元素開始，將其與前面已排序的元素逐個比較，找到合適的位置插入。
2. 將當(dāng)前元素與前面已排序的元素進(jìn)行比較，如果當(dāng)前元素小于前面的元素，則將前面的元素后移一位，直到找到合適的位置。
3. 插入當(dāng)前元素到合適的位置后，繼續(xù)比較并插入下一個元素。
4. 重復(fù)上述步驟，直到所有元素都被插入到合適的位置。

動圖如下：

下面是一個使用Java實現(xiàn)插入排序的示例代碼：

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i]; // 當(dāng)前要插入的元素
            int j = i - 1; // 已經(jīng)排好序的元素的最后一個索引

            // 將比 key 大的元素向后移動
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j]; // 向后移動元素
                j--; // 向前遍歷已經(jīng)排好序的元素
            }

            // 插入 key 到合適的位置
            arr[j + 1] = key; // 將 key 插入到正確的位置
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 9, 1, 3};
        insertionSort(arr); // 使用插入排序算法對數(shù)組進(jìn)行排序

        System.out.println("排序后的數(shù)組：");
        for (int num : arr) {
            System.out.print(num + " "); // 輸出排序后的數(shù)組
        }
    }
}

直接插入排序的特性總結(jié)：

1. 元素集合越接近有序，直接插入排序算法的時間效率越高
2. 時間復(fù)雜度：O(N^2)
3. 空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法
4. 穩(wěn)定性：穩(wěn)定

2.2 希爾排序( 縮小增量排序 )

希爾排序法又稱縮小增量法。

希爾排序法的基本思想是：先選定一個整數(shù)，把待排序文件中所有記錄分成多個組，所有距離為的記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進(jìn)行排序。然后重復(fù)上述分組和排序的工作。當(dāng)?shù)竭_(dá)=1時，所有記錄在統(tǒng)一組內(nèi)排好序。

下面是希爾排序的工作原理：

1. 選擇一個增量序列，增量序列由一系列整數(shù)構(gòu)成，通常是遞減的，最后一個增量必須為1。
2. 根據(jù)選定的增量序列，將待排序的數(shù)組分割成若干個子數(shù)組，每個子數(shù)組包含相同間隔的元素。
3. 將每個子數(shù)組的元素依次與該子數(shù)組中的其他元素進(jìn)行比較和交換，使得子數(shù)組中的元素逐漸有序。
4. 重復(fù)以上步驟，縮小增量，直至增量為1。
5. 最后進(jìn)行一次完整的插入排序，以保證數(shù)組的最終有序性。

示圖如下：

動圖如下：

希爾排序的特性總結(jié)：

1. 希爾排序是對直接插入排序的優(yōu)化。
2. 當(dāng)gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。
3. 希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導(dǎo)致很難去計算，因此在好些樹中給出的希爾排序的時間復(fù)雜度都不固定

因為咋們的gap是按照Knuth提出的方式取值的，而且Knuth進(jìn)行了大量的試驗統(tǒng)計，我們暫時就按照：O（n^1.25）到O（1.6 * n^1.25） 來算。

下面是一個使用Java實現(xiàn)的希爾排序示例代碼：

public class ShellSort {
    public static void shellSort(int[] arr) {
        int n = arr.length;
        
        // 初始化增量為數(shù)組長度的一半
        int gap = n / 2;
        
        while (gap > 0) {
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;
                
                // 插入排序
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                
                arr[j] = temp;
            }
            
            // 縮小增量
            gap /= 2;
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {9, 5, 2, 7, 1, 3, 6, 8, 4};
        
        System.out.println("原始數(shù)組：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
        
        shellSort(arr);
        
        System.out.println("排序后的數(shù)組：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

希爾排序穩(wěn)定性：不穩(wěn)定

三：選擇排序

3.1直接選擇排序

當(dāng)我們需要對一個數(shù)組進(jìn)行排序時，選擇排序是一種簡單而直觀的算法。

它的工作原理是選擇數(shù)組中最小的元素，將它與數(shù)組的第一個元素交換位置。然后，選擇剩余元素中最小的元素，將它與數(shù)組的第二個元素交換位置。以此類推，直到整個數(shù)組排序完成

動圖如下：

public class SelectionSort {
    public static void main(String[] args) {
        // 創(chuàng)建一個整數(shù)數(shù)組
        int[] arr = {64, 25, 12, 22, 11};
        
        // 調(diào)用選擇排序方法
        selectionSort(arr);
        
        // 輸出排序后的數(shù)組
        System.out.println("排序后的數(shù)組：");
        for(int i=0; i < arr.length; i++){
            System.out.print(arr[i] + " ");
        }
    }

    public static void selectionSort(int[] arr) {
        // 獲取數(shù)組長度
        int n = arr.length;
        
        // 遍歷整個數(shù)組
        for (int i = 0; i < n-1; i++) {
            // 假設(shè)當(dāng)前索引為 i 的元素是最小值
            int minIndex = i;
            
            // 在剩余的元素中尋找最小值的索引
            for (int j = i+1; j < n; j++) {
                // 如果找到比當(dāng)前最小值還小的值，則更新最小值的索引
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            
            // 將最小值與當(dāng)前位置交換
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

【直接選擇排序的特性總結(jié)】

1. 直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用
2. 時間復(fù)雜度：O(N^2)
3. 空間復(fù)雜度：O(1)
4. 穩(wěn)定性：不穩(wěn)定

3.2堆排序

堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法，它是選擇排序的一種。它是通過堆來進(jìn)行選擇數(shù)據(jù)。需要注意的是排升序要建大堆，排降序建小堆。

堆排序具體的講解可以查看這篇文章

【堆排序的特性總結(jié)】

1. 堆排序使用堆來選數(shù)，效率就高了很多。
2. 時間復(fù)雜度：O(N*logN)
3. 空間復(fù)雜度：O(1)
4. 穩(wěn)定性：不穩(wěn)定

四：交換排序

4.1冒泡排序

冒泡排序是一種簡單但效率較低的排序算法。

它的基本思想是通過不斷比較相鄰的兩個元素并交換位置，從而將較大（或較小）的元素逐漸“冒泡”到數(shù)組的頂部（或底部）。這個過程會不斷重復(fù)，直到數(shù)組中的所有元素都按照順序排列。

下面是一個詳細(xì)注釋的 Java 示例代碼：

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;

        // 外層循環(huán)控制比較的輪數(shù)，每輪比較后，最大的元素就會被冒泡到數(shù)組末尾
        for (int i = 0; i < n - 1; i++) {
            // 內(nèi)層循環(huán)用于比較相鄰的元素并交換位置
            // 每輪結(jié)束后，當(dāng)前輪數(shù)已經(jīng)排序完成的元素就會排在數(shù)組的最后
            // 所以下一輪比較時，不需要再考慮這些元素
            for (int j = 0; j < n - 1 - i; j++) {
                // 如果當(dāng)前元素比下一個元素大，就交換它們的位置
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};

        System.out.println("原始數(shù)組：");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        // 調(diào)用冒泡排序
        bubbleSort(arr);

        System.out.println("\n排序后的數(shù)組：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

動圖如下：

【冒泡排序的特性總結(jié)】

1. 冒泡排序是一種非常容易理解的排序
2. 時間復(fù)雜度：O(N^2)
3. 空間復(fù)雜度：O(1)
4. 穩(wěn)定性：穩(wěn)定

4.2快速排序

快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法,

其基本思想為：任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。

4.2.1Hoare版

實現(xiàn)思路：
1: 首先，從數(shù)組的左端和右端分別設(shè)置一個指針，即i和j，以及選擇一個基準(zhǔn)值pivot。

2:通過循環(huán)，從數(shù)組的右端開始向左查找，找到第一個小于基準(zhǔn)值的元素的下標(biāo)，將該下標(biāo)賦給 j 。然后從數(shù)組的左端開始向右查找，找到第一個大于基準(zhǔn)值的元素的下標(biāo)，將該下標(biāo)賦給 i 。

3: 在找到兩個元素的下標(biāo)后，交換它們的位置，將小于基準(zhǔn)值的元素移動到基準(zhǔn)值的左邊，大于基準(zhǔn)值的元素移動到基準(zhǔn)值的右邊。然后繼續(xù)循環(huán)，直到左指針i大于等于右指針j。

最后，將基準(zhǔn)值放在正確的位置上，將其與左指針i所指向的元素進(jìn)行交換。這樣，基準(zhǔn)值左邊的元素都小于基準(zhǔn)值，右邊的元素都大于基準(zhǔn)值。

需要注意的是：若選擇最左邊的數(shù)據(jù)作為key，則需要right先走；若選擇最右邊的數(shù)據(jù)作為key，則需要left先走

動圖如下：

private static int partition(int[] array, int left, int right) {
  // 設(shè)置左右指針和基準(zhǔn)值
  int i = left;
  int j = right;
  int pivot = array[left];
  
  // 在左指針小于右指針的條件下，進(jìn)行循環(huán)
  while (i < j) {
    // 從右往左找到第一個小于基準(zhǔn)值的元素的下標(biāo)
    while (i < j && array[j] >= pivot) {
      j--;
   }
  
    // 從左往右找到第一個大于基準(zhǔn)值的元素的下標(biāo)
    while (i < j && array[i] <= pivot) {
      i++;
   }
  
    // 交換找到的兩個元素的位置
    swap(array, i, j);
 }
  
  // 將基準(zhǔn)值放在正確的位置上
  swap(array, i, left);
  
  // 返回基準(zhǔn)值的下標(biāo)
  return i;
}

4.2.2挖坑法

實現(xiàn)思路：

1. 首先，在函數(shù)內(nèi)部定義兩個指針i和j，分別指向分區(qū)的左側(cè)和右側(cè)。初始時，將left作為基準(zhǔn)元素的索引，即基準(zhǔn)元素為array[left]。

2. 然后，通過循環(huán)，不斷將大于基準(zhǔn)元素的元素移動到右側(cè)，將小于基準(zhǔn)元素的元素移動到左側(cè)。具體的操作是，先從右側(cè)開始，找到小于或等于基準(zhǔn)元素的元素，然后將該元素移動到左側(cè)指針i的位置。

3. 接著，從左側(cè)開始，找到大于或等于基準(zhǔn)元素的元素，然后將該元素移動到右側(cè)指針j的位置。如此反復(fù)進(jìn)行，直到指針i和j相遇。

4. 最后，將基準(zhǔn)元素放置到它最終的位置上，也就是指針i的位置。這樣，基準(zhǔn)元素左側(cè)的元素都小于或等于它，右側(cè)的元素都大于或等于它。

5. 后返回基準(zhǔn)元素的索引i，用于后續(xù)的分區(qū)。

注意：若在最左邊挖坑，則需要R先走；若在最右邊挖坑，則需要L先走

動圖如下：

private static int partition(int[] array, int left, int right) {
    // 設(shè)置指針i和j分別指向分區(qū)的左側(cè)和右側(cè)
    int i = left;
    int j = right;
    // 設(shè)置基準(zhǔn)元素為分區(qū)的第一個元素
    int pivot = array[left];
    
    // 開始循環(huán)，直到指針i和j相遇
    while (i < j) {
        // 從右側(cè)開始，尋找小于或等于基準(zhǔn)元素的元素
        while (i < j && array[j] >= pivot) {
            j--;
        }
        // 找到后將該元素移動到左側(cè)指針i的位置
        array[i] = array[j];
        
        // 從左側(cè)開始，尋找大于或等于基準(zhǔn)元素的元素
        while (i < j && array[i] <= pivot) {
            i++;
        }
        // 找到后將該元素移動到右側(cè)指針j的位置
        array[j] = array[i];
    }
    
    // 將基準(zhǔn)元素放置到它最終的位置上
    array[i] = pivot;
    
    // 返回基準(zhǔn)元素的索引，用于后續(xù)的分區(qū)
    return i;
}

快速排序優(yōu)化

1. 三數(shù)取中法選key （三個數(shù)中取中間的數(shù)為基準(zhǔn)）
2. 遞歸到小的子區(qū)間時，可以考慮使用插入排序

快速排序總結(jié)：

1. 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
2. 時間復(fù)雜度：O(N*logN)
3. 空間復(fù)雜度：O(logN)（特殊情況，如果數(shù)據(jù)本身有序或者逆序，那么時間復(fù)雜度為 O （N²））
4. 穩(wěn)定性：不穩(wěn)定

時間復(fù)雜度示圖：

五：歸并排序

5.1 基本思想

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide andConquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。 歸并排序核心步驟：

動圖：

歸并排序總結(jié)：

1. 歸并的缺點在于需要O(N)的空間復(fù)雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
2. 時間復(fù)雜度：O(N*logN)
3. 空間復(fù)雜度：O(N)
4. 穩(wěn)定性：穩(wěn)定

5.2 代碼實現(xiàn)

public class MergeSort {
    // 歸并排序入口函數(shù)
    public int[] mergeSort(int[] array) {
        // 特殊情況處理：當(dāng)數(shù)組為空或只有一個元素時，無需排序，直接返回
        if (array == null || array.length <= 1) {
            return array;
        }
        
        // 調(diào)用歸并排序算法進(jìn)行排序
        mergeSort(array, 0, array.length - 1);
        
        return array;
    }
    
    // 歸并排序遞歸函數(shù)
    private void mergeSort(int[] array, int start, int end) {
        // 當(dāng)前排序范圍只有一個元素，無需繼續(xù)拆分
        if (start >= end) {
            return;
        }
        
        // 找到當(dāng)前排序范圍的中間位置
        int mid = start + (end - start) / 2;
        
        // 遞歸拆分左半部分
        mergeSort(array, start, mid);
        // 遞歸拆分右半部分
        mergeSort(array, mid + 1, end);
        
        // 合并左右兩部分排序結(jié)果
        merge(array, start, mid, end);
    }
    
    // 歸并兩個有序數(shù)組
    private void merge(int[] array, int start, int mid, int end) {
        // 創(chuàng)建一個臨時數(shù)組保存合并的結(jié)果
        int[] temp = new int[end - start + 1];
        
        int i = start;  // 左半部分起始位置
        int j = mid + 1;  // 右半部分起始位置
        int k = 0;  // 臨時數(shù)組的索引
        
        // 遍歷左右兩部分?jǐn)?shù)組，依次取出較小的元素放入臨時數(shù)組中
        while (i <= mid && j <= end) {
            if (array[i] < array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }
        
        // 處理剩余的元素
        while (i <= mid) {
            temp[k++] = array[i++];
        }
        
        while (j <= end) {
            temp[k++] = array[j++];
        }
        
        // 將臨時數(shù)組中的元素拷貝回原數(shù)組中
        for (i = 0; i < temp.length; i++) {
            array[start + i] = temp[i];
        }
    }
}

5.3海量數(shù)據(jù)的排序問題

外部排序：排序過程需要在磁盤等外部存儲進(jìn)行的排序

案例：內(nèi)存只有 1G，需要排序的數(shù)據(jù)有 100G因為內(nèi)存中因為無法把所有數(shù)據(jù)全部放下，所以需要外部排序，而歸并排序是最常用的外部排序

1. 先把文件切分成 200 份，每個 512 M
2. 分別對 512 M 排序，因為內(nèi)存已經(jīng)可以放的下，所以任意排序方式都可以
3. 進(jìn)行 2路歸并，同時對 200 份有序文件做歸并過程，最終結(jié)果就有序了

六：排序總結(jié)

6.1排序算法復(fù)雜度及穩(wěn)定性分析

文章來源地址http://www.zghlxwxcb.cn/news/detail-721826.html

6.2各個排序的比較

到了這里，關(guān)于七大排序 (9000字詳解直接插入排序，希爾排序，選擇排序，堆排序，冒泡排序，快速排序，歸并排序）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！