C语言排序算法

概述

本文档详细介绍C语言中各种常见排序算法的实现和分析，包括冒泡排序、选择排序、插入排序、快速排序、归并排序，以及补充的希尔排序、堆排序等算法。每种排序算法都包含算法原理、实现代码、时间复杂度和空间复杂度分析，以及适当的示例代码。

排序算法的基本概念

排序算法的分类

分类标准 类型 说明 示例
时间复杂度 简单排序 O(n²) 冒泡排序、选择排序、插入排序
高级排序 O(nlogn) 快速排序、归并排序、堆排序
线性排序 O(n) 计数排序、桶排序、基数排序
排序稳定性 稳定排序 相等元素的相对顺序不变 冒泡排序、插入排序、归并排序
不稳定排序 相等元素的相对顺序可能改变 选择排序、快速排序、堆排序
排序方式 原地排序 不需要额外存储空间 冒泡排序、选择排序、插入排序、快速排序
非原地排序 需要额外存储空间 归并排序、计数排序、桶排序

排序算法的性能评估

排序算法的性能主要通过以下指标评估：

  • 时间复杂度：算法执行时间随输入规模增长的变化趋势
  • 空间复杂度：算法执行所需的额外存储空间
  • 稳定性：排序后相等元素的相对顺序是否保持不变
  • 适应性：算法对已部分排序数据的处理效率
  • 操作次数：比较次数和交换次数

辅助函数

打印数组

1
2
3
4
5
6
7
8
9
10
11
/**
 * @brief 打印数组
 * @param arr 要打印的数组
 * @param size 数组的大小
 */
void print_array(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

生成随机数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @brief 生成随机数组
 * @param arr 要生成的数组
 * @param size 数组的大小
 * @param min 随机数的最小值
 * @param max 随机数的最大值
 */
void generate_random_array(int arr[], int size, int min, int max) {
    // 初始化随机种子
    srand(time(NULL));
    
    for (int i = 0; i < size; i++) {
        // 生成[min, max]范围内的随机数
        arr[i] = min + rand() % (max - min + 1);
    }
}

复制数组

1
2
3
4
5
6
7
8
9
10
11
/**
 * @brief 复制数组
 * @param dest 目标数组
 * @param src 源数组
 * @param size 数组的大小
 */
void copy_array(int dest[], int src[], int size) {
    for (int i = 0; i < size; i++) {
        dest[i] = src[i];
    }
}

冒泡排序

算法原理

冒泡排序通过重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行直到没有再需要交换的元素为止，也就是说该数列已经排序完成。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @brief 冒泡排序
 * @param arr 要排序的数组
 * @param size 数组的大小
 * @details 冒泡排序通过重复地遍历要排序的数列，一次比较两个元素，
 *          如果它们的顺序错误就把它们交换过来。
 */
void bubble_sort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        // 标记本轮是否有交换，优化冒泡排序
        int swapped = 0;
        
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换arr[j]和arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        
        // 如果本轮没有交换，说明数组已经有序，提前退出
        if (swapped == 0) {
            break;
        }
    }
}

算法分析

  • 时间复杂度：
    • 最好情况：O(n)（已排序数组）
    • 平均情况：O(n²)
    • 最坏情况：O(n²)（逆序数组）
  • 空间复杂度：O(1)
  • 稳定性：稳定
  • 适应性：适应性强，对已部分排序的数据处理效率高

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 冒泡排序示例
void bubble_sort_example() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("冒泡排序示例：\n");
    printf("排序前：");
    print_array(arr, size);
    
    bubble_sort(arr, size);
    
    printf("排序后：");
    print_array(arr, size);
}

补充示例：双向冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 双向冒泡排序（鸡尾酒排序）
void cocktail_sort(int arr[], int size) {
    int left = 0, right = size - 1;
    int swapped = 1;
    
    while (left < right && swapped) {
        swapped = 0;
        
        // 从左到右，将最大元素移到右侧
        for (int i = left; i < right; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                swapped = 1;
            }
        }
        right--;
        
        // 从右到左，将最小元素移到左侧
        for (int i = right; i > left; i--) {
            if (arr[i] < arr[i - 1]) {
                int temp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = temp;
                swapped = 1;
            }
        }
        left++;
    }
}

// 双向冒泡排序示例
void cocktail_sort_example() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("双向冒泡排序示例：\n");
    printf("排序前：");
    print_array(arr, size);
    
    cocktail_sort(arr, size);
    
    printf("排序后：");
    print_array(arr, size);
}

选择排序

算法原理

选择排序的基本思想是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置；然后再从剩余的未排序元素中寻找到最小（或最大）元素，放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @brief 选择排序
 * @param arr 要排序的数组
 * @param size 数组的大小
 * @details 选择排序每次从待排序数组中找到最小（或最大）的元素，
 *          放到已排序数组的末尾。
 */
void selection_sort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        // 找到未排序部分的最小值索引
        int min_idx = i;
        for (int j = i + 1; j < size; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        
        // 交换找到的最小值和未排序部分的第一个元素
        if (min_idx != i) {
            int temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}

算法分析

  • 时间复杂度：
    • 最好情况：O(n²)
    • 平均情况：O(n²)
    • 最坏情况：O(n²)
  • 空间复杂度：O(1)
  • 稳定性：不稳定
  • 适应性：不适应，无论输入数据如何，时间复杂度都是O(n²)

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 选择排序示例
void selection_sort_example() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("选择排序示例：\n");
    printf("排序前：");
    print_array(arr, size);
    
    selection_sort(arr, size);
    
    printf("排序后：");
    print_array(arr, size);
}

补充示例：双向选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// 双向选择排序
void bidirectional_selection_sort(int arr[], int size) {
    int left = 0, right = size - 1;
    
    while (left < right) {
        int min_idx = left, max_idx = left;
        
        // 找出当前区间的最小值和最大值
        for (int i = left; i <= right; i++) {
            if (arr[i] < arr[min_idx]) {
                min_idx = i;
            }
            if (arr[i] > arr[max_idx]) {
                max_idx = i;
            }
        }
        
        // 将最小值交换到左侧
        if (min_idx != left) {
            int temp = arr[left];
            arr[left] = arr[min_idx];
            arr[min_idx] = temp;
            // 如果最大值是left，交换后最大值位置变为min_idx
            if (max_idx == left) {
                max_idx = min_idx;
            }
        }
        
        // 将最大值交换到右侧
        if (max_idx != right) {
            int temp = arr[right];
            arr[right] = arr[max_idx];
            arr[max_idx] = temp;
        }
        
        left++;
        right--;
    }
}

// 双向选择排序示例
void bidirectional_selection_sort_example() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("双向选择排序示例：\n");
    printf("排序前：");
    print_array(arr, size);
    
    bidirectional_selection_sort(arr, size);
    
    printf("排序后：");
    print_array(arr, size);
}

插入排序

算法原理

插入排序的基本思想是：将数组分为已排序部分和未排序部分，初始时已排序部分只包含第一个元素，然后依次将未排序部分的每个元素插入到已排序部分的适当位置，直到整个数组排序完成。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @brief 插入排序
 * @param arr 要排序的数组
 * @param size 数组的大小
 * @details 插入排序将数组分为已排序和未排序两部分，
 *          每次从未排序部分取一个元素插入到已排序部分的正确位置。
 */
void insertion_sort(int arr[], int size) {
    for (int i = 1; i < size; 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;
    }
}

算法分析

  • 时间复杂度：
    • 最好情况：O(n)（已排序数组）
    • 平均情况：O(n²)
    • 最坏情况：O(n²)（逆序数组）
  • 空间复杂度：O(1)
  • 稳定性：稳定
  • 适应性：适应性强，对已部分排序的数据处理效率高

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 插入排序示例
void insertion_sort_example() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("插入排序示例：\n");
    printf("排序前：");
    print_array(arr, size);
    
    insertion_sort(arr, size);
    
    printf("排序后：");
    print_array(arr, size);
}

补充示例：折半插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 折半插入排序
void binary_insertion_sort(int arr[], int size) {
    for (int i = 1; i < size; 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;
    }
}

// 折半插入排序示例
void binary_insertion_sort_example() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("折半插入排序示例：\n");
    printf("排序前：");
    print_array(arr, size);
    
    binary_insertion_sort(arr, size);
    
    printf("排序后：");
    print_array(arr, size);
}

快速排序

算法原理

快速排序的基本思想是：选择一个基准元素，将数组分为小于基准和大于基准的两部分，然后递归地对这两部分进行排序。快速排序是一种分治算法，通过一趟排序将数组分成两部分，然后分别对这两部分继续排序。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * @brief 快速排序
 * @param arr 要排序的数组
 * @param low 起始索引
 * @param high 结束索引
 * @details 快速排序通过选择一个基准元素，将数组分为小于基准和大于基准两部分，
 *          然后递归地对这两部分进行排序。
 */
void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        // 分区操作，获取基准元素的最终位置
        int pivot = arr[high]; // 选择最后一个元素作为基准
        int i = (low - 1);     // 小于基准的元素的索引
        
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                // 交换arr[i]和arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        
        // 交换基准元素到正确位置
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        
        int pi = i + 1; // 基准元素的最终位置
        
        // 递归排序基准元素左右两部分
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

算法分析

  • 时间复杂度：
    • 最好情况：O(nlogn)（每次分区都将数组均匀分成两部分）
    • 平均情况：O(nlogn)
    • 最坏情况：O(n²)（数组已排序或逆序，每次分区都将数组分成1和n-1两部分）
  • 空间复杂度：
    • 最好情况：O(logn)
    • 最坏情况：O(n)
  • 稳定性：不稳定
  • 适应性：不适应，对已排序数组的处理效率低

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 快速排序示例
void quick_sort_example() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("快速排序示例：\n");
    printf("排序前：");
    print_array(arr, size);
    
    quick_sort(arr, 0, size - 1);
    
    printf("排序后：");
    print_array(arr, size);
}

补充示例：三数取中法快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// 三数取中法选择基准
int median_of_three(int arr[], int low, int high) {
    int mid = low + (high - low) / 2;
    
    // 对三个数进行排序
    if (arr[low] > arr[mid]) {
        int temp = arr[low];
        arr[low] = arr[mid];
        arr[mid] = temp;
    }
    if (arr[low] > arr[high]) {
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }
    if (arr[mid] > arr[high]) {
        int temp = arr[mid];
        arr[mid] = arr[high];
        arr[high] = temp;
    }
    
    // 将中位数交换到high-1位置
    int temp = arr[mid];
    arr[mid] = arr[high - 1];
    arr[high - 1] = temp;
    
    return arr[high - 1];
}

// 三数取中法快速排序
void quick_sort_median(int arr[], int low, int high) {
    if (low + 3 <= high) {
        // 使用三数取中法选择基准
        int pivot = median_of_three(arr, low, high);
        int i = low, j = high - 1;
        
        while (1) {
            while (arr[++i] < pivot) {}
            while (arr[--j] > pivot) {}
            
            if (i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            } else {
                break;
            }
        }
        
        // 交换基准元素到正确位置
        int temp = arr[i];
        arr[i] = arr[high - 1];
        arr[high - 1] = temp;
        
        // 递归排序基准元素左右两部分
        quick_sort_median(arr, low, i - 1);
        quick_sort_median(arr, i + 1, high);
    } else {
        // 对小规模数组使用插入排序
        insertion_sort(arr + low, high - low + 1);
    }
}

// 三数取中法快速排序示例
void quick_sort_median_example() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("三数取中法快速排序示例：\n");
    printf("排序前：");
    print_array(arr, size);
    
    quick_sort_median(arr, 0, size - 1);
    
    printf("排序后：");
    print_array(arr, size);
}

归并排序

算法原理

归并排序的基本思想是：采用分治法，将数组分成两半，分别对两半进行排序，然后将排序好的两半合并成一个有序数组。归并排序是一种稳定的排序算法，需要额外的存储空间来存储合并过程中的临时数据。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/**
 * @brief 归并排序
 * @param arr 要排序的数组
 * @param left 左边界
 * @param right 右边界
 * @details 归并排序采用分治法，将数组分成两半，分别排序，然后合并。
 */
void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        // 计算中间位置
        int mid = left + (right - left) / 2;
        
        // 递归排序左半部分和右半部分
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        
        // 合并已排序的两部分
        merge(arr, left, mid, right);
    }
}

/**
 * @brief 归并排序的合并函数
 * @param arr 要合并的数组
 * @param left 左边界
 * @param mid 中间位置
 * @param right 右边界
 * @details 将两个已排序的子数组合并成一个有序数组。
 */
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    // 创建临时数组
    int L[n1], R[n2];
    
    // 复制数据到临时数组
    for (i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }
    
    // 合并临时数组
    i = 0;      // 左子数组的起始索引
    j = 0;      // 右子数组的起始索引
    k = left;   // 合并数组的起始索引
    
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    // 复制左子数组的剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    // 复制右子数组的剩余元素
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

算法分析

  • 时间复杂度：
    • 最好情况：O(nlogn)
    • 平均情况：O(nlogn)
    • 最坏情况：O(nlogn)
  • 空间复杂度：O(n)
  • 稳定性：稳定
  • 适应性：不适应，无论输入数据如何，时间复杂度都是O(nlogn)

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 归并排序示例
void merge_sort_example() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("归并排序示例：\n");
    printf("排序前：");
    print_array(arr, size);
    
    merge_sort(arr, 0, size - 1);
    
    printf("排序后：");
    print_array(arr, size);
}

补充示例：迭代归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 迭代归并排序
void iterative_merge_sort(int arr[], int size) {
    // 子数组长度从1开始，每次翻倍
    for (int curr_size = 1; curr_size < size; curr_size *= 2) {
        // 左子数组的起始位置
        for (int left_start = 0; left_start < size - 1; left_start += 2 * curr_size) {
            // 计算中间位置和右边界
            int mid = left_start + curr_size - 1;
            int right_end = left_start + 2 * curr_size - 1;
            if (right_end >= size) {
                right_end = size - 1;
            }
            
            // 合并两个子数组
            merge(arr, left_start, mid, right_end);
        }
    }
}

// 迭代归并排序示例
void iterative_merge_sort_example() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("迭代归并排序示例：\n");
    printf("排序前：");
    print_array(arr, size);
    
    iterative_merge_sort(arr, size);
    
    printf("排序后：");
    print_array(arr, size);
}

希尔排序

算法原理

希尔排序是插入排序的改进版，它通过将整个数组分割成若干子数组，对每个子数组进行插入排序，然后逐步减小分割间隔，最终完成整个数组的排序。希尔排序的核心思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 希尔排序
void shell_sort(int arr[], int size) {
    // 选择间隔序列，这里使用希尔建议的序列：n/2, n/4, ..., 1
    for (int gap = size / 2; gap > 0; gap /= 2) {
        // 对每个子数组进行插入排序
        for (int i = gap; i < size; i++) {
            int key = arr[i];
            int j = i;
            
            // 在子数组中插入key
            while (j >= gap && arr[j - gap] > key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            
            arr[j] = key;
        }
    }
}

算法分析

  • 时间复杂度：
    • 取决于间隔序列的选择，一般在O(n¹·³)到O(n²)之间
    • 最好情况：O(n)
    • 最坏情况：O(n²)
  • 空间复杂度：O(1)
  • 稳定性：不稳定
  • 适应性：适应性较强，对已部分排序的数据处理效率较高

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 希尔排序示例
void shell_sort_example() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("希尔排序示例：\n");
    printf("排序前：");
    print_array(arr, size);
    
    shell_sort(arr, size);
    
    printf("排序后：");
    print_array(arr, size);
}

补充示例：使用不同间隔序列的希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 使用Knuth间隔序列的希尔排序
void shell_sort_knuth(int arr[], int size) {
    // 计算最大间隔：1, 4, 13, 40, ...
    int gap = 1;
    while (gap < size / 3) {
        gap = 3 * gap + 1;
    }
    
    while (gap > 0) {
        for (int i = gap; i < size; i++) {
            int key = arr[i];
            int j = i;
            
            while (j >= gap && arr[j - gap] > key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            
            arr[j] = key;
        }
        
        // 减小间隔
        gap /= 3;
    }
}

// 使用Knuth间隔序列的希尔排序示例
void shell_sort_knuth_example() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("使用Knuth间隔序列的希尔排序示例：\n");
    printf("排序前：");
    print_array(arr, size);
    
    shell_sort_knuth(arr, size);
    
    printf("排序后：");
    print_array(arr, size);
}

堆排序

算法原理

堆排序是一种基于比较的排序算法，它利用堆这种数据结构来进行排序。堆是一个完全二叉树，分为最大堆和最小堆。在堆排序中，我们通常使用最大堆，即每个节点的值都大于或等于其子节点的值。堆排序的基本思想是：将待排序的数组构建成一个最大堆，然后将堆顶元素（最大值）与堆的最后一个元素交换，然后将剩余的元素重新构建成一个最大堆，重复这个过程，直到整个数组排序完成。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 堆排序
void heap_sort(int arr[], int size) {
    // 构建最大堆
    for (int i = size / 2 - 1; i >= 0; i--) {
        heapify(arr, size, i);
    }
    
    // 逐个从堆中取出元素
    for (int i = size - 1; i > 0; i--) {
        // 将堆顶元素（最大值）与末尾元素交换
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        
        // 对剩余的堆进行调整
        heapify(arr, i, 0);
    }
}

// 堆调整函数
void heapify(int arr[], int size, int root) {
    int largest = root;        // 初始化largest为根节点
    int left = 2 * root + 1;   // 左子节点
    int right = 2 * root + 2;  // 右子节点
    
    // 如果左子节点大于根节点
    if (left < size && arr[left] > arr[largest]) {
        largest = left;
    }
    
    // 如果右子节点大于当前最大值
    if (right < size && arr[right] > arr[largest]) {
        largest = right;
    }
    
    // 如果最大值不是根节点
    if (largest != root) {
        // 交换根节点和最大值
        int temp = arr[root];
        arr[root] = arr[largest];
        arr[largest] = temp;
        
        // 递归调整受影响的子树
        heapify(arr, size, largest);
    }
}

算法分析

  • 时间复杂度：
    • 最好情况：O(nlogn)
    • 平均情况：O(nlogn)
    • 最坏情况：O(nlogn)
  • 空间复杂度：O(1)
  • 稳定性：不稳定
  • 适应性：不适应，无论输入数据如何，时间复杂度都是O(nlogn)

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 堆排序示例
void heap_sort_example() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("堆排序示例：\n");
    printf("排序前：");
    print_array(arr, size);
    
    heap_sort(arr, size);
    
    printf("排序后：");
    print_array(arr, size);
}

补充示例：最小堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// 最小堆排序
void min_heap_sort(int arr[], int size) {
    // 构建最小堆
    for (int i = size / 2 - 1; i >= 0; i--) {
        min_heapify(arr, size, i);
    }
    
    // 逐个从堆中取出元素
    for (int i = size - 1; i > 0; i--) {
        // 将堆顶元素（最小值）与末尾元素交换
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        
        // 对剩余的堆进行调整
        min_heapify(arr, i, 0);
    }
}

// 最小堆调整函数
void min_heapify(int arr[], int size, int root) {
    int smallest = root;       // 初始化smallest为根节点
    int left = 2 * root + 1;   // 左子节点
    int right = 2 * root + 2;  // 右子节点
    
    // 如果左子节点小于根节点
    if (left < size && arr[left] < arr[smallest]) {
        smallest = left;
    }
    
    // 如果右子节点小于当前最小值
    if (right < size && arr[right] < arr[smallest]) {
        smallest = right;
    }
    
    // 如果最小值不是根节点
    if (smallest != root) {
        // 交换根节点和最小值
        int temp = arr[root];
        arr[root] = arr[smallest];
        arr[smallest] = temp;
        
        // 递归调整受影响的子树
        min_heapify(arr, size, smallest);
    }
}

// 最小堆排序示例
void min_heap_sort_example() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("最小堆排序示例：\n");
    printf("排序前：");
    print_array(arr, size);
    
    min_heap_sort(arr, size);
    
    printf("排序后：");
    print_array(arr, size);
}

排序算法的比较与选择

各排序算法的比较

排序算法 平均时间复杂度 最坏时间复杂度 空间复杂度 稳定性 适应性
冒泡排序 O(n²) O(n²) O(1) 稳定 适应
选择排序 O(n²) O(n²) O(1) 不稳定 不适应
插入排序 O(n²) O(n²) O(1) 稳定 适应
希尔排序 O(n¹·³) O(n²) O(1) 不稳定 适应
快速排序 O(nlogn) O(n²) O(logn) 不稳定 不适应
归并排序 O(nlogn) O(nlogn) O(n) 稳定 不适应
堆排序 O(nlogn) O(nlogn) O(1) 不稳定 不适应

排序算法的选择建议

  1. 小规模数据（n ≤ 50）：插入排序或选择排序
  2. 中等规模数据（50 < n ≤ 1000）：希尔排序
  3. 大规模数据（n > 1000）：快速排序、归并排序或堆排序
  4. 要求排序稳定：归并排序
  5. 要求原地排序：快速排序、堆排序
  6. 数据基本有序：插入排序或冒泡排序
  7. 数据分布均匀：快速排序
  8. 需要最坏情况保证：归并排序或堆排序

排序算法的应用示例

示例：学生成绩排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// 学生结构体
typedef struct {
    char name[50];
    int score;
} Student;

// 打印学生数组
void print_students(Student students[], int size) {
    for (int i = 0; i < size; i++) {
        printf("姓名：%s，成绩：%d\n", students[i].name, students[i].score);
    }
}

// 按成绩排序学生（使用快速排序）
void sort_students_by_score(Student students[], int low, int high) {
    if (low < high) {
        Student pivot = students[high];
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            if (students[j].score < pivot.score) {
                i++;
                Student temp = students[i];
                students[i] = students[j];
                students[j] = temp;
            }
        }
        
        Student temp = students[i + 1];
        students[i + 1] = students[high];
        students[high] = temp;
        
        int pi = i + 1;
        
        sort_students_by_score(students, low, pi - 1);
        sort_students_by_score(students, pi + 1, high);
    }
}

// 学生成绩排序示例
void student_sort_example() {
    Student students[] = {
        {"张三", 85},
        {"李四", 92},
        {"王五", 78},
        {"赵六", 95},
        {"钱七", 88}
    };
    int size = sizeof(students) / sizeof(students[0]);
    
    printf("学生成绩排序示例：\n");
    printf("排序前：\n");
    print_students(students, size);
    
    sort_students_by_score(students, 0, size - 1);
    
    printf("\n按成绩排序后：\n");
    print_students(students, size);
}

示例：字符串排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 字符串排序（使用冒泡排序）
void sort_strings(char *strings[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int swapped = 0;
        
        for (int j = 0; j < size - i - 1; j++) {
            if (strcmp(strings[j], strings[j + 1]) > 0) {
                char *temp = strings[j];
                strings[j] = strings[j + 1];
                strings[j + 1] = temp;
                swapped = 1;
            }
        }
        
        if (!swapped) {
            break;
        }
    }
}

// 字符串排序示例
void string_sort_example() {
    char *strings[] = {"banana", "apple", "orange", "grape", "pear"};
    int size = sizeof(strings) / sizeof(strings[0]);
    
    printf("字符串排序示例：\n");
    printf("排序前：\n");
    for (int i = 0; i < size; i++) {
        printf("%s ", strings[i]);
    }
    printf("\n");
    
    sort_strings(strings, size);
    
    printf("排序后：\n");
    for (int i = 0; i < size; i++) {
        printf("%s ", strings[i]);
    }
    printf("\n");
}

排序算法的优化策略

  1. 针对小规模数据：对于小规模数据（通常n < 100），使用插入排序等简单排序算法，因为它们的常数因子较小
  2. 混合排序算法：结合不同排序算法的优点，例如快速排序中对小规模子数组使用插入排序
  3. 利用已排序信息：对于部分有序的数据，使用适应性强的排序算法
  4. 选择合适的基准元素：在快速排序中使用三数取中法选择基准元素，避免最坏情况
  5. 避免不必要的交换：在冒泡排序和选择排序中，使用标记变量检测是否已排序
  6. 减少比较次数：在折半插入排序中使用二分查找减少比较次数
  7. 内存访问优化：考虑缓存局部性，优化内存访问模式
  8. 并行化：对于大规模数据，考虑使用并行排序算法

排序算法的性能测试

性能测试函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// 排序算法性能测试
void test_sort_performance() {
    int sizes[] = {1000, 5000, 10000, 50000};
    int num_sizes = sizeof(sizes) / sizeof(sizes[0]);
    
    for (int i = 0; i < num_sizes; i++) {
        int size = sizes[i];
        int *arr = (int *)malloc(size * sizeof(int));
        int *temp = (int *)malloc(size * sizeof(int));
        
        if (arr == NULL || temp == NULL) {
            printf("内存分配失败！\n");
            return;
        }
        
        // 生成随机数组
        generate_random_array(arr, size, 1, 100000);
        
        printf("\n测试数组大小：%d\n", size);
        
        // 测试冒泡排序
        copy_array(temp, arr, size);
        clock_t start = clock();
        bubble_sort(temp, size);
        clock_t end = clock();
        double bubble_time = (double)(end - start) / CLOCKS_PER_SEC;
        printf("冒泡排序：%.6f秒\n", bubble_time);
        
        // 测试选择排序
        copy_array(temp, arr, size);
        start = clock();
        selection_sort(temp, size);
        end = clock();
        double selection_time = (double)(end - start) / CLOCKS_PER_SEC;
        printf("选择排序：%.6f秒\n", selection_time);
        
        // 测试插入排序
        copy_array(temp, arr, size);
        start = clock();
        insertion_sort(temp, size);
        end = clock();
        double insertion_time = (double)(end - start) / CLOCKS_PER_SEC;
        printf("插入排序：%.6f秒\n", insertion_time);
        
        // 测试希尔排序
        copy_array(temp, arr, size);
        start = clock();
        shell_sort(temp, size);
        end = clock();
        double shell_time = (double)(end - start) / CLOCKS_PER_SEC;
        printf("希尔排序：%.6f秒\n", shell_time);
        
        // 测试快速排序
        copy_array(temp, arr, size);
        start = clock();
        quick_sort(temp, 0, size - 1);
        end = clock();
        double quick_time = (double)(end - start) / CLOCKS_PER_SEC;
        printf("快速排序：%.6f秒\n", quick_time);
        
        // 测试归并排序
        copy_array(temp, arr, size);
        start = clock();
        merge_sort(temp, 0, size - 1);
        end = clock();
        double merge_time = (double)(end - start) / CLOCKS_PER_SEC;
        printf("归并排序：%.6f秒\n", merge_time);
        
        // 测试堆排序
        copy_array(temp, arr, size);
        start = clock();
        heap_sort(temp, size);
        end = clock();
        double heap_time = (double)(end - start) / CLOCKS_PER_SEC;
        printf("堆排序：%.6f秒\n", heap_time);
        
        // 释放内存
        free(arr);
        free(temp);
    }
}

测试结果分析

排序算法的性能测试结果会受到多种因素的影响，包括：

  • 硬件环境：CPU速度、内存大小、缓存性能等
  • 数据特征：数据规模、数据分布、有序程度等
  • 实现细节：代码优化程度、编译器优化等

一般来说，对于大规模数据，高级排序算法（快速排序、归并排序、堆排序）的性能明显优于简单排序算法（冒泡排序、选择排序、插入排序）。在高级排序算法中，快速排序通常表现最好，但在最坏情况下性能会下降。归并排序的性能稳定，但需要额外的存储空间。堆排序不需要额外存储空间，但常数因子较大，实际性能可能不如快速排序。

总结

本文档详细介绍了C语言中各种常见排序算法的实现和分析，包括：

  1. 简单排序算法：冒泡排序、选择排序、插入排序
  2. 高级排序算法：快速排序、归并排序
  3. 补充排序算法：希尔排序、堆排序

每种排序算法都包含了算法原理、实现代码、时间复杂度和空间复杂度分析，以及适当的示例代码。此外，还介绍了排序算法的分类、性能评估、选择建议、优化策略和性能测试方法。

掌握这些排序算法对于理解算法设计的基本思想和解决实际问题都非常重要。在实际应用中，应根据具体情况选择合适的排序算法，以达到最佳的性能效果。

sorting.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/**
 * @brief 排序算法示例程序
 * @details 这个程序演示了C语言中各种常见的排序算法，包括
 *          冒泡排序、选择排序、插入排序、快速排序和归并排序，
 *          并提供了算法的时间复杂度分析和演示示例。
 * @return 0 表示程序成功执行
 */

// =========================
// 函数原型声明
// =========================
void print_array(int arr[], int size);         // 打印数组
void bubble_sort(int arr[], int size);         // 冒泡排序
void selection_sort(int arr[], int size);      // 选择排序
void insertion_sort(int arr[], int size);      // 插入排序
void quick_sort(int arr[], int low, int high); // 快速排序
void merge_sort(int arr[], int left, int right); // 归并排序
void merge(int arr[], int left, int mid, int right); // 归并排序的合并函数
void generate_random_array(int arr[], int size, int min, int max); // 生成随机数组
void copy_array(int dest[], int src[], int size); // 复制数组

/**
 * @brief 主函数
 * @return 0 表示程序成功执行
 */
int main() {
    // 测试数组
    int original[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(original) / sizeof(original[0]);
    int test_array[size];
    
    // 随机数组测试
    int random_size = 10;
    int random_array[random_size];
    generate_random_array(random_array, random_size, 1, 100);
    
    printf("=== 排序算法示例 ===\n\n");
    
    // =========================
    // 冒泡排序
    // =========================
    printf("=== 冒泡排序 ===\n");
    printf("时间复杂度: O(n^2)\n");
    printf("空间复杂度: O(1)\n");
    
    copy_array(test_array, original, size);
    printf("排序前: ");
    print_array(test_array, size);
    
    bubble_sort(test_array, size);
    
    printf("排序后: ");
    print_array(test_array, size);
    
    printf("\n");
    
    // =========================
    // 选择排序
    // =========================
    printf("=== 选择排序 ===\n");
    printf("时间复杂度: O(n^2)\n");
    printf("空间复杂度: O(1)\n");
    
    copy_array(test_array, original, size);
    printf("排序前: ");
    print_array(test_array, size);
    
    selection_sort(test_array, size);
    
    printf("排序后: ");
    print_array(test_array, size);
    
    printf("\n");
    
    // =========================
    // 插入排序
    // =========================
    printf("=== 插入排序 ===\n");
    printf("时间复杂度: O(n^2)\n");
    printf("空间复杂度: O(1)\n");
    
    copy_array(test_array, original, size);
    printf("排序前: ");
    print_array(test_array, size);
    
    insertion_sort(test_array, size);
    
    printf("排序后: ");
    print_array(test_array, size);
    
    printf("\n");
    
    // =========================
    // 快速排序
    // =========================
    printf("=== 快速排序 ===\n");
    printf("时间复杂度: O(nlogn) (平均), O(n^2) (最坏)\n");
    printf("空间复杂度: O(logn)\n");
    
    copy_array(test_array, original, size);
    printf("排序前: ");
    print_array(test_array, size);
    
    quick_sort(test_array, 0, size - 1);
    
    printf("排序后: ");
    print_array(test_array, size);
    
    printf("\n");
    
    // =========================
    // 归并排序
    // =========================
    printf("=== 归并排序 ===\n");
    printf("时间复杂度: O(nlogn)\n");
    printf("空间复杂度: O(n)\n");
    
    copy_array(test_array, original, size);
    printf("排序前: ");
    print_array(test_array, size);
    
    merge_sort(test_array, 0, size - 1);
    
    printf("排序后: ");
    print_array(test_array, size);
    
    printf("\n");
    
    // =========================
    // 随机数组测试
    // =========================
    printf("=== 随机数组测试 ===\n");
    printf("生成的随机数组: ");
    print_array(random_array, random_size);
    
    // 使用快速排序对随机数组进行排序
    int random_copy[random_size];
    copy_array(random_copy, random_array, random_size);
    quick_sort(random_copy, 0, random_size - 1);
    
    printf("快速排序后: ");
    print_array(random_copy, random_size);
    
    return 0;
}

/**
 * @brief 打印数组
 * @param arr 要打印的数组
 * @param size 数组的大小
 */
void print_array(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

/**
 * @brief 冒泡排序
 * @param arr 要排序的数组
 * @param size 数组的大小
 * @details 冒泡排序通过重复地遍历要排序的数列，一次比较两个元素，
 *          如果它们的顺序错误就把它们交换过来。
 */
void bubble_sort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        // 标记本轮是否有交换，优化冒泡排序
        int swapped = 0;
        
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换arr[j]和arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        
        // 如果本轮没有交换，说明数组已经有序，提前退出
        if (swapped == 0) {
            break;
        }
    }
}

/**
 * @brief 选择排序
 * @param arr 要排序的数组
 * @param size 数组的大小
 * @details 选择排序每次从待排序数组中找到最小（或最大）的元素，
 *          放到已排序数组的末尾。
 */
void selection_sort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        // 找到未排序部分的最小值索引
        int min_idx = i;
        for (int j = i + 1; j < size; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        
        // 交换找到的最小值和未排序部分的第一个元素
        if (min_idx != i) {
            int temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}

/**
 * @brief 插入排序
 * @param arr 要排序的数组
 * @param size 数组的大小
 * @details 插入排序将数组分为已排序和未排序两部分，
 *          每次从未排序部分取一个元素插入到已排序部分的正确位置。
 */
void insertion_sort(int arr[], int size) {
    for (int i = 1; i < size; 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;
    }
}

/**
 * @brief 快速排序
 * @param arr 要排序的数组
 * @param low 起始索引
 * @param high 结束索引
 * @details 快速排序通过选择一个基准元素，将数组分为小于基准和大于基准两部分，
 *          然后递归地对这两部分进行排序。
 */
void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        // 分区操作，获取基准元素的最终位置
        int pivot = arr[high]; // 选择最后一个元素作为基准
        int i = (low - 1);     // 小于基准的元素的索引
        
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                // 交换arr[i]和arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        
        // 交换基准元素到正确位置
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        
        int pi = i + 1; // 基准元素的最终位置
        
        // 递归排序基准元素左右两部分
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

/**
 * @brief 归并排序
 * @param arr 要排序的数组
 * @param left 左边界
 * @param right 右边界
 * @details 归并排序采用分治法，将数组分成两半，分别排序，然后合并。
 */
void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        // 计算中间位置
        int mid = left + (right - left) / 2;
        
        // 递归排序左半部分和右半部分
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        
        // 合并已排序的两部分
        merge(arr, left, mid, right);
    }
}

/**
 * @brief 归并排序的合并函数
 * @param arr 要合并的数组
 * @param left 左边界
 * @param mid 中间位置
 * @param right 右边界
 * @details 将两个已排序的子数组合并成一个有序数组。
 */
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    // 创建临时数组
    int L[n1], R[n2];
    
    // 复制数据到临时数组
    for (i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }
    
    // 合并临时数组
    i = 0;      // 左子数组的起始索引
    j = 0;      // 右子数组的起始索引
    k = left;   // 合并数组的起始索引
    
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    // 复制左子数组的剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    // 复制右子数组的剩余元素
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

/**
 * @brief 生成随机数组
 * @param arr 要生成的数组
 * @param size 数组的大小
 * @param min 随机数的最小值
 * @param max 随机数的最大值
 */
void generate_random_array(int arr[], int size, int min, int max) {
    // 初始化随机种子
    srand(time(NULL));
    
    for (int i = 0; i < size; i++) {
        // 生成[min, max]范围内的随机数
        arr[i] = min + rand() % (max - min + 1);
    }
}

/**
 * @brief 复制数组
 * @param dest 目标数组
 * @param src 源数组
 * @param size 数组的大小
 */
void copy_array(int dest[], int src[], int size) {
    for (int i = 0; i < size; i++) {
        dest[i] = src[i];
    }
}