合肥做检查军大网站,钙网logo免费设计在线生成,wordpress 军事主题,建设旅游网站的意义1. 排序的概念及其运用 1.1 排序的概念
https://en.wikipedia.org/wiki/Insertion_sorthttps://en.wikipedia.org/wiki/Insertion_sort
排序#xff1a;所谓排序#xff0c;就是使一串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起来的… 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(i1)个元素时前面的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 n-1; i){// 定义当前元素的位置int end i;// 保存当前元素的值int temp a[end 1];// 循环向前比较直到找到合适的位置插入当前元素while (end 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 n - gap; i) // 以间隔为步长进行插入排序{int end i;int temp a[end gap]; // 保存当前位置的值while (end 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 n - gap; i gap){int end i;int temp a[end gap]; // 保存当前位置的值while (end 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/Shellsort 4. 稳定性不稳定 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[i1]--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[min]){min 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[child 1]) // 如果右孩子存在且大于左孩子{child; // 右孩子节点索引加1选择较大的孩子节点}if (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 size a[child] a[child 1]) // 如果右孩子存在且小于左孩子{child; // 右孩子节点索引加1选择较小的孩子节点}if (a[child] a[parent]) // 如果孩子节点小于父节点{Swap(a[child], a[parent]); // 交换孩子节点和父节点的值parent child; // 更新父节点索引child child * 2 1; // 更新孩子节点索引}else{break; // 如果孩子节点不小于父节点则退出循环}}
}void HeapSort(HeapDataType* a, int n)
{
#if 1// 大堆排序for (int i ((n - 1) - 1) / 2; i 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 (int i 0; i n; i){AdjustUp2(a, i);}int end n - 1;while (end 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 n - 1 - i; j) // 内层循环进行相邻元素的比较和交换{if (a[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) 和 [div1, right)// 递归排[left, div)QuickSort(array, left, div);// 递归排[div1, right)QuickSort(array, div1, 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[begin])return begin;else if (a[end] a[mid])return mid;elsereturn end;}else{if (a[end] a[mid])return mid;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 iostream // 标准输入/输出操作
#include algorithm // std::sort 函数
#include vector // 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::vectorint 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::vectorint::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 end a[end] 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 right a[right] 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 end a[end] 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 end){StackPush(st, end);StackPush(st, key 1);}if (key - 1 begin){StackPush(st, key - 1);StackPush(st, begin);}}StackDestroy(st);
}快速排序的特性总结1. 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序2. 时间复杂度O(N*logN)
3. 空间复杂度O(logN)4. 稳定性不稳定
2.7 归并排序
https://en.wikipedia.org/wiki/Merge_sorthttps://en.wikipedia.org/wiki/Merge_sort
2.7.1 基本思想
归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide andConquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 2.7.2 归并排序的实现
递归方式实现
/*** 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; i (gap) * 2) {// 定义要合并的两个子数组的边界int begin1 i;int end1 i gap - 1;int begin2 i gap;int end2 i 2 * gap - 1;// 检查边界是否超过数组大小if (end1 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. 稳定性稳定
2.8 计数排序
https://en.wikipedia.org/wiki/Counting_sorthttps://en.wikipedia.org/wiki/Counting_sort
2.8.1 基本思想
计数排序是一种根据小正整数键对对象集合进行排序的算法。也就是说它是一种整数排序算法。它通过对拥有不同键值的对象数量进行计数并对这些计数应用前缀和来确定每个键值在输出序列中的位置来进行操作 2.8.2 计数排序的实现
// 参数
// a要排序的整数数组
// n数组中元素的数量
// 返回值void
void CountSort(int* a, int n)
{// 寻找数组中的最小值和最大值int min a[0];int max a[0];for (int i 1; i n; i){if (a[i] min){min a[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(Nk) , 其中N为数组的长度k为哈希表的长度2. 空间复杂度O(Nk), 需要用到一个哈希表和一个额外数组3. 稳定性稳定
3. 排序算法复杂度及稳定性分析
