网站收录在下降泰安专业网页设计培训

网站收录在下降,泰安专业网页设计培训,wordpress百度收录数,国内产品网站目录 1、排序 1.1.概念 1.2.常见排序算法 VS2026Debug模式下各排序算法排序100000各数据所需时间#xff08;单位毫秒#xff09; 2、常见排序算法的实现 2.1.插入排序 2.1.1基本思想 2.1.2直接插入排序 直接插入排序的特性 直接插入排序的C语言实现 2.1.3希尔排序…目录1、排序1.1.概念1.2.常见排序算法VS2026Debug模式下各排序算法排序100000各数据所需时间单位毫秒2、常见排序算法的实现2.1.插入排序2.1.1基本思想2.1.2直接插入排序直接插入排序的特性直接插入排序的C语言实现2.1.3希尔排序缩小增量排序希尔排序的基本思想希尔排序的特性希尔排序的C语言代码2.2选择排序2.2.1基本思想2.2.2直接选择排序直接选择排序的特性直接选择排序的C语言代码2.2.3堆排序【数据结构】堆的原理与C语言实现-CSDN博客堆排序的特性堆排序的C语言代码2.3交换排序2.3.1基本思想2.3.2冒泡排序冒泡排序的特性冒泡排序的C语言代码2.3.3快速排序快速排序有两种优化方法快速排序递归代码快速排序非递归2.4归并排序基本思想归并排序的特性归并排序C语言代码3.排序算法复杂度及稳定性分析1、排序1.1.概念排序使一串记录按照其中某个或某些关键字的大小递增或递减排列起来。稳定性在待排序的记录中存在多个具有相同关键字的记录若经过排序这些相同关键字的相对次序保持不变则称这种排序算法是稳定的否则称为不稳定的。内部排序数据元素全部放在内存中的排序。外部排序数据元素太多时不能同时放在内存中根据排序的过程不断在内外存之间移动数据的排序。1.2.常见排序算法插入排序直接插入排序、希尔排序选择排序选择排序、堆排序交换排序冒泡排序、快速排序归并排序归并排序VS2026Debug模式下各排序算法排序100000各数据所需时间单位毫秒2、常见排序算法的实现2.1.插入排序2.1.1基本思想直接插入排序是一种简单的插入排序法其基本思想把待排序的记录按其关键码的大小逐个插入到一个已经排序好的有序序列中直到所有数据插入完为止得到一个新的有序序列。类似于扑克牌2.1.2直接插入排序当插入第i(i1)个元素时前面的array[0],array[1]……array[i-1]个元素已经排好序此时将第i个元素与前面的array[[n-1],array[i-2]……依次比较找到插入位置将第i个元素插入原来位置的元素后移。直接插入排序的特性元素集合越接近有序直接插入排序算法的效率越高。时间复杂度O(N^2)空间复杂度O(1)稳定性稳定直接插入排序的C语言实现void InsertSort(int* a, int n) { for (int i 0; i n - 1; i) { int end i; // [0,end]是有序的end1位置的值插入到[0,end]中保持有序 int tmp a[end 1]; while (end 0) { if (tmp a[end]) { a[end 1] a[end]; --end; } else { break; } } a[end 1] tmp; } }2.1.3希尔排序缩小增量排序希尔排序法又称缩小增量法。希尔排序的基本思想先选定一个整数gap把待排序文件中的所有记录分为gap组所有距离为gap的记录分为同一组并对每一组分别进行排序。然后取更小的gap重复上述步骤直到gap1时所有记录在同一个组内排好序。希尔排序的特性希尔排序是对直接插入排序的优化当gap1时都是预排序目的是让数组更接近有序。希尔排序的时间复杂度不好计算因为gap的取值方式很多。可以认为希尔排序的时间复杂度大致为O(N^1.3)。稳定性不稳定希尔排序的C语言代码这里gap的取值方式为 gap / 3 1void ShellSort(int* a, int n) { int gap n; while (gap 1) { gap gap / 3 1; // 1可以保证最后一次gap一定是1 // gap1时是预排序gap1时是直接插入排序 for (int i 0; i n - gap; i) { int end i; int tmp a[end gap]; while (end 0) { if (tmp a[end]) { a[end gap] a[end]; end - gap; } else { break; } } a[end gap] tmp; } } }2.2选择排序2.2.1基本思想每次从待排序数据元素中取出最小或最大的一个元素存放在序列的起始位置直到全部排序完成。2.2.2直接选择排序在元素集合array[i]--array[n-1]中选择关键码最大或最小的元素若它不是这组数据的最后一个或第一个元素则将其与最后一个或第一个元素交换在剩余的array[i]--array[n-2]array[i1]--array[n-1]集合中重复上述步骤直到集合剩余1个元素直接选择排序的特性直接选择排序效率不是很高实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定直接选择排序的C语言代码void SelectSort(int* a, int n) { int begin 0, end n - 1; while (begin end) { int mini begin, maxi begin; for (int i begin 1; i end; i) { if (a[i] a[maxi]) { maxi i; } if (a[i] a[mini]) { mini i; } } Swap(a[begin], a[mini]); if (begin maxi) { maxi mini; } Swap(a[end], a[maxi]); begin; --end; } }2.2.3堆排序堆排序是指利用堆这种数据结构设计的排序算法它是选择排序的一种通过堆来进行选择数据。注意排升序要建大堆排降序要建小堆堆的详细介绍可以看这篇文章【数据结构】堆的原理与C语言实现-CSDN博客堆排序的特性时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定堆排序的C语言代码void AdjustDown(int* a, int n, int parent) { // 先假设左孩子小 int child parent * 2 1; while (child n) // child n说明孩子不存在调整到叶子了 { // 找出小的那个孩子 if (child 1 n a[child 1] a[child]) { child; } if (a[child] a[parent]) { Swap(a[child], a[parent]); parent child; child parent * 2 1; } else { break; } } } void HeapSort(int* a, int n) { // 向下调整建堆 O(N) for (int i (n - 1 - 1) / 2; i 0; i--) { AdjustDown(a, n, i); } // O(N*logN) int end n - 1; while (end 0) { Swap(a[0], a[end]); AdjustDown(a, end, 0); --end; } }2.3交换排序2.3.1基本思想交换 就是根据序列中两个记录的键值的比较结果来对换这两个记录在序列中的位置。交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动2.3.2冒泡排序冒泡排序的特性时间复杂度O(N^2)空间复杂度O(1)稳定性稳定冒泡排序的C语言代码void BubbleSort(int* a, int n) { for (int j 0; j n; j) { int flag 0; for (int i 1; i n - j; i) { if (a[i - 1] a[i]) { Swap(a[i - 1], a[i]); flag 1; } } if (flag 0) { break; } } }2.3.3快速排序快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元序列中某元素为基准值按照该排序码将待排序集合分割成两个子序列左子序列的值均小于基准值右子序列的值均大于基准值然后左右子序列重复该过程直到所有元素都排列在相应位置上为止。快速排序的特性时间复杂度O(N*logN)空间复杂度O(logN)稳定性不稳定快速排序有两种优化方法1三数取中法选基准值可以避免选择到最大值或最小值避免效率降低2递归到小的子区间时可以考虑使用插入排序快速排序递归代码int GetMidi(int* a, int left, int right) { int midi (left right) / 2; if (a[left] a[midi]) { if (a[midi] a[right]) { return midi; } else if (a[left] a[right]) { return right; } else { return left; } } else { // a[left] a[midi] if (a[midi] a[right]) { return midi; } else if (a[left] a[right]) { return left; } else { return right; } } } // hoare版本的单趟 int PartSort1(int* a, int left, int right) { // 三数取中 int midi GetMidi(a, left, right); Swap(a[midi], a[left]); int keyi left; int begin left, end right; while (begin end) { while (begin end a[end] a[keyi]) { --end; } while (begin end a[begin] a[keyi]) { begin; } Swap(a[begin], a[end]); return begin; } Swap(a[keyi], a[begin]); } // 前后指针法单趟 int PartSort2(int* a, int left, int right) { // 三数取中 int midi GetMidi(a, left, right); Swap(a[midi], a[left]); int keyi left; int prev left; int cur prev 1; // 继续 while (cur right) { if (a[cur] a[keyi] prev ! cur) { Swap(a[prev], a[cur]); } cur; } Swap(a[keyi], a[prev]); return prev; } void QuickSort(int* a, int left, int right) { if (left right) { return; } if (right - left 1 10) { InsertSort(a left, right - left 1); } else { //int keyi PartSort1(a, left, right); int keyi PartSort2(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi 1, right); } } // 在深度太深的情况下递归会有栈溢出的风险快速排序非递归快速排序的非递归实现使用栈或数组都可以循环每走一次取栈顶区间左右子区间入栈#includestack.h // 快速排序非递归 void QuickSortNonR(int* a, int left, int right) { ST st; STInit(st); STPush(st, right); STPush(st, left); // 栈不为空就继续栈为空就结束 // 循环每走一次相当于一次递归 while (!STEmpty(st)) { int begin STTop(st); STPop(st); int end STTop(st); STPop(st); int keyi PartSort2(a, begin, end); // [begin, keyi-1] keyi [keyi1, end] // 先入右再入左 if (keyi 1 end) { STPush(st, end); STPush(st, keyi 1); } if (begin keyi - 1) { STPush(st, keyi - 1); STPush(st, begin); } } STDestroy(st); }2.4归并排序基本思想归并排序是建立在归并操作上的一种有效的排序算法该算法采用的是分治法的一个非常经典的应用。将已有序的两个子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表 成为二路归并。归并排序的特性归并排序的缺点是需要O(N)的空间复杂度归并排序更多的是解决在磁盘的外排序问题时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定归并排序C语言代码// 归并排序 void _MergeSort(int* a, int* tmp, int begin, int end) { if (begin end) { return; } int mid (begin end) / 2; // [begin,mid] [mid1,end] 两个区间有序就可以进行归并 _MergeSort(a, tmp, begin, mid); _MergeSort(a, tmp, mid 1, end); // 归并 int begin1 begin, end1 mid; int begin2 mid 1, end2 end; int i begin; while (begin1end1 begin2end2) { if (a[begin1] a[begin2]) { tmp[i] a[begin1]; } else { tmp[i] a[begin2]; } } while (begin1 end1) { tmp[i] a[begin1]; } while (begin2 end2){ tmp[i] a[begin2]; } memcpy(a begin, tmp begin, (end - begin 1) * sizeof(int)); } void MergeSort(int* a, int n) { int* tmp (int*)malloc(sizeof(int) * n); if (tmp NULL) { perror(malloc fail); return; } _MergeSort(a, tmp, 0, n - 1); free(tmp); tmp NULL; }3.排序算法复杂度及稳定性分析排序方式平均情况最好情况最坏情况辅助空间稳定性冒泡排序O(n^2)O(n)O(n^2)O(1)稳定简单选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定直接插入排序O(n^2)O(n)O(n^2)O(1)稳定希尔排序O(nlogn)~O(n^2)O(n^1.3)O(n^2)O(1)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定快速排序O(nlogn)O(nlogn)O(n^2)O(logn)~O(n)不稳定完