数据结构（第八章排序算法）-EW帮帮网

一.直接插入排序

直接插入排序（Insertion Sort） 是一种简单直观的排序算法。它的工作原理类似于整理扑克牌：每次从未排序部分取出一个元素，将其插入到已排序部分的适当位置，直到所有元素都被排序。

1. 算法思想

将数组分为两部分：已排序部分和未排序部分。
初始时，已排序部分只包含第一个元素，未排序部分包含剩余元素。
每次从未排序部分取出第一个元素，将其插入到已排序部分的适当位置。
重复上述过程，直到未排序部分为空。

2. 算法步骤

从第二个元素开始（假设第一个元素已排序）。
将当前元素与已排序部分的元素从后向前比较。
如果当前元素小于已排序部分的元素，则将已排序部分的元素向后移动一位。
重复步骤 3，直到找到当前元素的正确位置。
将当前元素插入到正确位置。
重复上述过程，直到所有元素都被排序。

3. 代码实现

C++ 实现

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // 当前待插入的元素
        int j = i - 1;

        // 将比 key 大的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        // 插入 key 到正确位置
        arr[j + 1] = key;
    }
}

Python 实现

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]  # 当前待插入的元素
        j = i - 1

        # 将比 key 大的元素向后移动
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        # 插入 key 到正确位置
        arr[j + 1] = key

4. 示例

假设数组为 [5, 2, 4, 6, 1, 3]，排序过程如下：

初始状态：[5, 2, 4, 6, 1, 3]
插入 2：[2, 5, 4, 6, 1, 3]
插入 4：[2, 4, 5, 6, 1, 3]
插入 6：[2, 4, 5, 6, 1, 3]
插入 1：[1, 2, 4, 5, 6, 3]
插入 3：[1, 2, 3, 4, 5, 6]

最终排序结果：[1, 2, 3, 4, 5, 6]

5. 时间复杂度

最坏情况：数组完全逆序，时间复杂度为 O(n2)。
最好情况：数组已经有序，时间复杂度为 O(n)。
平均情况：时间复杂度为 O(n2)。

6. 空间复杂度

直接插入排序是 原地排序算法，空间复杂度为 O(1)。

7. 稳定性

直接插入排序是 稳定排序算法，相同元素的相对位置不会改变。

8. 优缺点

优点：

实现简单，代码易于理解。
对小规模数据或基本有序的数据效率较高。
是稳定排序算法。

缺点：

对大规模数据效率较低，时间复杂度为 O(n2)O(n2)。
不适合数据量较大的场景。

9. 适用场景

数据量较小。
数据基本有序。
需要稳定排序的场景。

10. 优化

10.1 二分插入排序

在查找插入位置时，使用二分查找将时间复杂度从 O(n)优化到 O(log⁡n)。
但移动元素的时间复杂度仍为 O(n)，因此总体时间复杂度仍为 O(n2)。

代码实现：

void binaryInsertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int left = 0, right = i - 1;

        // 二分查找插入位置
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        // 移动元素
        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }

        // 插入元素
        arr[left] = key;
    }
}

二.折半插入排序

折半插入排序（Binary Insertion Sort） 是直接插入排序的一种优化版本。它通过 二分查找 来减少比较次数，从而提高查找插入位置的效率。尽管移动元素的时间复杂度仍然是 O(n)，但折半插入排序在数据量较大时比直接插入排序更快。

1. 算法思想

将数组分为两部分：已排序部分和未排序部分。
初始时，已排序部分只包含第一个元素，未排序部分包含剩余元素。
每次从未排序部分取出第一个元素，使用二分查找确定其在已排序部分的插入位置。
将元素插入到正确位置，并移动后续元素。
重复上述过程，直到未排序部分为空。

2. 算法步骤

从第二个元素开始（假设第一个元素已排序）。
使用二分查找在已排序部分中找到当前元素的插入位置。
将插入位置后的所有元素向后移动一位。
将当前元素插入到正确位置。
重复上述过程，直到所有元素都被排序。

3. 代码实现

C++ 实现

void binaryInsertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // 当前待插入的元素
        int left = 0, right = i - 1;

        // 二分查找插入位置
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        // 移动元素
        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }

        // 插入元素
        arr[left] = key;
    }
}

Python 实现


def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]  # 当前待插入的元素
        left, right = 0, i - 1

        # 二分查找插入位置
        while left <= right:
            mid = left + (right - left) // 2
            if arr[mid] > key:
                right = mid - 1
            else:
                left = mid + 1

        # 移动元素
        for j in range(i - 1, left - 1, -1):
            arr[j + 1] = arr[j]

        # 插入元素
        arr[left] = key

4. 示例

假设数组为 [5, 2, 4, 6, 1, 3]，排序过程如下：

初始状态：[5, 2, 4, 6, 1, 3]
插入 2：[2, 5, 4, 6, 1, 3]
插入 4：[2, 4, 5, 6, 1, 3]
插入 6：[2, 4, 5, 6, 1, 3]
插入 1：[1, 2, 4, 5, 6, 3]
插入 3：[1, 2, 3, 4, 5, 6]

最终排序结果：[1, 2, 3, 4, 5, 6]

5. 时间复杂度

查找插入位置：使用二分查找，时间复杂度为 O(log⁡n)。
移动元素：最坏情况下需要移动 O(n)个元素。
总体时间复杂度：O(n2)。

尽管查找插入位置的时间复杂度降低到 O(log⁡n)，但由于移动元素的时间复杂度仍然是O(n)，因此总体时间复杂度仍为O(n2)。

6. 空间复杂度

折半插入排序是 原地排序算法，空间复杂度为 O(1)。

7. 稳定性

折半插入排序是 稳定排序算法，相同元素的相对位置不会改变。

8. 优缺点

优点：

比直接插入排序减少了比较次数，适合数据量较大的场景。
实现简单，代码易于理解。
是稳定排序算法。

缺点：

移动元素的时间复杂度仍然是 O(n)，总体时间复杂度为 O(n2)。
不适合数据量非常大的场景。

9. 适用场景

数据量较大且需要稳定排序的场景。
数据基本有序时，效率较高。

10. 与直接插入排序的比较

特性	直接插入排序	折半插入排序
比较次数	O(n2)	O(nlog⁡n)
移动次数	O(n2)	O(n2）
时间复杂度	O(n2)	O(n2)
适用场景	数据量较小或基本有序	数据量较大或基本有序

三.希尔排序

希尔排序（Shell Sort） 是插入排序的一种高效改进版本，也称为 缩小增量排序。它通过将数组分成若干子序列，对每个子序列进行插入排序，逐步减少子序列的长度，最终完成整个数组的排序。希尔排序的核心思想是 使数组中任意间隔为 h 的元素有序，从而减少后续插入排序的工作量。

1. 算法思想

增量序列：选择一个增量序列 h1,h2,…,hk，其中 h1>h2>⋯>hk=1。
分组插入排序：对于每个增量 hihi，将数组分成若干子序列，每个子序列包含间隔为 hihi 的元素，对每个子序列进行插入排序。
逐步缩小增量：重复上述过程，直到增量为 1，此时对整个数组进行插入排序。

2. 算法步骤

选择一个增量序列（如 h=n/2,n/4,…,1）。
对于每个增量 hh：
- 将数组分成若干子序列，每个子序列包含间隔为 h 的元素。
- 对每个子序列进行插入排序。
重复上述过程，直到增量为 1，此时对整个数组进行插入排序。

3. 代码实现

C++ 实现

void shellSort(int arr[], int n) {
    // 选择增量序列
    for (int h = n / 2; h > 0; h /= 2) {
        // 对每个子序列进行插入排序
        for (int i = h; i < n; i++) {
            int key = arr[i];
            int j = i;
            // 插入排序
            while (j >= h && arr[j - h] > key) {
                arr[j] = arr[j - h];
                j -= h;
            }
            arr[j] = key;
        }
    }
}

Python 实现

def shell_sort(arr):
    n = len(arr)
    # 选择增量序列
    h = n // 2
    while h > 0:
        # 对每个子序列进行插入排序
        for i in range(h, n):
            key = arr[i]
            j = i
            # 插入排序
            while j >= h and arr[j - h] > key:
                arr[j] = arr[j - h]
                j -= h
            arr[j] = key
        h //= 2

4. 示例

假设数组为 [5, 2, 4, 6, 1, 3]，增量序列为 [3, 1]，排序过程如下：

增量 h=3：
- 子序列 1：[5, 6] → 排序后：[5, 6]
- 子序列 2：[2, 1] → 排序后：[1, 2]
- 子序列 3：[4, 3] → 排序后：[3, 4]
- 数组变为：[5, 1, 3, 6, 2, 4]
增量 h=1：
- 对整个数组进行插入排序：
  - 插入 1：[1, 5, 3, 6, 2, 4]
  - 插入 3：[1, 3, 5, 6, 2, 4]
  - 插入 6：[1, 3, 5, 6, 2, 4]
  - 插入 2：[1, 2, 3, 5, 6, 4]
  - 插入 4：[1, 2, 3, 4, 5, 6]

最终排序结果：[1, 2, 3, 4, 5, 6]

5. 时间复杂度

最坏情况：取决于增量序列的选择，通常为 O(n2)。
最好情况：当数组已经有序时，时间复杂度为 O(nlog⁡n)。
平均情况：取决于增量序列的选择，通常为 O( $n^{1.5}$ )。

6. 空间复杂度

希尔排序是 原地排序算法，空间复杂度为 O(1)。

7. 稳定性

希尔排序是 不稳定排序算法，相同元素的相对位置可能会改变。

8. 优缺点

优点：

比直接插入排序效率更高，尤其是对中等规模的数据。
实现简单，代码易于理解。
是原地排序算法，空间复杂度低。

缺点：

时间复杂度依赖于增量序列的选择。
是不稳定排序算法。

9. 增量序列的选择

增量序列的选择对希尔排序的性能有很大影响。常见的增量序列包括：

Shell 增量序列：h=n/2,n/4,…,1。
Hibbard 增量序列：h=1,3,7,15,…,2k−1。
Sedgewick 增量序列：结合了 Shell 和 Hibbard 的优点，性能更好。

10. 适用场景

数据量中等。
对稳定性没有要求。
需要原地排序的场景。

11. 与插入排序的比较

特性	直接插入排序	希尔排序
时间复杂度	O(n2)	O( $n^{1.5}$ )
空间复杂度	O(1)	O(1)
稳定性	稳定	不稳定
适用场景	数据量较小或基本有序	数据量中等

四.冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复地遍历列表，比较相邻的元素并交换它们的位置，直到整个列表有序为止。它的名字来源于较小的元素会像“气泡”一样逐渐“浮”到列表的顶端。

算法步骤

遍历列表：从列表的第一个元素开始，依次比较相邻的两个元素。
比较与交换：如果前一个元素比后一个元素大（升序排序），则交换它们的位置。
重复过程：重复上述步骤，直到没有需要交换的元素，列表完全有序。

时间复杂度

最坏情况：O(n²)（列表完全逆序）
平均情况：O(n²)
最好情况：O(n)（列表已经有序）

空间复杂度

O(1)（原地排序，不需要额外空间）

代码实现（Python）

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 标志位，用于优化（如果某次遍历没有交换，说明已经有序）
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                # 交换相邻元素
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # 如果没有发生交换，提前退出
        if not swapped:
            break
    return arr

# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("排序后的数组:", sorted_arr)

示例运行结果

排序后的数组: [11, 12, 22, 25, 34, 64, 90]

c++

 for(int i = 0 ; i < n ; i ++)
    {
        for(int j = 0 ; j < n - i - 1; j ++)
        {
            if(a[j] > a[j+1])
            {
                int t = a[j+1];
                a[j+1] = a[j];
                a[j] = t;
            }
        }
    }

优化

提前终止：如果在某次遍历中没有发生任何交换，说明列表已经有序，可以提前终止算法。
记录最后一次交换位置：可以记录最后一次交换的位置，减少不必要的比较。

适用场景

适用于小规模数据或部分有序的数据。
对于大规模数据，冒泡排序的效率较低，通常选择更高效的排序算法（如快速排序、归并排序等）

五.快速排序

快速排序（Quick Sort）是一种高效的排序算法，采用分治法（Divide and Conquer）策略。它的核心思想是通过选择一个基准元素（pivot），将数组分为两部分：一部分比基准元素小，另一部分比基准元素大，然后递归地对这两部分进行排序。

算法步骤

选择基准元素：从数组中选择一个元素作为基准（通常选择第一个元素、最后一个元素或中间元素）。
分区操作：
- 将数组分为两部分：一部分比基准元素小，另一部分比基准元素大。
- 基准元素最终位于正确的位置。
递归排序：对基准元素左右两部分分别递归调用快速排序。

时间复杂度

平均情况：O(n log n)
最坏情况：O(n²)（当数组已经有序或完全逆序时，取决于基准元素的选择）
最好情况：O(n log n)

空间复杂度

O(log n)（递归调用栈的深度）

代码实现（Python）

def quick_sort(arr):
    # 如果数组长度小于等于1，直接返回
    if len(arr) <= 1:
        return arr
    
    # 选择基准元素（这里选择最后一个元素）
    pivot = arr[-1]
    
    # 分区操作
    left = [x for x in arr[:-1] if x <= pivot]  # 小于等于基准的元素
    right = [x for x in arr[:-1] if x > pivot]  # 大于基准的元素
    
    # 递归排序并合并结果
    return quick_sort(left) + [pivot] + quick_sort(right)

# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = quick_sort(arr)
print("排序后的数组:", sorted_arr)

示例运行结果

复制

排序后的数组: [11, 12, 22, 25, 34, 64, 90]

优化

随机选择基准元素：避免最坏情况（如数组已经有序），可以随机选择基准元素。
三数取中法：选择第一个、最后一个和中间元素的中位数作为基准元素。
小数组使用插入排序：当数组规模较小时，插入排序的效率更高。

适用场景

快速排序是实际应用中最常用的排序算法之一，适用于大规模数据。
对于小规模数据，插入排序或冒泡排序可能更高效。

六.简单选择排序

简单选择排序（Selection Sort）是一种直观的排序算法。它的核心思想是每次从未排序的部分中选择最小（或最大）的元素，放到已排序部分的末尾，直到所有元素有序。

算法步骤

初始化：将数组分为已排序部分和未排序部分。初始时，已排序部分为空，未排序部分为整个数组。
选择最小元素：在未排序部分中找到最小元素。
交换位置：将最小元素与未排序部分的第一个元素交换位置。
更新已排序部分：将交换后的元素纳入已排序部分。
重复过程：重复上述步骤，直到未排序部分为空。

时间复杂度

最坏情况：O(n²)
平均情况：O(n²)
最好情况：O(n²)

无论输入数据的分布如何，选择排序都需要进行 n(n-1)/2 次比较。

空间复杂度

O(1)（原地排序，不需要额外空间）

代码实现（Python）

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 假设当前未排序部分的第一个元素是最小的
        min_index = i
        # 在未排序部分中找到最小元素的索引
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # 将最小元素与未排序部分的第一个元素交换
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = selection_sort(arr)
print("排序后的数组:", sorted_arr)

示例运行结果

复制

排序后的数组: [11, 12, 22, 25, 34, 64, 90]

特点

简单直观：算法逻辑简单，易于实现。
不稳定性：选择排序是一种不稳定的排序算法（可能改变相同元素的相对顺序）。
适合小规模数据：对于小规模数据，选择排序的效率尚可接受；但对于大规模数据，效率较低。

适用场景

适用于数据量较小的情况。
当内存空间有限时，选择排序是一种不错的选择（原地排序）。

七.堆堆排

堆排序（Heap Sort） 是一种基于 二叉堆 数据结构的排序算法。它通过构建最大堆（或最小堆）来实现排序，具有 O(nlog⁡n)O(nlogn) 的时间复杂度，是一种高效的排序算法。

1. 算法思想

构建最大堆：将待排序数组构建成一个最大堆（父节点的值大于子节点的值）。
交换堆顶元素：将堆顶元素（最大值）与堆的最后一个元素交换，然后将堆的大小减 1。
调整堆：对剩余的堆进行调整，使其重新满足最大堆的性质。
重复步骤 2 和 3：直到堆的大小为 1，排序完成。

2. 算法步骤

构建最大堆：
- 从最后一个非叶子节点开始，依次向上调整每个子树，使其满足最大堆的性质。
交换堆顶元素：
- 将堆顶元素（最大值）与堆的最后一个元素交换。
调整堆：
- 对剩余的堆进行调整，使其重新满足最大堆的性质。
重复步骤 2 和 3：
- 直到堆的大小为 1，排序完成。

3. 代码实现

C++ 实现

void heapify(int arr[], int n, int i) {
    int largest = i; // 初始化最大值为根节点
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点

    // 如果左子节点大于根节点
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点大于当前最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大值不是根节点
    if (largest != i) {
        swap(arr[i], arr[largest]); // 交换
        heapify(arr, n, largest); // 递归调整子树
    }
}

void heapSort(int arr[], int n) {
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 交换堆顶元素并调整堆
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]); // 交换堆顶元素和最后一个元素
        heapify(arr, i, 0); // 调整堆
    }
}

Python 实现

def heapify(arr, n, i):
    largest = i  # 初始化最大值为根节点
    left = 2 * i + 1  # 左子节点
    right = 2 * i + 2  # 右子节点

    # 如果左子节点大于根节点
    if left < n and arr[left] > arr[largest]:
        largest = left

    # 如果右子节点大于当前最大值
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 如果最大值不是根节点
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 交换
        heapify(arr, n, largest)  # 递归调整子树

def heap_sort(arr):
    n = len(arr)

    # 构建最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 交换堆顶元素并调整堆
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # 交换堆顶元素和最后一个元素
        heapify(arr, i, 0)  # 调整堆

4. 示例

假设数组为 [5, 2, 4, 6, 1, 3]，排序过程如下：

构建最大堆：
- 初始数组：[5, 2, 4, 6, 1, 3]
- 构建后的最大堆：[6, 5, 4, 2, 1, 3]
交换堆顶元素：
- 交换堆顶元素 6 和最后一个元素 3，数组变为：[3, 5, 4, 2, 1, 6]
- 调整堆：[5, 3, 4, 2, 1, 6]
重复交换和调整：
- 交换堆顶元素 5 和最后一个元素 1，数组变为：[1, 3, 4, 2, 5, 6]
- 调整堆：[4, 3, 1, 2, 5, 6]
- 继续交换和调整，直到堆的大小为 1。

最终排序结果：[1, 2, 3, 4, 5, 6]

5. 时间复杂度

构建最大堆：O(n)。
每次调整堆：O(log⁡n)。
总体时间复杂度：O(nlog⁡n)。

6. 空间复杂度

堆排序是 原地排序算法，空间复杂度为 O(1)。

7. 稳定性

堆排序是 不稳定排序算法，相同元素的相对位置可能会改变。

8. 优缺点

优点：

时间复杂度为 O(nlog⁡n)，效率较高。
是原地排序算法，空间复杂度低。

缺点：

是不稳定排序算法。
对缓存不友好，因为堆排序的访问模式是跳跃式的。

9. 适用场景

数据量较大。
对稳定性没有要求。
需要原地排序的场景。

10. 与其他排序算法的比较

特性	堆排序	快速排序	归并排序
时间复杂度	O(nlog⁡n)	O(nlog⁡n)	O(nlog⁡n)
空间复杂度	O(1)	O(log⁡n)	O(n)
稳定性	不稳定	不稳定	稳定
适用场景	数据量较大	数据量较大	数据量较大且需要稳定排序

八.归并排序

归并排序是一种分治算法，它将一个数组分成若干个子数组，分别对子数组进行排序，然后将排序好的子数组合并成一个有序的数组。以下是归并排序的详细解释和实现：

归并排序的基本思想

分治法：将数组分成两部分，分别对这两部分进行排序，最后将排序好的两部分合并。
递归：通过递归的方式将数组不断分割，直到每个子数组只有一个元素（单个元素是有序的）。
合并：将两个有序的子数组合并成一个有序数组。

归并排序的步骤

分割：将数组从中间分成两部分，递归地对左右两部分进行归并排序。
合并：将两个有序的子数组合并成一个有序数组。合并过程是归并排序的核心。

合并过程

假设有两个有序数组 left 和 right，我们需要将它们合并成一个有序数组 result：

初始化两个指针 i 和 j，分别指向 left 和 right 的第一个元素。
比较 left[i] 和 right[j]：
- 如果 left[i] < right[j]，将 left[i] 放入 result，并将 i 向右移动一位。
- 否则，将 right[j] 放入 result，并将 j 向右移动一位。
当一个数组的所有元素都被放入 result 后，将另一个数组的剩余部分直接追加到 result。

归并排序的时间复杂度

时间复杂度：O(n log n)，其中 n 是数组的长度。分割过程是 O(log n)，合并过程是 O(n)。
空间复杂度：O(n)，因为需要额外的空间来存储合并后的数组。

Python实现

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # 分割数组
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    # 合并两个有序数组
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    # 合并过程
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # 将剩余的元素追加到结果中
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

# 示例
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("排序后的数组:", sorted_arr)

归并排序的特点

稳定性：归并排序是一种稳定的排序算法，即相同元素的相对顺序在排序后不会改变。
适用性：适合处理大规模数据，尤其是链表排序。
缺点：需要额外的存储空间，空间复杂度较高。

九.基数排序

基数排序（Radix Sort）是一种非比较型的排序算法，它通过逐位处理数据，将数字或字符串按照每一位的值进行分桶和合并，从而实现排序。以下是关于基数排序的详细介绍：

基数排序的基本思想

基数排序的核心在于分桶和合并。它不依赖于元素之间的直接比较，而是通过元素的位权信息（如数字的个位、十位、百位等）进行排序。

基数排序有两种主要的实现方式：

最低有效位优先（LSD，Least Significant Digit）：从最低位（个位）开始排序，逐步向最高位（如百位、千位）进行。
最高有效位优先（MSD，Most Significant Digit）：从最高位开始排序，递归地对每个桶中的元素进行排序。

算法步骤（以LSD为例）

确定最大值的位数：找到数组中的最大值，确定需要处理的最大位数。
按位分桶排序：
- 从最低位（个位）开始，根据当前位的值将数组中的元素放入对应的桶中（0-9）。
- 按桶的顺序收集元素，形成新的序列。
- 逐步处理更高位，重复上述步骤，直到处理完最高位。

时间复杂度

基数排序的时间复杂度为 O(kn)，其中 n 是数组的长度，k 是最大值的位数。在整数排序中，如果位数相对固定，基数排序的时间复杂度接近线性时间 O(n)。

空间复杂度

基数排序需要额外的空间来存储桶，空间复杂度为 O(n + k)，其中 k 是基数（通常为10，对应十进制）。

稳定性

基数排序是一种稳定的排序算法。在每一轮排序中，相同位值的元素会保持原有的相对顺序。

Python实现

def radix_sort(arr):
    if not arr:
        return arr
    max_num = max(arr)  # 找到最大值
    exp = 1  # 初始位权（个位）
    while max_num // exp > 0:  # 直到处理完最高位
        buckets = [[] for _ in range(10)]  # 创建10个桶
        for num in arr:
            buckets[(num // exp) % 10].append(num)  # 按当前位放入桶
        arr = [num for bucket in buckets for num in bucket]  # 按桶顺序收集
        exp *= 10  # 提升位权
    return arr

应用场景

基数排序适用于以下场景：

整数排序：尤其是当整数的位数相对固定时。
字符串排序：可以将字符串的每个字符视为一个“位”。
大数据处理：由于其线性时间复杂度，在处理大规模数据时表现出色。

基数排序通过分桶和合并的方式，避免了传统比较排序的时间瓶颈，是一种高效且稳定的排序算法。

十.计数排序

计数排序（Counting Sort）是一种非比较型的排序算法，适用于一定范围内的整数排序。它的核心思想是利用一个额外的数组（计数数组）来统计每个整数出现的次数，从而实现快速排序。计数排序是一种非常高效的排序算法，尤其在数据范围较小时表现突出。

计数排序的基本思想

计数排序的核心在于**“计数”和“定位”**：

计数：统计每个整数出现的次数。
定位：根据计数结果，直接将每个整数放到它在排序后数组中的正确位置。

计数排序的关键在于它不依赖于元素之间的比较，而是通过“计数”来实现排序，因此它的效率非常高。

计数排序的步骤

假设有一个数组 arr，其中的整数范围为 [min_value, max_value]，计数排序的步骤如下：

确定范围：找到数组中的最小值 min_value 和最大值 max_value，确定整数的范围。
创建计数数组：创建一个大小为 range_size = max_value - min_value + 1 的计数数组 count，初始化为 0。
统计频率：遍历原数组 arr，对于每个元素 arr[i]，将其对应的计数数组位置 count[arr[i] - min_value] 加 1。
计算前缀和（可选）：如果需要稳定排序，需要对计数数组计算前缀和，以确定每个元素在排序后数组中的位置。
输出排序结果：根据计数数组，将元素按顺序放入结果数组中。

计数排序的稳定性

计数排序是一种稳定的排序算法。为了保持稳定性，需要从后向前填充结果数组。

时间复杂度

时间复杂度：O(n + k)，其中 n 是数组的长度，k 是整数范围（max_value - min_value）。当 k 不大时，计数排序非常高效。
空间复杂度：O(k)，需要额外的计数数组。

Python实现

def counting_sort(arr):
    if not arr:
        return []

    # 确定范围
    min_value = min(arr)
    max_value = max(arr)
    range_size = max_value - min_value + 1

    # 创建计数数组
    count = [0] * range_size

    # 统计频率
    for num in arr:
        count[num - min_value] += 1

    # 计算前缀和（可选，用于稳定排序）
    for i in range(1, range_size):
        count[i] += count[i - 1]

    # 输出排序结果
    output = [0] * len(arr)
    for num in reversed(arr):  # 从后向前填充，保证稳定性
        output[count[num - min_value] - 1] = num
        count[num - min_value] -= 1

    return output

# 示例
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print("排序后的数组:", sorted_arr)

应用场景

计数排序适用于以下场景：

整数排序：当整数范围较小（如 0 到 100）时，计数排序非常高效。
数据范围已知：如果数据范围已知且范围较小，计数排序是理想选择。
需要稳定排序：计数排序是一种稳定的排序算法，适合对稳定性有要求的场景。

注意事项

数据范围：如果整数范围非常大（如 1 到 10^9），计数排序的空间复杂度会很高，此时不适合使用。
非整数数据：计数排序主要用于整数排序。如果数据是非整数类型（如浮点数或字符串），需要转换为整数范围或使用其他排序算法。

计数排序通过“计数”而非“比较”来实现排序，是一种非常高效且稳定的排序算法，特别适合处理范围较小的整数数据。

十一.外部排序

外部排序是一种用于处理大规模数据的排序算法，当数据量太大而无法全部加载到内存时使用。它通过将数据分成小块，在内存中排序这些小块，然后将它们合并成一个有序的整体。以下是外部排序的基本步骤：

1. 分块排序

分块：将大数据集分成多个小块，每个块的大小适合内存处理。
排序：将每个块加载到内存中，使用内部排序算法（如快速排序、归并排序等）进行排序。
写回：将排序后的块写回外部存储（如磁盘）。

2. 归并排序

归并：将已排序的块逐步合并。通常使用多路归并，每次从多个块中选取最小的元素，合并成一个更大的有序块。
重复：直到所有块合并成一个完整的有序数据集。

3. 优化策略

多路归并：减少归并次数，提高效率。
缓冲区：使用缓冲区减少I/O操作，提升性能。
并行处理：利用多核或多机并行处理，加快排序速度。

应用场景

大数据处理：如数据库排序、数据仓库查询。
文件排序：如日志文件、大型文本文件排序。

示例代码（伪代码）

def external_sort(data, chunk_size):
    # 分块排序
    chunks = []
    for i in range(0, len(data), chunk_size):
        chunk = data[i:i + chunk_size]
        chunk.sort()
        chunks.append(chunk)
    
    # 归并排序
    sorted_data = merge_sorted_chunks(chunks)
    return sorted_data

def merge_sorted_chunks(chunks):
    # 多路归并
    import heapq
    return list(heapq.merge(*chunks))

总结

外部排序通过分块和归并处理大规模数据，适用于内存有限的情况。常用方法包括多路归并和缓冲区优化，广泛应用于大数据和文件处理场景。

十二.败者树

败者树（Loser Tree）是一种用于多路归并的高效数据结构，常用于外部排序中。它通过减少比较次数来提高归并效率，特别适合处理大规模数据。

基本概念

多路归并：将多个有序序列合并成一个有序序列。
败者树：一种完全二叉树，用于快速选出多个序列中的最小元素。

结构

叶子节点：存储各个归并序列的当前元素。
内部节点：存储“失败者”（即比较中较大的元素）。
根节点：不存储数据，仅用于比较。

操作步骤

初始化：
- 将每个序列的第一个元素放入叶子节点。
- 从叶子节点向上比较，败者（较大值）存入父节点，胜者（较小值）继续向上比较。
- 最终，根节点的胜者是最小元素。
调整：
- 取出最小元素后，从该元素所属序列中取出下一个元素，替换叶子节点中的值。
- 从该叶子节点向上调整，重新比较并更新败者树。

优点

减少比较次数：每次调整只需比较从叶子节点到根节点的路径，复杂度为 O(log⁡k)O(logk)，其中 kk 是归并路数。
高效：适合处理大规模数据，尤其在外部排序中表现优异。

应用场景

外部排序：多路归并时使用败者树提高效率。
优先级队列：需要快速获取最小元素的场景。

十三.置换选择排序

置换选择排序（Displacement Selection Sort）是一种基于堆的排序算法，主要用于生成初始归并段（也称为顺串）的排序方法。它是一种“内排序”和“外排序”相结合的算法，常用于外排序的初始阶段。以下是关于置换选择排序的详细介绍：

1. 基本原理

置换选择排序的核心思想是利用堆的性质来生成初始归并段。它通过不断从输入数据中选择最小（或最大）的元素，并将其放入输出序列中，同时调整剩余数据的堆结构，从而实现排序。

输入：一组无序的记录。
输出：若干个长度不等的初始归并段，每个归并段内部有序。

2. 算法步骤

假设输入数据为一个无序序列，输出为若干个有序的初始归并段：

（1）初始化

创建一个最小堆（或最大堆），堆的大小为 k（通常 k 是一个较小的常数）。
从输入数据中读取前 k 个记录，将它们构建成一个最小堆。

（2）生成初始归并段

循环条件：输入数据未读完或堆不为空。
循环体：
1. 取出堆顶元素：从堆中取出最小值（堆顶元素），并将其放入当前归并段。
2. 调整堆：从输入数据中读取下一个记录，将其插入堆中，并调整堆结构。
3. 判断归并段结束：如果新插入的记录与当前归并段的最后一个记录的排序关键字不满足有序关系，则当前归并段结束，开始生成下一个归并段。

（3）结束条件

当输入数据读完且堆为空时，排序结束。

3. 特点

优点：
- 生成的归并段长度不等：置换选择排序生成的归并段长度不固定，但通常比简单选择排序生成的归并段更长，从而减少了归并段的数量，提高了外排序的效率。
- 适合外排序：特别适合处理大规模数据，尤其是数据量超过内存容量时。
缺点：
- 实现复杂度较高：需要维护堆结构，并且需要判断归并段的结束条件。
- 对内存要求较高：需要额外的存储空间来维护堆。

4. 示例

假设输入数据为：[8, 5, 3, 9, 1, 7, 6, 2, 4]，堆大小 k = 3。

（1）初始化

读取前 3 个元素 [8, 5, 3]，构建最小堆：[3, 5, 8]。

（2）生成归并段

第一次循环：
- 取出堆顶元素 3，放入归并段 [3]。
- 读取下一个元素 9，插入堆中，调整堆为 [5, 9, 8]。
第二次循环：
- 取出堆顶元素 5，放入归并段 [3, 5]。
- 读取下一个元素 1，插入堆中，调整堆为 [1, 9, 8]。
第三次循环：
- 取出堆顶元素 1，放入归并段 [3, 5, 1]。
- 由于 1 不满足归并段的有序性，当前归并段结束，生成新的归并段。
后续步骤：
- 继续上述过程，直到输入数据读完且堆为空。

最终生成的初始归并段可能为：[3, 5], [1, 7, 6], [2, 4, 9]。

5. 应用场景

置换选择排序主要用于外排序的初始阶段，用于生成初始归并段。它特别适合处理大规模数据，尤其是数据量超过内存容量时，可以有效减少归并段的数量，提高排序效率。

如果你有更多问题，比如代码实现或具体应用，可以随时告诉我！

十四.最佳归并树

最佳归并树是一种用于优化外部排序中多路归并过程的树形结构，其目标是通过合理组织归并段，使整个归并过程的磁盘I/O次数最小化。

定义

最佳归并树类似于哈夫曼树，是一种带权路径长度最短的树结构。它将多个有序序列合并成一个有序序列，使得所有合并操作的总代价（通常是磁盘I/O次数）最小。在多路归并中，最佳归并树可以是二叉树或多叉树，具体取决于归并的路数。

构建方法

初始归并段的准备：通过内部排序将数据分成若干个有序的初始归并段。
构建归并树：
- 将初始归并段的长度作为叶子节点的权值。
- 每次选择权值最小的若干个节点进行归并，形成新的节点，并将新节点的权值设置为归并段长度之和。
- 重复上述过程，直到构建出完整的归并树。
处理虚段：
- 如果初始归并段的数量无法构成严格的k叉树，则需要补充长度为0的“虚段”，以确保树的结构满足最佳归并的要求。
- 补充虚段的数量计算公式为：k - (m - 1) % (k - 1) - 1，其中m为初始归并段的数量。

性质与特点

最小化I/O次数：最佳归并树通过优化归并段的组织方式，使得整个归并过程的总I/O次数最小。
灵活性：可以适应不同数量的初始归并段和不同的归并路数。
高效性：在构建过程中可以利用高效的算法和数据结构（如败者树）来加速归并过程。

应用场景

最佳归并树广泛应用于外部排序，特别是在处理大规模数据时。它常用于大数据处理、数据库管理系统和文件系统等领域，用于优化多路归并过程。

例如，对于9个初始归并段，其长度分别为2, 3, 6, 9, 12, 17, 18, 24, 30，通过构建最佳归并树，其对外存的读写次数为446次。

数据结构（第八章 排序算法）

一.直接插入排序

1. 算法思想

2. 算法步骤

3. 代码实现

C++ 实现

Python 实现

4. 示例

5. 时间复杂度

6. 空间复杂度

7. 稳定性

8. 优缺点

优点：

缺点：

9. 适用场景

10. 优化

10.1 二分插入排序

代码实现：

二.折半插入排序

1. 算法思想

2. 算法步骤

3. 代码实现

C++ 实现

Python 实现

4. 示例

5. 时间复杂度

6. 空间复杂度

7. 稳定性

8. 优缺点

优点：

缺点：

9. 适用场景

10. 与直接插入排序的比较

三.希尔排序

1. 算法思想

2. 算法步骤

3. 代码实现

C++ 实现

Python 实现

4. 示例

5. 时间复杂度

6. 空间复杂度

7. 稳定性

8. 优缺点

优点：

缺点：

9. 增量序列的选择

10. 适用场景

11. 与插入排序的比较

四.冒泡排序

算法步骤

时间复杂度

空间复杂度

代码实现（Python）

示例运行结果

优化

适用场景

五.快速排序

算法步骤

时间复杂度

空间复杂度

代码实现（Python）

示例运行结果

优化

适用场景

六.简单选择排序

算法步骤

时间复杂度

空间复杂度

代码实现（Python）

示例运行结果

特点

适用场景

七.堆堆排

1. 算法思想

2. 算法步骤

3. 代码实现

C++ 实现

Python 实现

4. 示例

数据结构（第八章排序算法）