数据结构——排序

一、排序的基本概念

1. 排序的定义

所谓排序（Sorting）就是将数据表调整为按关键字从小到大，或从大到小的次序排列的过程。
排序（Sorting）是一种将一组元素按照特定顺序重新排列的过程。通常，排序的目的是使元素按照某种规则（如升序或降序）排列，以便于查找、比较或其他操作。
对一个数据表来说，不同的要求可能会选择不同的字段作为其关键字。

输入:

一个包含 ( n ) 个元素的序列 ( $S = [s_1, s_2, \dots, s_n]$ )，其中每个元素 ( $s_i$ ) 可以是数字、字符串或其他可比较的数据类型。

一个比较函数或规则，用于确定元素之间的顺序（如升序或降序）。

输出

一个包含相同元素的序列 ( $S' = [s'_1, s'_2, \dots, s'_n]$ )，其中元素按照给定的比较规则排列。例如，对于升序排序，( $s'_1 \leq s'_2 \leq \dots \leq s'_n$ )。

2. 排序的分类

（1）增排序和减排序

如果排序的结果是按关键字从小到大的次序排列的，就是增排序，否则就是减排序。

（2）内部排序和外部排序

如果在排序过程中，数据表中的所有数据均在内存中，则这类排序为内部排序，否则为外部排序。

（3）稳定排序和不稳定排序

在排序过程中，如果关键字相同的两个元素的相对次序不变，则称为稳定排序，否则是不稳定排序。
排序的稳定性是排序算法的一个性质，无关算法的优劣判定。若待排序表中关键字唯一，则考虑排序算法时稳定性与其无关紧要。

算法稳定性（Stability）是指排序算法在处理具有相同关键字的元素时，是否能够保持它们在原始序列中的相对顺序。

稳定排序算法：如果两个元素 ( $s_i$ ) 和 ( $s_j$ ) 在原始序列中满足 ( $s_i$ = $s_j$ ) 且 ( i < j )，那么在排序后的序列中，( $s_i$ ) 仍然出现在 ( $s_j$ ) 之前。

不稳定排序算法：不保证具有相同关键字的元素在排序后保持原始相对顺序。

（4）单关键字/多关键字排序

（5）排序的基本方法

虽然存在多种排序算法，但按照各算法所采用的基本方法可将其划分为：插入排序、交换排序、选择排序、归并排序和基数排序。

4. 归并排序

5. 基数排序

二、直接插入排序

1. 算法思想

直接插入排序（Insertion Sort）是一种简单的排序算法，其核心思想是将待排序的元素逐个插入到已排序部分的适当位置，直到所有元素都插入完毕。

具体步骤：

初始状态：假设第一个元素已经是有序的。
插入过程：从第二个元素开始，依次将每个元素插入到前面已排序的部分中。
- 将当前元素与已排序部分的元素从后向前比较。
- 如果当前元素小于已排序部分的某个元素，则将该元素向后移动一位。
- 重复上述过程，直到找到合适的位置插入当前元素。
重复：重复上述过程，直到所有元素都插入到正确的位置。

示例：
假设有一个数组 [5, 2, 4, 6, 1, 3]，排序过程如下：

初始状态：[5]（第一个元素已排序）
插入2：[2, 5]
插入4：[2, 4, 5]
插入6：[2, 4, 5, 6]
插入1：[1, 2, 4, 5, 6]
插入3：[1, 2, 3, 4, 5, 6]

2. 性能分析

时间复杂度：
- 最好情况：当数组已经有序时，每次插入只需比较一次，时间复杂度为 O(n)。
- 最坏情况：当数组逆序时，每次插入需要比较和移动所有已排序元素，时间复杂度为 O(n²)。
- 平均情况：时间复杂度为 O(n²)。
空间复杂度：直接插入排序是原地排序算法，只需要常数级别的额外空间，空间复杂度为 O(1)。

3. 稳定性

直接插入排序是稳定的排序算法。因为在插入过程中，相等的元素不会改变它们的相对顺序。

4. 适用性

适用场景：
- 数据量较小或部分有序的数组。
- 数据基本有序时，插入排序的效率较高。
- 适用于链表结构，因为插入操作不需要移动大量元素。
不适用场景：
- 数据量较大且无序时，插入排序的效率较低。

5. 代码

数组例图

void insertSort( elementType A[], int n )
{                                      //A[0]单元未用
	for ( i=2; i<=n; i++)    //未排序区逐个取出元素
    {
	    temp=A[i];     //当前元素暂存临时变量
        j=i-1;              //j从1到i-1为已经排序区
	    while ( (A[j].key>temp.key) && (j>=1) )
   	    {
             A[j+1] =A[j];  
             j--;
         }
  	    A[j+1]=temp;  //注意j+1才是目标位置哦
	}
}

以下代码引入监视哨：

void insertSort( elementType A[], int n )
{                                   //A[0]作为转储单元
	for ( i=2; i<=n; i++) 
    {
		A[0]=A[i]; 
            j=i-1;
		while ( A[j].key>A[0].key )
		{
                A[j+1]=A[j];  
                j--;
            }
		A[j+1]=A[0] ;
	}
}

即未使用的A[0]作为temp。

三、折半插入排序

折半插入排序（Binary Insertion Sort）是对直接插入排序的优化，通过使用二分查找来减少比较次数，从而提高查找插入位置的效率。

1. 算法思想

折半插入排序的核心思想与直接插入排序类似，都是将待排序元素插入到已排序部分的适当位置。不同的是，折半插入排序在查找插入位置时使用了二分查找，而不是逐个比较。

具体步骤：

初始状态：假设第一个元素已经是有序的。
插入过程：
- 从第二个元素开始，依次将每个元素插入到前面已排序的部分中。
- 使用二分查找在已排序部分中找到当前元素的插入位置。
- 将插入位置后的元素依次向后移动一位。
- 将当前元素插入到正确的位置。
重复：重复上述过程，直到所有元素都插入到正确的位置。

2. 性能分析

时间复杂度：
- 最好情况：当数组已经有序时，每次插入只需比较一次，时间复杂度为 O(n)。
- 最坏情况：当数组逆序时，每次插入需要移动所有已排序元素，时间复杂度为 O(n²)。
- 平均情况：时间复杂度为 O(n²)。
虽然折半插入排序减少了比较次数（从 O(n) 降到 O(log n)），但元素的移动次数仍然是 O(n²)，因此整体时间复杂度仍为 O(n²)。
空间复杂度：折半插入排序是原地排序算法，只需要常数级别的额外空间，空间复杂度为 O(1)。

3. 稳定性

折半插入排序是稳定的排序算法。因为在插入过程中，相等的元素不会改变它们的相对顺序。

4. 适用性

适用场景：
- 数据量较小或部分有序的数组。
- 当比较操作的开销较大时（例如比较字符串或复杂对象），折半插入排序可以减少比较次数。
不适用场景：
- 数据量较大且无序时，折半插入排序的效率仍然较低。

5. 代码实现

void insertSort( elementType A[], int n ) {
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){                      // 依次将A[2]~A[n]插入到前面的已排序序列
        A[0] = A[i];                        // 将A[i]暂存到A[0]
        low = 1;
        high = i-1;                         // 设置折半查找的范围
        while(low <= high) {                // 折半查找，默认递增有序
            mid = (low+high/)/2;            // 取中间点
            if(A[mid]>=A[0]) high = mid -1; // 查找左半子表
            else high = mid + 1;            // 查找右半子表
        }
        for (j=i-1;j>=high+1;j--){
            A[j+1]=A[j];                    // 统一后移元素，空出插入位置
        }
        A[high+1]=A[0];                     // 插入操作
    }
}

四、起泡排序(bubble sort)

1. 算法思想

冒泡排序是一种简单直观的排序算法，它通过相邻元素的比较和交换，将较大的元素逐步“冒泡”到数组的最后，最终实现排序。

具体过程如下：

从第一个元素开始，逐个比较相邻的两个元素：
- 如果前者大于后者，则交换它们的位置；
- 否则，不交换。
遍历一轮后，最大的元素会被放到最后（就像气泡上浮）。
重复以上过程，每次排序后未排序部分的元素减少一个，直到整个数组有序。

假设有一个数组 [5, 3, 8, 6, 2]，用冒泡排序进行排序：

轮次	过程（交换的元素加标注）	结果
第 1 轮	(5,3), 8, (8,6), (8,2)	`[3, 5, 6, 2, 8]`
第 2 轮	3, (5,6), (6,2), 8	`[3, 5, 2, 6, 8]`
第 3 轮	3, (5,2), 6, 8	`[3, 2, 5, 6, 8]`
第 4 轮	(3,2), 5, 6, 8	`[2, 3, 5, 6, 8]`

最终数组变为 [2, 3, 5, 6, 8]，排序完成。

2. 性能分析

冒泡排序的时间复杂度主要取决于比较和交换的次数：

最坏情况（逆序排列，如 [5,4,3,2,1]）：
- 每次都需要交换，复杂度为 O(n²)。
最好情况（已经有序，如 [1,2,3,4,5]）：
- 如果使用“冒泡排序优化”（加入 flag 标记是否发生交换），则只需 O(n)。
平均情况：约为 O(n²)。

情况	时间复杂度
最坏情况（完全逆序）	O(n²)
最好情况（已排序）	O(n) (优化版)
平均情况	O(n²)

3. 稳定性

冒泡排序是稳定的排序算法。
原因：相等的元素在交换过程中不会改变相对位置。

4. 适用性

适用于：

数据量小（n 较小时，冒泡排序的实现简单，便于理解）。
基本有序的数据（优化版的冒泡排序可在 O(n) 内完成）。
对稳定性有要求的场景（不会改变相等元素的相对位置）。

不适用于：

大规模数据排序（O(n²) 复杂度在 n 较大时性能低）。
对性能要求较高的场景（如快速排序、归并排序更优）。
大量随机数据（交换次数较多，效率低）。

5. 优化冒泡排序

如果在某一轮遍历时 没有发生交换，说明数组已经有序，可以提前结束排序，优化时间复杂度至 O(n)。

6. 优化代码

void bubbleSort(int arr[], int n) {
    bool swapped;  // 标记是否发生交换
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;  // 如果没有交换，说明已排序，提前结束
    }
}

五、简单选择排序

1. 算法思想

简单选择排序（Selection Sort）是一种直观但 性能较低 的排序算法，其核心思想是：

每轮从未排序部分选择最小（或最大）元素。
将其放到未排序部分的最前面。
重复以上过程，直到数组有序。

主要步骤：

设数组长度为 n，外层循环 i 遍历 0 到 n-2：
- 在 arr[i] 到 arr[n-1] 中 找最小值，并 交换到 arr[i] 位置。
- i++，重复步骤，直到排序完成。

假设有数组 [6, 2, 8, 4, 1]，执行选择排序：

轮次	过程（找到最小值并交换）	结果
第1轮	最小值 `1` 交换到 `arr[0]`	`[1, 2, 8, 4, 6]`
第2轮	最小值 `2` 位置不变	`[1, 2, 8, 4, 6]`
第3轮	最小值 `4` 交换到 `arr[2]`	`[1, 2, 4, 8, 6]`
第4轮	最小值 `6` 交换到 `arr[3]`	`[1, 2, 4, 6, 8]`
最终结果		`[1, 2, 4, 6, 8]`

2. 性能分析

时间复杂度:

情况	时间复杂度
最坏情况（逆序，如 `[5,4,3,2,1]`）	O(n²)
最好情况（已排序，如 `[1,2,3,4,5]`）	O(n²)
平均情况	O(n²)

无论如何，都要进行 (n-1) + (n-2) + ... + 1 ≈ n²/2 次比较，即 O(n²)。
交换次数较少，每轮最多 1 次交换，总交换次数为 O(n)，比冒泡排序（O(n²) 交换）更少。

空间复杂度:

O(1)，是原地排序，不需要额外存储空间。

3. 稳定性

选择排序 是 不稳定排序。

原因：交换可能改变相同元素的相对顺序。

1 2	`初始： [3, 3', 2, 5] 第一轮：2 和 3 交换 -> [2, 3', 3, 5] （3' 和 3 顺序改变）`

因此，选择排序 不是稳定的。

4. 适用性

适用于：

数据量小（如 n < 1000）。
交换代价高，因为选择排序的交换次数最少，仅 O(n) 次。

不适用于：

大规模数据排序（O(n²) 复杂度在大数据场景下性能太低）。
稳定性要求高的场景（应使用归并排序、插入排序等稳定算法）。

5. 代码

标准版

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;  // 记录最小值索引
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        swap(arr[i], arr[minIndex]);  // 交换最小值到当前位置
    }
}

双向选择排序（改进版）

void selectionSortOptimized(int arr[], int n) {
    int left = 0, right = n - 1;
    while (left < right) {
        int minIndex = left, maxIndex = right;

        for (int i = left; i <= right; i++) {
            if (arr[i] < arr[minIndex]) minIndex = i;
            if (arr[i] > arr[maxIndex]) maxIndex = i;
        }

        swap(arr[left], arr[minIndex]);
        if (maxIndex == left) maxIndex = minIndex; // 避免因最小值交换导致 maxIndex 失效
        swap(arr[right], arr[maxIndex]);

        left++;
        right--;
    }
}

优化点：

每轮找到最小值和最大值，一次交换两个，减少排序轮数。

六、希尔排序(shell sort)

1. 算法思想

希尔排序是一种基于插入排序的改进算法，也称为 缩小增量排序（Diminishing Increment Sort）。其核心思想是：

通过 步长（gap） 将数组划分为多个子序列，在每个子序列中进行 直接插入排序，以减少数据的无序程度。
随着步长逐渐缩小，最终步长为 1，此时整个数组进行一次标准的直接插入排序，从而得到有序数组。

具体过程如下：

选择一个合适的初始步长 gap（常见的取值方法包括 gap = n/2，或使用 Hibbard、Knuth 等增量序列）。
以 gap 为间隔，将数组划分为若干个子序列，并对每个子序列进行插入排序。
逐步缩小 gap，重复上述过程，直到 gap=1，最终完成排序。

我们以 数组 [8, 9, 1, 7, 2, 3, 5, 4, 6, 0] 为例，演示希尔排序的过程，采用 增量序列 gap = n/2（即 5 → 2 → 1）。

步骤 1：gap = 5
将数组按 gap=5 分成 5 组，然后分别对每组执行 插入排序。

初始数组：

1 2	`索引: 0 1 2 3 4 5 6 7 8 9 数组: [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]`

按照 gap=5 分组：

组 1: (索引 0, 5) → [8, 3]
组 2: (索引 1, 6) → [9, 5]
组 3: (索引 2, 7) → [1, 4]
组 4: (索引 3, 8) → [7, 6]
组 5: (索引 4, 9) → [2, 0]

对每组进行插入排序：

组 1: [8, 3] → [3, 8]
组 2: [9, 5] → [5, 9]
组 3: [1, 4] → [1, 4]
组 4: [7, 6] → [6, 7]
组 5: [2, 0] → [0, 2]

排序后数组：

1 2	`索引: 0 1 2 3 4 5 6 7 8 9 数组: [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]`

步骤 2：gap = 2

再次对 gap=2 进行分组：

1 2	`组 1: (索引 0, 2, 4, 6, 8) → [3, 1, 0, 9, 7] 组 2: (索引 1, 3, 5, 7, 9) → [5, 6, 8, 4, 2]`

对每组进行插入排序：

1 2	`组 1: [3, 1, 0, 9, 7] → [0, 1, 3, 7, 9] 组 2: [5, 6, 8, 4, 2] → [2, 4, 5, 6, 8]`

排序后数组：

1 2	`索引: 0 1 2 3 4 5 6 7 8 9 数组: [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]`

步骤 3：gap = 1（最终插入排序）

对整个数组执行 插入排序：

1	`初始: [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]`

逐步插入：

1. 插入 1 → [0, 1, 2, 4, 3, 5, 7, 6, 9, 8]
2. 插入 3 → [0, 1, 2, 3, 4, 5, 7, 6, 9, 8]
3. 插入 6 → [0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
4. 插入 8 → [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

最终有序数组：

1	`[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]`

2. 性能分析

希尔排序的性能与步长序列的选择密切相关，不同步长序列会影响排序效率。其时间复杂度分析如下：

最优情况（适当的步长序列）：接近 O(n log n)（例如采用 Sedgewick 增量序列）。
平均情况：一般在 O(n^{1.3} ~ O(n^{1.5}) 之间。
最坏情况：可达 O(n^2)，例如使用 gap=n/2 且数据排列不佳时。

相比直接插入排序，希尔排序减少了数据移动次数，提高了整体效率，特别适用于大规模数据排序。

3. 稳定性

希尔排序是不稳定排序算法。
原因在于：当 gap 较大时，元素可能会跨越多个位置进行交换，导致相同元素的相对顺序被打乱。例如，若数组 [5, 3, 5, 2] 经过 gap=2 处理后可能变为 [5, 2, 5, 3]，从而破坏了稳定性。

4. 适用性

希尔排序适用于：

数据量大但基本有序（比插入排序快）。
对原地排序有需求（无需额外空间）。
数据分布无特殊限制。

但在以下情况可能不适用：

要求稳定性（例如处理相同键值的数据）。
需要最优时间复杂度（快速排序或归并排序通常更优）。

5. 代码

void shellSort(elementType A[], int n){
    // A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    int dk,i,j;
    for(dk=n/2;dk>=1;dk=dk/2){              // 增量变化，无统一规定
        for(i=dk+1;i<=n;++i)
            {
                if (A[i]<A[i-dk]){          // 须将A[i]插入有序增量子表
                    A[0] = a[i];            // 暂存在A[0]
                    for(j=i-dk;j>0&&A[0]<A[j];j-=dk){
                        A[j+dk] = A[j];     // 记录后移，查找插入位置
                    }
                    A[j+dk] = A[0];         // 插入
                }
            }
    }
}

七、快速排序

1. 算法思想

快速排序（Quick Sort）是一种基于分治（Divide and Conquer）思想的高效排序算法，主要步骤如下：

选取基准（Pivot）：从数组中选一个元素作为基准值（pivot）。
分区（Partition）：
- 重新排列数组，使得：
  - 左侧的元素 ≤ pivot
  - 右侧的元素 ≥ pivot
- 基准元素放入最终正确的位置。
递归排序：
- 对基准左侧和右侧的两个子数组分别递归执行快速排序，直到子数组长度为 1 或 0。

以数组 [6, 2, 8, 4, 1, 9, 5] 为例：

选取 5 作为基准值（pivot）。
重新排列：[2, 4, 1, 5, 8, 9, 6]（5 的左边都是 ≤5，右边都是 ≥5）。
递归处理 [2, 4, 1] 和 [8, 9, 6]：
- [2, 4, 1] 选 2 作为 pivot，排序为 [1, 2, 4]。
- [8, 9, 6] 选 8 作为 pivot，排序为 [6, 8, 9]。
合并后得到最终结果 [1, 2, 4, 5, 6, 8, 9]。

2. 性能分析

时间复杂度
- 平均情况：快速排序的分区过程每次将数组分为两半，因此递归深度为 log n，每次需要 O(n) 的比较，整体复杂度为 O(n log n)。
- 最坏情况（已排序或逆序排列且总是选到最小/最大值作为 pivot）：
  - 递归深度变为 O(n)，总比较次数为 O(n²)。
  - 解决方法：随机选取 pivot 或 三数取中法（median-of-three）。

情况	时间复杂度
最优情况（均分）	O(n log n)
平均情况	O(n log n)
最坏情况（已排序数组）	O(n²)

空间复杂度
- O(log n)（递归调用栈），最坏情况下 O(n)（递归深度等于数组长度）。
- 采用 尾递归优化 或 非递归方式 可降低空间消耗。

3. 稳定性

快速排序 不是稳定排序。
原因：元素可能会跨区域交换，导致相同元素的相对顺序发生变化。

1
2
3

初始： [3, 3', 2, 5]
若 pivot = 2，则 3 和 3' 可能换位置
排序后： [2, 3', 3, 5]（3 在 3' 后面，相对顺序改变）

因此，快速排序不稳定。

4. 适用性

适用于：

大数据量排序（O(n log n) 复杂度，比 O(n²) 的冒泡/插入排序快）。
内存有限的场景（空间复杂度 O(log n)）。
一般用途的高效排序（大多数编程语言标准库实现）。

不适用于：

数据接近有序（会退化为 O(n²)，应使用三数取中法）。
对稳定性有要求（使用归并排序或插入排序）。

5. 代码

递归版（经典实现）

// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选取最后一个元素作为基准
    int i = low - 1;  // i 指向小于 pivot 的最后一个位置

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);  // 交换比 pivot 小的元素
        }
    }
    swap(arr[i + 1], arr[high]);  // 把 pivot 放到正确位置
    return i + 1;
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  // 找到 pivot 位置
        quickSort(arr, low, pi - 1);  // 递归左半部分
        quickSort(arr, pi + 1, high); // 递归右半部分
    }
}

优化版（随机化基准）

#include <cstdlib>  // 引入随机数库

int randomizedPartition(int arr[], int low, int high) {
    int randomIdx = low + rand() % (high - low + 1);
    swap(arr[randomIdx], arr[high]);  // 随机选取 pivot
    return partition(arr, low, high);
}

void randomizedQuickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = randomizedPartition(arr, low, high);
        randomizedQuickSort(arr, low, pi - 1);
        randomizedQuickSort(arr, pi + 1, high);
    }
}

数据结构——排序

一、排序的基本概念

1. 排序的定义

2. 排序的分类

（1）增排序和减排序

（2）内部排序和外部排序

（3）稳定排序和不稳定排序

（4）单关键字/多关键字排序

（5）排序的基本方法

1. 插入排序

2. 交换排序

3. 选择排序

4. 归并排序

5. 基数排序

二、直接插入排序

1. 算法思想

2. 性能分析

3. 稳定性

4. 适用性

5. 代码

三、折半插入排序

1. 算法思想

2. 性能分析

3. 稳定性

4. 适用性

5. 代码实现

四、起泡排序(bubble sort)

1. 算法思想

2. 性能分析

3. 稳定性

4. 适用性

5. 优化冒泡排序

6. 优化代码

五、简单选择排序

1. 算法思想

2. 性能分析

3. 稳定性

4. 适用性

5. 代码

标准版

双向选择排序（改进版）

六、希尔排序(shell sort)

1. 算法思想

2. 性能分析

3. 稳定性

4. 适用性

5. 代码

七、快速排序

1. 算法思想

2. 性能分析

3. 稳定性

4. 适用性

5. 代码

递归版（经典实现）

优化版（随机化基准）

八、堆排序

1. 算法思想

2. 性能分析

3. 稳定性

4. 适用性

5. 代码

九、二路归并排序(merge sort)

1. 算法思想

2. 性能分析

3. 稳定性

4. 适用性

5. 代码

十、基数排序

1. 算法思想

2. 性能分析

3. 稳定性

4. 适用性

5. 代码

十一、外部排序

十二、排序算法的分析和应用