C/C++数据结构——剖析排序算法

1. 排序的概念及其运用

1.1 排序的概念

1.2常见的排序算法

2. 常见排序算法的解析与实现

2.1 插入排序

2.1.1 基本思想

2.1.2 直接插入排序

2.1.3 直接插入排序的实现

2.2 希尔排序

2.2.1 基本思想

2.2.2 希尔排序的实现

2.3 选择排序

2.3.1 基本思想

2.3.2 直接选择排序

2.3.3选择排序的实现

2.4 堆排序

2.4.1 基本思想

2.4.2 堆排序的实现

2.5冒泡排序

2.5.1 基本思想

2.5.2 冒泡排序的实现

2.6 快速排序

2.6.1 基本思想

2.6.2快速排序优化

2.6.3 快速排序的实现

C/C++库函数实现：

递归方式实现：

非递归方式实现（借助栈）：

2.7 归并排序

2.7.1 基本思想

2.7.2 归并排序的实现

递归方式实现：

非递归方式实现：

2.8 计数排序

2.8.1 基本思想

2.8.2 计数排序的实现

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

1. 排序的概念及其运用

1.1 排序的概念

https://en.wikipedia.org/wiki/Insertion_sorthttps://en.wikipedia.org/wiki/Insertion_sort

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2常见的排序算法

// 排序实现的接口// 插入排序void InsertSort(int* a, int n);// 希尔排序void ShellSort(int* a, int n);// 选择排序void SelectSort(int* a, int n);// 堆排序void AdjustDwon(int* a, int n, int root);void HeapSort(int* a, int n);// 冒泡排序void BubbleSort(int* a, int n);// 快速排序递归实现// 快速排序hoare版本int PartSort1(int* a, int left, int right);// 快速排序挖坑法int PartSort2(int* a, int left, int right);// 快速排序前后指针法int PartSort3(int* a, int left, int right);void QuickSort(int* a, int left, int right);// 快速排序 非递归实现void QuickSortNonR(int* a, int left, int right);// 归并排序递归实现void MergeSort(int* a, int n);// 归并排序非递归实现void MergeSortNonR(int* a, int n);// 计数排序void CountSort(int* a, int n);// 测试排序的性能对比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);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];}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();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);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);}

排序OJ(可使用各种排序跑这个OJ)力扣（LeetCode）官网 – 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。https://leetcode-cn.com/problems/sort-an-array/

2. 常见排序算法的解析与实现

2.1 插入排序

2.1.1 基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

实际中我们玩扑克牌时，就用了插入排序的思想

2.1.2 直接插入排序

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

2.1.3 直接插入排序的实现

// 定义一个插入排序函数void InsertSort(int* a,int n){// 遍历数组，从第一个元素到倒数第二个元素for (int i = 0; i = 0){if (temp < a[end]){a[end + 1] = a[end];end--;}else{break;}}// 将当前元素插入到合适的位置a[end + 1] = temp;}}

直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度: Worst : O(N^2) , Best : O(N)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

2.2 希尔排序

2.2.1 基本思想

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

2.2.2 希尔排序的实现

一组一组排：

void ShellSort(int* a, int n){int gap = n; // 初始化间隔为数组长度// 开始希尔排序while (gap > 1) // 当间隔大于1时进行排序{gap = gap / 3 + 1; // 根据规则更新间隔// 以下是希尔排序的核心算法for (int i = 0; i = 0){if (temp < a[end]) // 如果当前值小于前一个值，则交换位置{a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = temp; // 插入当前值到正确位置}}}

多组并排：

void ShellSort(int* a, int n){int gap = n; // 初始化间隔为数组长度// 开始希尔排序while (gap > 1) // 当间隔大于1时进行排序{gap = gap / 3 + 1; // 根据规则更新间隔// 以下是希尔排序的核心算法for (int j = 0; j < gap; j++) // 以间隔为步长进行插入排序{for (int i = j; i = 0){if (temp < a[end]) // 如果当前值小于前一个值，则交换位置{a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = temp; // 插入当前值到正确位置}}}}

希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：

《数据结构(C语言版)》— 严蔚敏

《数据结构-用面相对象方法与C++描述》— 殷人昆

https://en.wikipedia.org/wiki/Shellsorthttps://en.wikipedia.org/wiki/Shellsort4. 稳定性：不稳定

2.3 选择排序

2.3.1 基本思想

https://en.wikipedia.org/wiki/Selection_sorthttps://en.wikipedia.org/wiki/Selection_sort

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

2.3.2 直接选择排序

（1）在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素。
（2）若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个(第一个)元素交换。
（3）在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。

2.3.3选择排序的实现

void SelectSort(int* a, int n){int begin = 0;int end = n - 1;// 开始选择排序while (begin < end){int min = begin;int max = begin;// 找到当前范围内的最小值和最大值的索引for (int i = begin + 1; i <= end; i++){if (a[i]  a[max]){max = i;}}// 将最小值与当前范围的起始位置交换int temp1 = a[begin];a[begin] = a[min];a[min] = temp1;// 如果最大值的索引等于当前范围的起始位置，更新最大值的索引if (max == begin){max = min;}// 将最大值与当前范围的结束位置交换int temp2 = a[max];a[max] = a[end];a[end] = temp2;begin++;end--;}}

直接选择排序的特性总结：
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

2.4 堆排序

2.4.1 基本思想

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

https://en.wikipedia.org/wiki/Heapsorthttps://en.wikipedia.org/wiki/Heapsort

2.4.2 堆排序的实现

typedef int HeapDataType; // 定义堆数据类型为整型void Swap(int* x, int* y){int temp = *x;*x = *y;*y = temp;}// 向上调整建大堆void AdjustUp1(HeapDataType* a, int child){int parent = (child - 1) / 2; // 计算父节点索引while (child > 0){if (a[child] > a[parent]) // 如果子节点大于父节点{Swap(&a[child], &a[parent]); // 交换子节点和父节点的值child = parent; // 更新子节点索引parent = (parent - 1) / 2; // 更新父节点索引}else{break; // 如果子节点不大于父节点，则退出循环}}}// 向上调整建小堆void AdjustUp2(HeapDataType* a, int child){int parent = (child - 1) / 2; // 计算父节点索引while (child > 0){if (a[child] < a[parent]) // 如果子节点小于父节点{Swap(&a[child], &a[parent]); // 交换子节点和父节点的值child = parent; // 更新子节点索引parent = (parent - 1) / 2; // 更新父节点索引}else{break; // 如果子节点不小于父节点，则退出循环}}}// 大堆的向下调整void AdjustDown1(HeapDataType* a, int size, int parent){int child = parent * 2 + 1; // 计算左孩子节点索引while (child < size){if (child + 1 < size && a[child]  a[parent]) // 如果孩子节点大于父节点{Swap(&a[child], &a[parent]); // 交换孩子节点和父节点的值parent = child; // 更新父节点索引child = child * 2 + 1; // 更新孩子节点索引}else{break; // 如果孩子节点不大于父节点，则退出循环}}}// 小堆的向下调整void AdjustDown2(HeapDataType* a, int size, int parent){int child = parent * 2 + 1; // 计算左孩子节点索引while (child < size){if (child + 1  a[child + 1]) // 如果右孩子存在且小于左孩子{child++; // 右孩子节点索引加1，选择较小的孩子节点}if (a[child] = 0; i++) // 从最后一个非叶子节点开始向上调整建堆{AdjustDown1(a, n, i); // 向下调整建大堆}int end = n - 1; // 堆尾索引while (end > 0){Swap(&a[0], &a[end]); // 将堆顶元素与末尾元素交换AdjustDown1(a, end, 0); // 重新调整堆顶元素end--; // 缩小堆范围}#endif#if 0for (inti = 0; i  0){Swap(&a[0], &a[end]);AdjustDown2(a, end, 0);end--;}#endif}

堆排序的特性总结：
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

2.5冒泡排序

https://en.wikipedia.org/wiki/Bubble_sorthttps://en.wikipedia.org/wiki/Bubble_sort

2.5.1 基本思想

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.5.2 冒泡排序的实现

// 定义一个函数，用于交换两个整数指针指向的值void Swap(int* x, int* y){int temp = *x; // 用一个临时变量保存x指向的值*x = *y; // 将y指向的值赋给x指向的值*y = temp; // 将临时变量的值赋给y指向的值}// 定义一个函数，用于对整型数组进行冒泡排序void BubbleSort(int* a, int n){for (int i = 0; i < n; i++) // 外层循环控制比较的轮数{int flag = 1; // 设置一个标志位，用于判断是否已经完成排序for (int j = 0; j  a[j + 1]) // 如果前一个元素大于后一个元素{flag = 0; // 将标志位置为0，表示还未完成排序Swap(&a[j], &a[j + 1]); // 调用Swap函数交换两个元素的值}}if (flag) // 如果标志位仍为1，说明已经完成排序break; // 跳出循环，排序结束}}

冒泡排序的特性总结：
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定

2.6 快速排序

https://en.wikipedia.org/wiki/Quicksorthttps://en.wikipedia.org/wiki/Quicksort

2.6.1 基本思想

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

// 假设按照升序对array数组中[left, right)区间中的元素进行排序void QuickSort(int array[], int left, int right){if(right - left <= 1)return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int div = partion(array, left, right);// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)// 递归排[left, div)QuickSort(array, left, div);// 递归排[div+1, right)QuickSort(array, div+1, right);}

2.6.2快速排序优化

1. 三数取中法选key
2. 递归到小的子区间时，可以考虑使用插入排序

这里的partion（分区）方案我选的是三数取中：

int partion(int* a, int begin, int end){int mid = (begin + end) / 2;if (a[begin] < a[mid]){if (a[end]  a[mid])return mid;elsereturn end;}else{if (a[end]  a[begin])return begin;elsereturn end;}}

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

2.6.3 快速排序的实现

C/C++库函数实现：

qsort：

int compare(const void* a, const void* b){return (*(int*)a - *(int*)b);}int main(){int arr[] = { 3, 2, 6, 8, 4, 10, 0, 9, 5, 7, 1 };qsort(arr, sizeof(arr) / sizeof(arr[0]), sizeof(int), compare);for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++)printf("%d ", arr[i]);return 0;}

sort：

// 排序算法示例#include  // 标准输入/输出操作#include // std::sort 函数#include  // std::vector 容器// 比较两个整数以进行排序的函数bool myfunction(int i, int j) { return (i < j); }// 用于比较两个整数进行排序的仿函数结构体struct myclass {bool operator() (int i, int j) { return (i < j); }} myobject;int main() {int myints[] = { 32,71,12,45,26,80,53,33 };std::vector myvector(myints, myints + 8); // 使用myints中的值初始化向量// 使用默认比较函数（operator <）对前4个元素进行排序std::sort(myvector.begin(), myvector.begin() + 4); // 结果: (12 32 45 71) 26 80 53 33// 使用函数myfunction作为比较函数对剩余元素进行排序std::sort(myvector.begin() + 4, myvector.end(), myfunction); // 结果: 12 32 45 71 (26 33 53 80)// 使用对象myobject作为比较函数对整个向量进行排序std::sort(myvector.begin(), myvector.end(), myobject); // 结果: (12 26 32 33 45 53 71 80)// 打印向量的内容std::cout << "myvector contains:";for (std::vector::iterator it = myvector.begin(); it != myvector.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;}

递归方式实现：

1. hoare版本：

// 参数：// a: 指向待排序整数数组的指针// left: 数组最左边元素的索引// right: 数组最右边元素的索引// 返回值：// 分区后枢纽元素所在的索引int QuickSortPart1(int* a, int left, int right){// 找到枢纽元素并对数组进行分区int mid = partion(a, left, right); // 假设partion函数在其他地方定义// 将枢纽元素与最左边元素交换位置Swap(&a[left], &a[mid]);// 初始化用于分区的变量int begin = left;int end = right;int key = begin;// 执行分区操作while (begin < end){// 将'end'指针向左移动，直到找到比枢纽元素小的元素while (begin = a[key])end--;// 将'begin'指针向右移动，直到找到比枢纽元素大的元素while (begin < end && a[begin] <= a[key])begin++;// 交换'begin'和'end'指针指向的元素Swap(&a[begin], &a[end]);}// 将枢纽元素放置到正确的位置Swap(&a[begin], &a[key]);return begin;}//一定注意是右边先走！！！

【注意】

为什么相遇位置比key要小？

2. 挖坑法版本：

// 参数：// a: 指向待排序整数数组的指针// left: 数组最左边元素的索引// right: 数组最右边元素的索引// 返回值：// 分区后枢纽元素所在的索引int QuickSortPart2(int* a, int left, int right){// 找到枢纽元素并对数组进行分区int mid = partion(a, left, right); // 假设partion函数在其他地方定义// 将枢纽元素与最左边元素交换位置Swap(&a[left], &a[mid]);// 保存枢纽元素的值int key = a[left];int hole = left;// 执行分区操作while (left < right){// 将'right'指针向左移动，直到找到比枢纽元素小的元素while (left = key)right--;// 将找到的元素放入之前枢纽元素的位置a[hole] = a[right];hole = right;// 将'left'指针向右移动，直到找到比枢纽元素大的元素while (left < right && a[left] <= key)left++;// 将找到的元素放入之前枢纽元素的位置a[hole] = a[left];hole = left;}// 将枢纽元素放置到正确的位置a[hole] = key;return hole;}

3. 前后指针版本：

// 参数：// a: 指向待排序整数数组的指针// left: 数组最左边元素的索引// right: 数组最右边元素的索引// 返回值：// 分区后枢纽元素所在的索引int QuickSortPart3(int* a, int left, int right){// 找到枢纽元素并对数组进行分区int mid = partion(a, left, right); // 假设partion函数在其他地方定义// 将枢纽元素与最左边元素交换位置Swap(&a[left], &a[mid]);// 初始化前后指针int prev = left;int cur = prev + 1;int key = left;// 执行分区操作while (cur <= right){// 如果当前元素小于枢纽元素，则交换当前元素和前指针指向的元素if (a[cur] < a[key]){prev++;Swap(&a[prev], &a[cur]);cur++;}else{cur++;}}// 将枢纽元素放置到正确的位置Swap(&a[prev], &a[key]);key = prev;return key;}

非递归方式实现（借助栈）：

// 参数：// a: 指向待排序结构体数组的指针// left: 数组最左边元素的索引// right: 数组最右边元素的索引// 返回值：// 分区后枢纽元素所在的索引int PartSort1(STDataType* a, int left, int right){// 找到枢纽元素并对数组进行分区int mid = GetMid(a, left, right);// 将枢纽元素与最左边元素交换位置Swap(&a[left], &a[mid]);// 初始化起始和结束指针int begin = left;int end = right;int key = begin;// 执行分区操作while (begin < end){// 将'end'指针向左移动，直到找到比枢纽元素小的元素while (begin = a[key])end--;// 将'begin'指针向右移动，直到找到比枢纽元素大的元素while (begin < end && a[begin] <= a[key])begin++;// 交换找到的元素的位置Swap(&a[begin], &a[end]);}// 将枢纽元素放置到正确的位置Swap(&a[key], &a[begin]);return begin;}// 参数：// a: 指向待排序结构体数组的指针// left: 数组最左边元素的索引// right: 数组最右边元素的索引void QuickSortNonR(STDataType* a, int left, int right){Stack st;StackInit(&st);StackPush(&st, right);StackPush(&st, left);// 非递归快速排序while (!StackEmpty(&st)){int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);int key = PartSort1(a, begin, end);// 将未排序部分压入栈中if (key + 1  begin){StackPush(&st, key - 1);StackPush(&st, begin);}}StackDestroy(&st);}

快速排序的特性总结：
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(logN)
4. 稳定性：不稳定

/** * @brief 归并排序算法的实现函数，使用递归的方式进行排序 ** @param a 待排序数组的指针 * @param begin 子数组的起始位置 * @param end 子数组的结束位置 * @param temp 临时数组用于存放排序结果 */void _MergeSort(int* a, int begin, int end, int* temp){if (begin >= end)return;// 计算中间位置int mid = (begin + end) / 2;// 递归调用_MergeSort对左右两个子数组进行排序_MergeSort(a, begin, mid, temp);_MergeSort(a, mid + 1, end, temp);// 合并两个有序子数组int begin1 = begin;int end1 = mid;int begin2 = mid + 1;int end2 = end;int i = begin; // i表示临时数组的下标while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){temp[i] = a[begin1];i++;begin1++;}else{temp[i] = a[begin2];i++;begin2++;}}// 处理剩余元素while (begin1 <= end1){temp[i] = a[begin1];i++;begin1++;}while (begin2 <= end2){temp[i] = a[begin2];i++;begin2++;}// 将排序后的结果拷贝回原数组memcpy(a + begin, temp + begin, sizeof(int) * ((end + 1) - begin));}/** * @brief 归并排序算法的入口函数，分配临时数组并调用_MergeSort函数 ** @param a 待排序数组的指针 * @param n 数组的大小 */void MergeSort(int* a, int n){// 分配临时数组int* temp = (int*)malloc(sizeof(int) * n);if (temp == NULL){perror("malloc fail");return;}// 调用_MergeSort函数对整个数组进行排序_MergeSort(a, 0, n - 1, temp);// 释放临时数组内存free(temp);}*/

非递归方式实现：

// 这个函数以迭代方式实现归并排序算法，而不使用递归// 参数：// a：要排序的整数数组// n：数组中元素的数量// 返回值：voidvoid MergeSortNonR(int* a, int n){// 分配内存用于临时数组以存储排序后的元素int* temp = (int*)malloc(sizeof(int) * n);// 检查内存分配是否成功if (temp == NULL){printf("malloc失败");return;}// 初始化要比较的元素之间的间隔int gap = 1;// 循环直到间隔小于元素数量while (gap < n){// 以当前间隔大小的增量遍历数组for (int i = 0; i = n || begin2 >= n){break;}// 如果结束边界超过数组大小，则调整它if (end2 >= n){end2 = n - 1;}// 打印正在合并的子数组的边界 // printf("[%2d,%2d][%2d,%2d]\n", begin1, end1, begin2, end2);int j = begin1;// 按顺序合并两个子数组while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){temp[j] = a[begin1];j++;begin1++;}else{temp[j] = a[begin2];j++;begin2++;}}while (begin1 <= end1){temp[j] = a[begin1];j++;begin1++;}while (begin2 <= end2){temp[j] = a[begin2];j++;begin2++;}memcpy(a + i, temp + i, sizeof(int) * ((end2 - i) + 1));}gap *= 2;}}

归并排序的特性总结：
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定

// 参数：// a：要排序的整数数组// n：数组中元素的数量// 返回值：voidvoid CountSort(int* a, int n){// 寻找数组中的最小值和最大值int min = a[0];int max = a[0];for (int i = 1; i < n; i++){if (a[i] = max){max = a[i];}}// 计算数值范围int range = max - min + 1;// 分配内存用于计数数组int* count = (int*)calloc(range, sizeof(int));// 检查内存分配是否成功if (count == NULL){printf("calloc失败");return;}// 统计每个元素出现的次数for (int i = 0; i < n; i++){count[a[i] - min]++;}// 将排序后的元素放回原数组int i = 0;for (int j = 0; j < range; j++){while (count[j]--){a[i++] = j + min;}}}

计数排序的特性总结：

1. 时间复杂度：O(N+k), 其中N为数组的长度，k为哈希表的长度
2. 空间复杂度：O(N+k), 需要用到一个哈希表和一个额外数组
3. 稳定性：稳定

C/C++数据结构——剖析排序算法

1. 排序的概念及其运用

1.1 排序的概念

1.2常见的排序算法

2. 常见排序算法的解析与实现

2.1 插入排序

2.1.1 基本思想

2.1.2 直接插入排序

2.1.3 直接插入排序的实现

2.2 希尔排序

2.2.1 基本思想

2.2.2 希尔排序的实现

2.3 选择排序

2.3.1 基本思想

2.3.2 直接选择排序

2.3.3选择排序的实现

最新关注

热文推荐