排序学习整理（3）

前情提要

排序学习整理（1）-CSDN博客

排序学习整理（2）-CSDN博客

2.4 归并排序

归并排序(Merge Sort)是一种分治法思想的典型应用。它将待排序的数组分成若干子序列，每个子序列分别排序后，再将其合并成一个整体有序的序列。归并排序是一种稳定排序算法，时间复杂度为 O(n log⁡n)。

 核心步骤就像这样

 分到叶子之后，开始两两排序归并到一起

基本思想

1. 分解：将待排序序列分成两个子序列，递归对子序列继续分解，直到子序列长度为 1。
2. 合并：将两个已经排好序的子序列合并成一个有序序列。

算法步骤

1. 将数组从中间分成两部分，分别对这两部分进行归并排序。
2. 递归完成后，利用辅助空间将两个已排序的子序列合并成一个有序序列。
3. 重复上述过程，直到整个数组有序。

代码实现

递归版归并排序

#include <stdio.h>
#include <stdlib.h>// 合并两个有序子数组
void Merge(int* a, int left, int mid, int right, int* tmp) {int i = left;      // 左子数组起点int j = mid + 1;   // 右子数组起点int k = 0;         // 临时数组索引// 合并两个有序数组while (i <= mid && j <= right) {if (a[i] <= a[j]) {tmp[k++] = a[i++];} else {tmp[k++] = a[j++];}}// 如果左子数组有剩余，直接拷贝while (i <= mid) {tmp[k++] = a[i++];}// 如果右子数组有剩余，直接拷贝while (j <= right) {tmp[k++] = a[j++];}// 将临时数组中的元素拷贝回原数组for (i = 0; i < k; ++i) {a[left + i] = tmp[i];}
}// 归并排序主函数
void MergeSort(int* a, int left, int right, int* tmp) {if (left < right) {int mid = left + (right - left) / 2;// 对左半部分排序MergeSort(a, left, mid, tmp);// 对右半部分排序MergeSort(a, mid + 1, right, tmp);// 合并两部分Merge(a, left, mid, right, tmp);}
}// 辅助函数
void MergeSortWrapper(int* a, int n) {int* tmp = (int*)malloc(n * sizeof(int));  // 分配辅助空间if (tmp == NULL) {perror("Memory allocation failed");return;}MergeSort(a, 0, n - 1, tmp);free(tmp);  // 释放辅助空间
}

无限取mid切成两条子树嘛，切到成叶子之后再轮流塞到tmp里排序，排好再拷贝回去，上面的动图应该蛮清楚了

当然，标了一个递归版就自然有非递归版

非递归版归并排序

void MergeSortIterative(int* a, int n) {int* tmp = (int*)malloc(n * sizeof(int));  // 辅助数组if (tmp == NULL) {perror("Memory allocation failed");return;}// 步长从 1 开始，逐渐加倍for (int step = 1; step < n; step *= 2) {for (int i = 0; i < n; i += 2 * step) {int left = i;int mid = (i + step - 1 < n) ? i + step - 1 : n - 1;int right = (i + 2 * step - 1 < n) ? i + 2 * step - 1 : n - 1;if (mid < right) {Merge(a, left, mid, right, tmp);  // 合并当前区间}}}free(tmp);  // 释放辅助空间
}

要记得把Merge函数加进去，与递归版的区别只在分割子树的方式不同罢了

特性总结

算法复杂度

1. 时间复杂度：
   • 最佳、最坏、平均时间复杂度均为 O(n log⁡n)，因为每次分解需要 O(log⁡n)次，而每次合并需要 O(n) 次。
2. 空间复杂度：
   • 递归版：需要 O(n)的辅助数组和 O(log⁡n) 的递归调用栈。
   • 非递归版：只需要 O(n)的辅助数组，递归调用栈占用为 0。
3. 稳定性：
   • 归并排序是稳定排序算法，因为在合并时不会改变相同元素的相对位置。

---

优缺点

优点：

1. 稳定性：归并排序是稳定的排序算法。
2. 性能稳定：无论输入数据如何分布，时间复杂度始终为 O(n log⁡n)，表现非常稳定。
3. 适用范围广：适合处理大规模数据，特别是数据存储在外部存储器中时，归并排序的外排序特性尤为突出。

缺点：

1. 空间开销大：需要 O(n)的辅助空间，递归实现还需要额外的栈空间。
2. 不适合小规模数据：对于小规模数据，归并排序的性能不如插入排序等简单算法。

---

适用场景

1. 大规模数据排序：归并排序性能稳定，适合排序大数据集。
2. 数据分布复杂的情况：即使数据完全无序，归并排序依然表现出色。
3. 外排序：当数据量大到无法全部加载到内存时，归并排序的分段排序和合并特性尤为适合。

 想测下这些排序效率的话

void TestOP(){srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int)*N);int* a2 = (int*)malloc(sizeof(int)*N);int* a3 = (int*)malloc(sizeof(int)*N);int* a4 = (int*)malloc(sizeof(int)*N);int* a5 = (int*)malloc(sizeof(int)*N);int* a6 = (int*)malloc(sizeof(int)*N);int* a7 = (int*)malloc(sizeof(int)*N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N-1);int end5 = clock();int begin6 = clock();MergeSort(a6, N);int end6 = clock();int begin7 = clock();BubbleSort(a7, N);int end7 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);printf("BubbleSort:%d\n", end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}

2.6 非比较排序

2.6.1 计数排序

计数排序（Counting Sort）是一种非比较排序算法，适用于范围较小的正整数或整数数组。它通过统计数组中每个元素的出现次数，将其直接放置到目标数组的正确位置，从而完成排序。

（也可以算一种特殊的桶排序）

基本思想

1. 找出数组中最大值和最小值，确定值的范围。
2. 使用一个计数数组统计每个值的出现次数。
3. 根据计数数组中的累积计数，确定每个值在排序后数组中的位置。
4. 按照计数数组的统计信息，将原数组的元素放入目标数组中，从而完成排序。

算法步骤

1. 确定范围：

   • 找出待排序数组的最大值和最小值，用于确定计数数组的大小。

2. 创建计数数组：

   • 使用一个计数数组 count，长度为 (最大值−最小值+1)(\text{最大值} - \text{最小值} + 1)(最大值−最小值+1)，记录每个值的出现次数。

3. 累积计数：

   • 对计数数组进行累积操作，count[i] 表示小于等于该值的元素个数。

4. 输出结果：

   • 从原数组逆序扫描，根据计数数组中的累积计数，将每个元素放置到目标数组的正确位置，并更新计数。

5. 覆盖原数组：

   • 将目标数组中的排序结果复制回原数组（如果需要）。

 当然，数值大的话就不要开一一与下标对应的空间了

#include <stdio.h>
#include <stdlib.h>// 计数排序函数
void CountingSort(int* a, int n) {if (n <= 1) return; // 数组长度不足时直接返回// 找到数组中的最大值和最小值int max = a[0], min = a[0];for (int i = 1; i < n; i++) {if (a[i] > max) max = a[i];if (a[i] < min) min = a[i];}// 创建计数数组并初始化int range = max - min + 1; // 元素范围int* count = (int*)calloc(range, sizeof(int));if (count == NULL) {perror("Memory allocation failed");return;}// 统计每个元素的出现次数for (int i = 0; i < n; i++) {count[a[i] - min]++;}// 累积计数，用于计算每个元素的最终位置for (int i = 1; i < range; i++) {count[i] += count[i - 1];}// 创建目标数组int* output = (int*)malloc(n * sizeof(int));if (output == NULL) {perror("Memory allocation failed");free(count);return;}// 倒序遍历原数组，将元素放置到正确位置for (int i = n - 1; i >= 0; i--) {int index = count[a[i] - min] - 1;output[index] = a[i];count[a[i] - min]--;}// 将排序结果写回到原数组for (int i = 0; i < n; i++) {a[i] = output[i];}// 释放内存free(count);free(output);
}int main() {int a[] = {4, 2, 2, 8, 3, 3, 1};int n = sizeof(a) / sizeof(a[0]);printf("Before sorting: ");for (int i = 0; i < n; i++) {printf("%d ", a[i]);}printf("\n");CountingSort(a, n);printf("After sorting: ");for (int i = 0; i < n; i++) {printf("%d ", a[i]);}printf("\n");return 0;
}

特性总结

算法复杂度

1. 时间复杂度：O(n + k)

2. 空间复杂度：O(n + k)

---

优点

1. 速度快：在数据范围较小且数据量较大时效率极高。
2. 稳定性：计数排序是稳定的排序算法。
3. 简单易实现：实现过程清晰明了。

---

缺点

1. 空间占用大：当数据范围（最大值减最小值）较大时，需要大量额外内存。
2. 只能处理整数或可离散化的数据：无法直接用于浮点数或其他复杂类型。

---

适用场景

1. 数据范围较小且集中：如考试成绩排序、年龄统计等。
2. 需要稳定性：在一些关键排序场景下，稳定性非常重要。
3. 输入为正整数或可轻松转换为整数：如字符编码排序等。

简而言之，在数据范围集中的情况下 ，计数排序可以达到O(n)级的效率，高快排一个指数级，但计数排序这也仅适用于数据范围集中的情况了。

剩下的两种都不太重要，大致介绍一下 

2.6.2 基数排序

基数排序(Radix Sort)是一种非比较排序算法，适用于整数或字符串等可分解为“位”的数据。它通过逐位排序，将输入数据按每一位（从低位到高位或从高位到低位）进行分组排序，从而完成整体排序。

基本思想

1. 将每个数字按照其位（如个位、十位、百位）进行逐位比较和排序。
2. 每一位排序时，利用稳定排序算法（如计数排序）保证排序后的顺序正确。
3. 多次排序后，整个数组将变得有序。

例如，对一组整数按个位、十位、百位依次排序，最终完成整体排序。

算法步骤

1. 确定最大位数： 找出数组中最大数的位数，决定排序的轮数。

2. 逐位排序：

   • 从最低位开始，对所有元素按当前位进行排序。
   • 利用计数排序等稳定排序方法，将元素按当前位的值分组排序。

3. 重复排序： 对所有位重复上述操作，直到排序到最高位。

4. 完成排序： 所有轮次排序后，数组即为有序。

 代码实现

#include <stdio.h>
#include <stdlib.h>// 获取数组中的最大值
int GetMax(int* a, int n) {int max = a[0];for (int i = 1; i < n; i++) {if (a[i] > max) {max = a[i];}}return max;
}// 对数组按照某个位数进行计数排序
void CountingSortForRadix(int* a, int n, int exp) {int* output = (int*)malloc(n * sizeof(int));int count[10] = {0}; // 因为是按位排序，只有 0-9 共 10 个数字// 统计每个位上的出现次数for (int i = 0; i < n; i++) {int digit = (a[i] / exp) % 10;count[digit]++;}// 计算累积计数for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 按当前位排序，将数据放入输出数组for (int i = n - 1; i >= 0; i--) {int digit = (a[i] / exp) % 10;output[count[digit] - 1] = a[i];count[digit]--;}// 将排序结果复制回原数组for (int i = 0; i < n; i++) {a[i] = output[i];}free(output);
}// 基数排序主函数
void RadixSort(int* a, int n) {int max = GetMax(a, n); // 找到数组中最大值for (int exp = 1; max / exp > 0; exp *= 10) {CountingSortForRadix(a, n, exp);}
}// 测试函数
int main() {int a[] = {170, 45, 75, 90, 802, 24, 2, 66};int n = sizeof(a) / sizeof(a[0]);printf("Before sorting: ");for (int i = 0; i < n; i++) {printf("%d ", a[i]);}printf("\n");RadixSort(a, n);printf("After sorting: ");for (int i = 0; i < n; i++) {printf("%d ", a[i]);}printf("\n");return 0;
}

算法复杂度

时间复杂度：O(d*(n+k))，

• d：最大元素的位数。
• n：数组元素个数。
• k：计数排序中数字范围（通常为 10，即 0-9）。

空间复杂度：

                O(n + k)，需要额外的计数数组和临时存储数组。

要用它的地方基本都可以上更好的计数排序，已经没什么意义了

2.6.3 桶排序

说到没意义，这还有桶排序呢！

如果说基数排序、冒泡排序还有教学意义，桶排序是真的完全没作用了 

桶排序(Bucket Sort)是一种非比较排序算法，通过将元素分配到多个桶中，分别对每个桶内的元素进行排序，最后将所有桶的元素合并得到有序序列。适用于数据分布均匀、范围较小的场景。

基本思想

1. 将输入数据分配到一定数量的桶中，每个桶对应一个范围区间。
2. 对每个桶内部的数据进行排序（可以使用任何稳定的排序算法，如插入排序或快速排序）。
3. 按照桶的顺序依次合并所有桶中的数据，形成最终的有序数组。

算法步骤

确定范围和桶数：

                根据数组中的最大值和最小值，计算每个桶的范围。

                创建一个足够多的桶（通常使用数组或链表作为桶）。

分配元素到桶：

                根据每个元素的值，计算其所属的桶索引，将其放入对应的桶中。

对桶内排序：

                每个桶内的数据进行排序，通常使用插入排序或其他适合小数据量的排序算法。

合并结果：

                按桶的顺序，将桶内的数据依次合并到输出数组。

 代码实现

#include <stdio.h>
#include <stdlib.h>// 定义桶的结构
typedef struct Bucket {int* data;   // 动态数组int count;   // 当前存储的元素个数int capacity; // 桶的容量
} Bucket;// 初始化桶
void InitBucket(Bucket* bucket) {bucket->capacity = 10; // 初始容量bucket->data = (int*)malloc(bucket->capacity * sizeof(int));bucket->count = 0;
}// 向桶中添加元素
void AddToBucket(Bucket* bucket, int value) {if (bucket->count == bucket->capacity) {bucket->capacity *= 2;bucket->data = (int*)realloc(bucket->data, bucket->capacity * sizeof(int));}bucket->data[bucket->count++] = value;
}// 桶内使用插入排序
void InsertionSort(int* arr, int n) {for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}// 桶排序函数
void BucketSort(int* arr, int n) {if (n <= 1) return;// 找到数组中的最大值和最小值int min = arr[0], max = arr[0];for (int i = 1; i < n; i++) {if (arr[i] < min) min = arr[i];if (arr[i] > max) max = arr[i];}int bucketCount = 10; // 默认分成10个桶int range = max - min + 1;int bucketRange = range / bucketCount + 1;// 初始化桶数组Bucket* buckets = (Bucket*)malloc(bucketCount * sizeof(Bucket));for (int i = 0; i < bucketCount; i++) {InitBucket(&buckets[i]);}// 将数据分配到桶中for (int i = 0; i < n; i++) {int bucketIndex = (arr[i] - min) / bucketRange;AddToBucket(&buckets[bucketIndex], arr[i]);}// 对每个桶中的数据排序并合并结果int index = 0;for (int i = 0; i < bucketCount; i++) {if (buckets[i].count > 0) {InsertionSort(buckets[i].data, buckets[i].count);for (int j = 0; j < buckets[i].count; j++) {arr[index++] = buckets[i].data[j];}}free(buckets[i].data);}// 释放桶数组free(buckets);
}// 测试函数
int main() {int arr[] = {42, 32, 33, 52, 37, 47, 51, 30};int n = sizeof(arr) / sizeof(arr[0]);printf("Before sorting: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");BucketSort(arr, n);printf("After sorting: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

 本质就是把数据用链表挂在数组上再排序，占用内存多，适用范围小，还不好写！

• 时间复杂度：

  • 最好情况：O(n + k)，所有元素均匀分布到各桶中，每个桶内数据很少。
  • 最坏情况：O(n^2)，所有数据集中到一个桶中。
  • 平均情况：O(n + k)，其中 k 是桶的数量。

• 空间复杂度：

  • O(n + k)，需要额外的桶数组。

 3.排序算法复杂度及稳定性分析

最后的总结，不过不建议背。还是理解为上

稳定性是指：在待排序的记录序列中，若存在多个具有相同关键字的记录，在排序后，这些记录的相对次序保持不变，即在原序列中，若 r[i]=r[j]r[i] = r[j] 且 r[i]r[i] 在 r[j]r[j] 之前，那么排序后 r[i]r[i] 仍然在 r[j]r[j] 之前，则这种排序算法被称为稳定的；反之，若排序后次序发生改变，则称为不稳定的。

就这样了，谢谢能看到这里啦