哪个网站可以做h5页面,买网站名称,wordpress 标签页面,襄阳网站建设价格低-文章开头必看 1.#xff01;#xff01;#xff01;本文排序默认都是排升序 2.排序是否稳定值指指排完序之后相同数的相对位置是否改变 3.代码相关解释我都写在注释中了#xff0c;方便对照着看 1.插入排序1.1直接插入排序1.2希尔排序1.2.1单趟1.2.2多趟基础版——排完一…-文章开头必看 1.本文排序默认都是排升序 2.排序是否稳定值指指排完序之后相同数的相对位置是否改变 3.代码相关解释我都写在注释中了方便对照着看 1.插入排序1.1直接插入排序1.2希尔排序1.2.1单趟1.2.2多趟基础版——排完一组再排一组1.2.3多趟优化版——多组并排1.2.3完整版 2.选择排序2.1直接选择排序2.2.1单趟2.2.2多趟2.2.4完整版 2.2堆排序2.2.1向上调整建堆2.2.2向下调整建堆 3.交换排序3.1冒泡排序3.1.1基础版3.1.2优化版 3.2快速排序3.2.1hoare写法3.2.2挖坑法3.2.3双指针法3.2.4小区间优化3.2.5非递归写法 4 .归并排序4 .1归并排序4.1递归写法4.2非递归写法 5.非比较排序5.1计数排序 6.所有排序代码合集Sort.hSort.ctest.cStack.hStack.c 1.插入排序
1.1直接插入排序 插入排序是一种高效的简单排序算法它的工作原理是将一个未排序的元素插入到一个已排序的列表中并保持列表的有序性。对于已经部分有序的数组来说插入排序是非常高效的但是插入算法的时间复杂度为O(n^2)因此对于大型数组来说并不是理想的选择但只要有部分有序性能就会比冒泡好很多类似斗地主摸牌摸一张往前面已经排好的序列中插入 void InsertSort(int* a, int n)
{int end 0;for (int i 0; i n - 1; i){//单趟//0-end是已经排好序了的end i;int tmp a[end 1];//正在被插入被排序的值while (end 0){//如果该数比end处的数小if (tmp a[end]){//往后挪a[end 1] a[end];}//说明该数已经比end处大或者相等了else{break;}//每次控制完end要往前走一步end--;}//走到这有两种情况//①while循环结束了此时tmp最小放在第一个位置也就是end1//②else的break此时tmp a[end]可以把tmp放到end后面了a[end 1] tmp;}
}分析 时间复杂度最好情况数列已经有序下是O(n) 此时只是tmp位置由前往后同时仅仅只比较了一轮因此就是O(n)最坏情况数列逆序下O(n^2) 此时tmp位置在不断后移的同时每次都要前面有序的数列往后挪动因此是O(n^2)空间复杂度O(1)没有开辟辅助空间稳定性稳定 因此这个算法在排序的时候tmp是找到比自身大数使其后挪直到找到比自身小或者相等的数然后插入到这个数的后面因此相同的数的相对位置不会改变也就是说这个算法是稳定的 1.2希尔排序 希尔排序称为“缩小增量排序”是一种基于插入排序的改进算法。它的工作原理是将一个数组分为若干个子序列每个子序列的元素都是相隔某个增量h的距离然后对每个子序列进行插入排序将整个数组变成一个基本有序的数组。最后再对整个数组进行一次插入排序使得整个数组完全有序。希尔排序的时间复杂度为O(n^1.3)并且它的性能相对于直接插入排序有了很大的提升。但是希尔排序的时间复杂度会受到增量选择的影响如何选择合适的增量是希尔排序算法的关键之一。 1.2.1单趟 int gap 3;//间隔三个数为一组int end 0;for (int i 0; i n - gap; i gap)//i n - gap和a[end gap]的范围相呼应{end i;int tmp a[end gap];while (end 0){if (tmp a[end])//这里就类似插入排序{a[end gap] a[end];}else{break;}end end - gap;}a[end gap] tmp;}1.2.2多趟基础版——排完一组再排一组 int gap 3;for (int j 0; j gap; j)//走gap趟{for (int i j; i n - gap; i gap)//内层就是单趟了{int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];}else{break;}end end - gap;}a[end gap] tmp;}}1.2.3多趟优化版——多组并排 int gap 3;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];}else{break;}end end - gap;}a[end gap] tmp;}
1.2.3完整版
void ShellSort(int* a, int n)int gap n;//上面只是排完了一组现在要逐步减小gap的值使其能完整的排序while (gap 1)//gap等于1之后不能再进循环了再进循环除等之后就是0了{//gap / 2;//性能比/31稍差些//gap / 3;//尽量还是/2因为如果7个数第一次/3gap是2第二次就成0了gap gap / 3 1;//这样就可以保证最后一定是1了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];}else{break;}end end - gap;}a[end gap] tmp;}}
}希尔排序性能分析假设整个数组初始是逆序 ①刚开始gap很大的时候如n/3则有n/3组数据每组数据比较3次12合计 n/3 * 3 O(n) ②到中间过程时假设gap n/9,n/9组数据每组9个数据单租12…9 36合计36 * n/9 O(4n)但是在①的基础上已经调整部分顺序了不会是完全逆序所以实际性能会好于4n ③最后gap 1整个序列以及十分接近有序了因此也是O(n) 因此整个过程性能比较次数变化是先增加然后减少成向上箭头状时间复杂度最好O(n1.3),最坏O(n2)空间复杂度O(1)希尔排序是不稳定的 因为预排序的时候相同的数据可能分在不同的组中因为其相对位置就不敢保证不变了 希尔排序是对直接插入排序的优化 让较大的数据很快的跳到后面较小的数很快跳到前面。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。 2.选择排序
2.1直接选择排序 选择排序也是一种简单的排序算法它的工作原理是每次从未排序的部分中找到最小的元素并将其放在已排序部分的末尾。这个操作会一直持续到整个数组都已被排序。选择排序对于部分有序的数组比较有效。类似斗地主摸牌牌发完之后一起整理整理过程先选出最小的放在最前面然后选次小放在最小的右边然后第三小…该过程既然是在未排序的数列中遍历一遍找出最小的那我们还可以顺便找出最大的这样效率会更好一点 2.2.1单趟 int mini 0;int maxi 0;for (int i 1; i n; i){if (a[i] a[maxi]){a[maxi] a[i];}if (a[i] a[mini]){a[mini] a[i];}}a[0] a[mini];a[n - 1] a[maxi];2.2.2多趟 int begin 0;int end n - 1;while (begin end){int mini begin;int maxi begin;for (int i begin 1; i end; i){if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}//有问题//有可能maxi就是在begin的位置如果把begin交换走了maxi的位置也会变//Swap(a[begin], a[mini]);//Swap(a[end], a[maxi]);Swap(a[begin], a[mini]); if (maxi begin){//本来在begin位置的最大值换到mini位置了maxi mini;}Swap(a[end], a[maxi]);begin;--end;}2.2.4完整版
void SelectSort(int* a, int n)
{int begin 0;int end n - 1;while (begin end){int mini begin;int maxi begin;for (int i begin 1; i end; i){if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}//有问题//有可能maxi就是在begin的位置如果把begin交换走了maxi的位置也会变//Swap(a[begin], a[mini]);//Swap(a[end], a[maxi]);Swap(a[begin], a[mini]); if (maxi begin){//本来在begin位置的最大值换到mini位置了maxi mini;}Swap(a[end], a[maxi]);begin;--end;}
}-性能分析 时间复杂度O(n2) 遍历未排序的部分时间复杂度为O(n)。由于这个操作需要重复n次对于n个元素所以总的时间复杂度为O(n^2)空间复杂度O(1)不稳定 很多人可能会以为他是个稳定但是我举个例子你就知道了 3 3 1 2 2 1 先找到最小的是位于第三位的1因此要和第一位的3交换此时第一位的3换到第三位之后其和第二位的三的相对位置就反了 2.2堆排序 堆是一种特殊的数据结构它满足某些特定的性质。堆可以用于解决一些特定的问题如优先级队列、求最大值和最小值等。堆排序就是利用堆的这种特性来实现的。首先构建一个最大堆或最小堆然后将根节点与最后一个元素交换位置这样最大的元素就放在了正确的位置:然后调整根节点以下的子树为一个最大堆或最小堆;重复这个过程直到整个数组都已被排序 2.2.1向上调整建堆
//前提是前面的数是堆
//时间复杂度O(logN)
static AdjustUp(int* a, int child)//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 HeapSort(int* a, int n)
{//向上调整建堆//排升序建大堆//原因先建大堆选出最大的再与末尾交换size--然后再来一个向下调整即可时间复杂度为logN * N////建小堆选出最小的接下来从第二个开始向上调整建堆建堆时间复杂度就是logN * N//向上调整时间复杂度logN又因为这样做会把原有堆的规律打乱每个数都需要重新建堆//算上每次要选出最小的总计时间复杂度就是logN * N * N//建堆for (int i 0; i n; i){AdjustUp(a, i);}//排序int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}2.2.2向下调整建堆
//前提是左右子树都是大堆/小堆
//时间复杂度O(logN)
static AdjustDown(int* a, int n,int parent)
{int child parent * 2 1;while (child n){//选出左右子树中最大的if (child 1 n a[child] a[child 1])child;//比较if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}elsebreak;}
}//向下调整也可以建堆
//时间复杂度O(N)
//一些前提须知①该位置的左右子树必须是同类型的堆②一个节点既可以看作大堆也可以看作小堆
//运用递归的思想那我们要从最后一个节点的父节点开始向下调整即可
void HeapSort2(int* a, int n)
{//建堆int fa ((n - 1) - 1) / 2;while (fa 0){AdjustDown(a, n, fa);fa--;}//排序int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}性能分析 时间复杂度O(nlogN) 每次建堆是是O(logN)n个数就是O(nlogN)空间复杂度O(1)不稳定 这个很明显的建堆的过程能否保持相对顺序我就不说了就单单看建完堆之后堆顶要和最后一个数交换就能看出来这相对位置肯定会被破坏 3.交换排序
3.1冒泡排序 冒泡排序是最简单的排序算法之一它通过重复地比较相邻的两个元素如果它们的顺序错误就交换它们直到没有元素需要交换为止。这个过程就像泡泡逐渐向上升一样因此得名冒泡排序。虽然它的效率不高但是在一些简单的场景中还是有用的。主要用在教学场景中是个很不错的入门算法 3.1.1基础版
void BubbleSort(int* a, int n)
{for (int j 0; j n - 1; j){for (int i 0; i n - 1 - j; i)//每趟都能把当前最大的数排到后面因此下一趟这个数可以不参与了{if (a[i] a[i 1]){Swap(a[i], a[i 1]);}}}
}3.1.2优化版
void BubbleSort(int* a, int n)
{for (int j 0; j n - 1; j){int flat 1;//加个flat变量用于监控整趟下来数据是不是已经处于有序的状态了。你看此时如果flat是1如果下面整个循环下来if语句都没进去过说明此时数据大小关系都是前一个小于等于后一个也就是有序的flat也不会被改成0后面也不用再排序了直接break跳出就像for (int i 0; i n - 1 - j; i){if (a[i] a[i 1]){Swap(a[i], a[i 1]);flat 0;}}if (flat 1)break;}
}性能分析 时间复杂度最好情况顺序是O(n)最坏情况逆序是O(n^2) 空间复杂度O(1) 稳定的 3.2快速排序 快速排序是一种高效的排序算法采用分治策略。它的工作原理是将一个数组分成两个子数组然后将它们分别进行排序。这个过程可以通过递归和非递归实现最终得到一个有序的数组。 这里先解释一下快排为什么如果数组是有序时时间复杂度很差 因为快排主要思想就是递归而递归的层次和其每次递归区间的划分有关系如果数组是有序的话那么每次的key都是最小逆序时为最大同理的然后往下递归时每次都只有右子树那么整个二叉树的高度是n而不是常见的O(logN)导致总的时间复杂度不是O(nlogN)而是O(n^2) 3.2.1hoare写法 快速排序的基本思想是通过一趟排序将待排序的数据分割成两部分。其中一部分的所有数据都比另一部分的所有数据要小。这个过程被称为一次划分。 具体实现步骤如下: 1.首先从序列中任意选择一个元素把它作为枢轴。 2将小于等于枢轴的所有元素都移动到枢轴的左侧大于枢轴的元素则移动到枢轴的 右侧。 3.以枢轴为界划分出两个子序列左侧子序列所有元素都小于右侧子序列。 4.枢轴元素不属于任一子序列并且枢轴元素当前所在位置就是该元素在整个排序完成后的最终位置。 5重复上述步骤对左右两个子序列继续进行排序直到整个序列有序。 这就是快速排序的基本思路它由C.A.RHoare在1962年提出是对冒泡排序的一种改进。 //优化
//为了避免数组接近有序时性能很差
//我们在选key的时候采取三数取中的策略
//这个方法就是可以让每次找的key都相对来说是不大不小的int GetKey(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right])return mid;else if (a[left] a[right])//mid是最大值return right;elsereturn left;}else//left mid{if (a[mid] a[right])return mid;else if (a[right] a[left])//mid是最小的return left;elsereturn right;}}//写法一——hoare版本写起来很复杂void QuickSort(int* a, int left,int right)
{if (left right)return;int midi GetKey(a, left, right);Swap(a[left], a[midi]);int key left;int LeftMove left 1;int RightMove right;while (LeftMove RightMove){//前面这个条件就是为了避免没有满足条件的值的情况下RighrMove一直--while(LeftMove RightMove a[RightMove] a[key])//如果这里是的话在左右两边都碰到和key相等的情况下会死循环{RightMove--;}while (LeftMove RightMove a[LeftMove] a[key]){LeftMove;}Swap(a[LeftMove], a[RightMove]);}if(a[key] a[RightMove])Swap(a[key], a[RightMove]);//此时key已经在正确的位置了而key的左边都是比key小的key的右边都是比key大的因此再递归的去排左边和右边QuickSort(a, left, LeftMove - 1);QuickSort(a, LeftMove 1, right);
}相遇位置比key小怎么做到的 答案右边先走 分析 相遇情况① Right动Left不动去跟L相遇 相遇位置是L位置L和R在上一轮交换过因此此时L位置的值还是比Key小的 相遇情况② L动R不动去跟R相遇 R先走找到比key小的停下来这是L找大没找到一直往右走直到遇到R此时R位置的值也是比key小 3.2.2挖坑法 挖坑法的思路是改进于hoare的版本。首先将第一个数据存放在临时变量key中此时第一个位置就形成一个坑位。这个写法还是有LeftMove和RightMove干的活都是一样的但此时他们俩谁先走都OK了后续也和上一版一样 void QuickSort(int* a, int left, int right)
{if (left right)return;int midi GetKey(a, left, right);Swap(a[left], a[midi]);int key a[left];int LeftMove left;//这里最好不要写成left1因为这样在后续递归中如果子递归只有两个数其中一个是key且不进循环的时候//在填坑过程会很麻烦要么直接给hole复制但是这样另外一个地方值没有改变。要么Swap但是找不到hole地址了也是会出错//写成left后续子递归只有俩时也会正常判断直到只有一个值在最上头的if就return了int RightMove right;int hole left;while (LeftMove RightMove){while (LeftMove RightMove a[RightMove] key){RightMove--;}a[hole] a[RightMove];hole RightMove;while (LeftMove RightMove a[LeftMove] key){LeftMove;}a[hole] a[LeftMove];hole LeftMove;}a[hole] key;QuickSort(a, left, hole - 1);QuickSort(a, hole 1, right);
}3.2.3双指针法 本质是把一段大于key的区间往右推同时把小的换到左边 其他的都在代码中 void QuickSort(int* a, int left, int right)
{if (left right)return;int midi GetKey(a, left, right);Swap(a[left], a[midi]);int key left;//prev的情况有两种//在cur还没遇到比key大的值的时候prev紧跟着cur//遇到之后prev此时在比key大的这组数前面int prev left; int cur prev 1;//cur找比key小的找到之后prev然后交换prev和cur的值while (cur right){ //后面的意思是如果prev之后和cur在同一个位置那就不交换//并且只能写在后面prev只有在满足前面条件的情况下才需要if (a[cur] a[key] prev ! cur){Swap(a[prev], a[cur]);}cur;//不管哪种情况cur是一直往后走的}Swap(a[prev], a[key]);QuickSort(a, left, prev - 1);QuickSort(a, right 1, right);
} 3.2.4小区间优化 因为这个递归规程类似二叉树然而我们知道二叉树最下面一层约占二叉树节点数的50%倒数第二层25% 所以这个程序75%的消耗的花在最下面两层 所以我们可以改变一下到最下面几层递归的形式 希尔不适合×优势就是在于能让大的数快速的跳跃到后面不适合这种小区间的 直接插入适合√除非小区间完全逆序不然都只需要动几下 int SingleSort(int* a, int left, int right)
{int midi GetKey(a, left, right);Swap(a[left], a[midi]);int prev left;int cur prev 1;int keyi left;while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyi]);return prev;
}void QuickSort(int* a, int left, int right)
{if (left right)return;if ((right - left 1) 10)//如果区间差大于10就是大区间用递归。反之小区间就用插入排序{int keyi SingleSort(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);}else//优化之处{InsertSort(a left, right - left 1);}
}3.2.5非递归写法 快速排序的非递归写法主要利用栈来手动模拟递归调用首先从数组中选择一个数作为标准数。然后将所有比标准数小的数放在它的左边所有比标准数大的数放在它的右边。这样标准数就被放在它应该在的位置上不需要再移动。 接下来对标准数左右两边的数字重复上述操作具体步骤包括: 1.选择数组的最后一个元素作为标准数。 2.使用栈存储待处理的子数组的起始和结束索引。 3.当栈非空时取出栈顶的起始和结束索引执行快速排序的划分操作。 4.将划分后得到的子数组的起始和结束索引 压入栈中。这种方法避免了递归调用的开销提高了效率并且不会有递归深度过大导致的栈溢出风险(因为动态栈是开辟在堆上的堆的内存比栈多很多很多) void QuickSort_NonR(int* a, int begin, int end)
{ST st;STInit(st);STPush(st, end);STPush(st, begin);while (!STEmpty(st)){int left STTop(st);STPop(st);int right STTop(st);STPop(st);int key SingleSort(a, left, right);if (key 1 right){STPush(st, right);STPush(st, key 1);}if (left key - 1){STPush(st, key - 1);STPush(st, left);}}STDestroy(st);
}性能分析 正常随机数据下性能都是较好的 性能最好的时候每次的key都是中间值然后n个数二路递归参与递归的个数会减少高度是logn因此是O(logN) 性能最差的时候有序和接近有序的时候n个数每次key都是最小值或者最大值因此高度是n个数最开始是n然后n-1n-2因此是O(N^2)空间复杂度,这也依赖数组初始的顺序和时间复杂度一样,最好是O(logN)最差时是O(N) 不稳定的 4 .归并排序
4 .1归并排序 归并排序的主要思路是利用分治策略进行排序 具体地说它有三个主要的步骤: 1.分解 :首先将待排序的数列分成两个大致相等的子序列。这个过程会一直递归直到每个子序列只包含一个元素。 2.解决:然后对每个子序列执行归并排序。这一步也是递归的直到子序列可以被看作是已经排序好的。 3合并: 最后将两个已经排序好的子序列合并成一个排序好的序列 在实际操作中可以采用迭代法来实现归并排序。这包括申请足够大的空间来存储合并后的序列设定两个指针分别指向两个已排序序列的起始位置然后比较两个指针所指向的元素选择较小的元素放入到合并空间并移动指针到下一位置。这个过程会一直重复直到某一指针到达序列尾。 4.1递归写法
void Merger(int* a, int* tmp, int begin, int end)
{//递归————————————if (end begin)return;int mid (end begin) / 2;//类似二叉树的后序Merger(a, tmp, begin, mid);Merger(a, tmp, mid 1, end);//归并————————————int index begin;int begin1 begin;int end1 mid;int begin2 mid 1;int end2 end;//归并——找小while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[index] a[begin1];elsetmp[index] a[begin2];}while (begin1 end1)tmp[index] a[begin1];while (begin2 end2)tmp[index] a[begin2];//将tmp拷贝回a数组memcpy(a begin, tmp begin, sizeof(int) * (end - begin 1));
}void MergerSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc failed);exit(-1);}Merger(a, tmp, 0, n - 1);free(tmp);
}4.2非递归写法 用不了栈或队列 为什么快排可以因为快排是先序而归并是后序 先序的话区间入栈之后-排完-出栈但是归并是走到底才开始排 可能会说走到底再排也可以先把区间入进去呀 不可以因为后续的区间是根据前面区间排完结果而来的 那非递归的思路要来自斐波那契数列的非递归了。就是把递归倒过来走我们递归是把大化小那非递归就从小开始排然后不断扩大区间 void Merger_NonR(int* a, int n)
{//创建临时数组int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc failed);exit(-1);}//11归——22归——44归for (int gap 1; gap n; gap * 2){for (int i 0; i n; i 2 * gap)//每次往后跳两个区间{int begin1 i;int end1 i gap - 1;int begin2 i gap;int end2 i 2 * gap - 1;int index i;//数组个数不是2次幂避免越界的修正1//只有end1begin2end2会发生越界begin1不会因为begin1iin//begin2 n时end1 n-1begin2 n时end1 n。都是不用归并了因此break的情况//也就是归并的第二组不存在//为什么不用归并了因为在前面的小区间归并的时候已经是有序的了if (begin2 n){break;}if (end2 n){end2 n - 1;//修正end2的下标让最后一组在合理范围内归并//这里为什么还要归并//因为end2越界而前面没越界的时候前面一组和这一组的顺序还没排好啊虽然数量不对等但还要排序啊}//归并——找小while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[index] a[begin1];elsetmp[index] a[begin2];}while (begin1 end1)tmp[index] a[begin1];while (begin2 end2)tmp[index] a[begin2];//将tmp拷贝回a数组//修正2memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));//i在这一次拷贝的过程中不变啊begin1会变}}free(tmp);
}性能分析 递归情况下时间复杂度O(nlogN)空间复杂度O(N)需要开辟同等大小的数组用作归并稳定 5.非比较排序
5.1计数排序 计数排序又称为鸽巢原理是对哈希直接定址法的变形应用计数排序的主要思路是利用一个额外的数组C其中第i个元素表示待排序数组A中值等于的元素的个数。核心步骤在于将输入的数据值转换为键存储在额外开辟的数组空间中。 具体实现逻辑如下: 1首先找出待排序的数组中最大和最小的元素。 2.然后根据找到的最大和最小值确定计数数组C的长度一般等于待排序数组的最大值与最小值的差加上1。 3.接下来扫描一遍原始数组以当前值作为下标将该下标的计数器增1。这就完成了分配的步骤。 4.最后再次扫描计数器数组按顺序把值收集起来形成排序后的数组。总的来说计数排序是一种线性时间复计数排序在数据范围集中且数据类型为整数时效率很高但是适用范围及场景有限 void CountSort(int* a, int n)
{int i 0;//统计数组区间int min a[0];int max a[0];for (i 0; i n; i)//n是总个数{if (a[i] min)min a[i];if (a[i] max)max a[i];}//计数int range max - min 1;//range是值的范围差,需要开这么多个位置int* count (int*)calloc(range , sizeof(int));for (i 0; i n; i)count[a[i] - min];//排序for (int j 0; j n; j){for (i 0; i range; i){while (count[i]--)a[j] imin;}}
}性能分析 时间复杂度O(MAX(n range)),依赖与n和range的量级了 空间O(range) 它就不讨论稳定性了 一般稳定性用于讨论能排结构体类似数据的算法中因为稳定性的意义在于它保证了排序结果的正确性。如果一个排序算法是稳定的这意味着在排序过程中具有相同关键字的记录的相对次序会保持不变。例如在一个包含多个相同关键字的记录序列中如果某个记录在另一个记录之前那么在排序后的序列中这个记录仍将在另一个记录之前。 如果排序的内容仅仅是一个复杂对象的某一个数字属性那么稳定性将毫无意义。但在某些情况下比如需要根据多个属性进行排序时稳定性就显得尤为重要。此外如果排序前和排序后相同关键字的相对位置发生了变化可能会导致排序结果的错误从而影响到后续的处理和分析。 6.所有排序代码合集
Sort.h
#pragma once#includestdio.h
#includestdlib.h
#includestring.h//一律写升序
//
//目前性能排序
// 快排 堆排序 ≈ 希尔排序 归并 直接插入 冒泡 直接选择
//void PrintArr(int* a, int n);//插入排序————————————————————————————————————————//直接插入排序
//性能分析
//最差是O(n^2)
//但只要有部分有序性能就会比冒泡好很多
void InsertSort(int* a, int n);//斗地主摸牌摸一张往前面已经排好的序列中插入//希尔排序基于插入排序
//希尔排序性能分析假设整个数组初始是逆序
//①刚开始gap很大的时候如n/3则有n/3组数据每组数据比较3次12合计 n/3 * 3 O(n)
//②到中间过程时假设gap n/9,n/9组数据每组9个数据单租12...9 36合计36 * n/9 O(4n)但是在①的基础上已经调整部分顺序了不会是完全逆序所以实际性能会好于4n
//③最后gap 1整个序列以及十分接近有序了因此也是O(n)
//因此整个过程性能比较次数变化是先增加然后减少成向上箭头状
//
void ShellSort(int* a, int n);//插入排序————————————————————————————————————————
//交换排序————————————————————————————————————————//冒泡排序
//性能分析
//O(n)~O(n^2)
void BubbleSort(int* a, int n);//优化版设置一个检测变量如果在一趟中并未发生交换则改变此变量意味着此序列已经是有序的可以不用继续后面的趟数了//快排
//性能分析
//正常随机数据下性能都是较好的
//性能最好的时候每次的key都是中间值然后n个数二路递归参与递归的个数会减少高度是logn因此是logN
//性能最差的时候有序和接近有序的时候n个数每次key都是最小值或者最大值因此高度是n个数最开始是n然后n-1n-2因此是O(N^2)
void QuickSort(int* a, int n);//交换排序————————————————————————————————————————
//选择排序————————————————————————————————————————//堆排序
void HeapSort(int* a, int n);//直接选择排序
void SelectSort(int* a, int n);//斗地主摸牌牌发完之后一起整理整理过程先选出最小的放在最前面然后选次小放在最小的右边然后第三小//优化版在一趟遍历的过程中一次性选出最小的和最大的//选择排序————————————————————————————————————————
//归并排序//空间复杂度O(n)
//时间复杂度O(n*logN)
void MergerSort(int* a, int n);//非选择排序
//计数排序——哈希的思想
void CountSort(int* a, int n);
Sort.c
#define _CRT_SECURE_NO_WARNINGS 1#define _CRT_SECURE_NO_WARNINGS 1#includeSort.h
#includeStack.hstatic void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}void PrintArr(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}
}//时间复杂度 最坏(逆序)O(n^2) 最好(顺序)O(n)
//空间复杂度 O(1)//升序
void InsertSort(int* a, int n)
{int end 0;for (int i 0; i n - 1; i){//单趟//0-end是已经排好序了的end i;int tmp a[end 1];//正在被插入被排序的值while (end 0){//如果该数比end处的数小if (tmp a[end]){//往后挪a[end 1] a[end];}//说明该数已经比end处大或者相等了else{break;}//每次控制完end要往前走一步end--;}//走到这有两种情况//①while循环结束了此时tmp最小放在第一个位置也就是end1//②else的break此时tmp a[end]可以把tmp放到end后面了a[end 1] tmp;}
}void ShellSort(int* a, int n)
{//单趟//int gap 3;//间隔三个数为一组//int end 0;//for (int i 0; i n - gap; i gap)//i n - gap和a[end gap]的范围相呼应//{// end i;// int tmp a[end gap];// while (end 0)// {// if (tmp a[end])//这里就类似插入排序// {// a[end gap] a[end];// }// else// {// break;// }// end end - gap;// }// a[end gap] tmp;//}//多趟写法1——先排一组再排另外一组//int gap 3;////for (int j 0; j gap; j)//走gap趟//{// for (int i j; i n - gap; i gap)//内层就是单趟了// {// int end i;// int tmp a[end gap];// while (end 0)// {// if (tmp a[end])// {// a[end gap] a[end];// }// else// {// break;// }// end end - gap;// }// a[end gap] tmp;// }//}//多趟写法二——多组并排//int gap 3;//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];// }// else// {// break;// }// end end - gap;// }// a[end gap] tmp;//}//完整int gap n;//上面只是排完了一组现在要逐步减小gap的值使其能完整的排序while (gap 1)//gap等于1之后不能再进循环了再进循环除等之后就是0了{//gap / 2;//性能比/31稍差些//gap / 3;//尽量还是/2因为如果7个数第一次/3gap是2第二次就成0了gap gap / 3 1;//这样就可以保证最后一定是1了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];}else{break;}end end - gap;}a[end gap] tmp;}}
}void BubbleSort(int* a, int n)
{//基础版//for (int j 0; j n - 1; j)//{// for (int i 0; i n - 1 - j; i)// {// if (a[i] a[i 1])// {// Swap(a[i], a[i 1]);// }// }//}//优化版for (int j 0; j n - 1; j){int flat 1;for (int i 0; i n - 1 - j; i){if (a[i] a[i 1]){Swap(a[i], a[i 1]);flat 0;}}if (flat 1)break;}
}//前提是前面的数是堆
//时间复杂度O(logN)
static AdjustUp(int* a, int child)//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;}}
}//前提是左右子树都是大堆/小堆
//时间复杂度O(logN)
static AdjustDown(int* a, int n,int parent)
{int child parent * 2 1;//从最后一个非叶子结点开始向下调整while (child n){//选出左右子树中最大的if (child 1 n a[child] a[child 1])child;//比较if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}elsebreak;}
}//最大的问题前提是有一个堆的数据结构存在
//空间复杂度因为排序额外消耗了一段空间O(n)
//void HeapSort(int* a, int n)
//{
// HP hp;
// HeapInit(hp);
// for (int i 0; i n; i)
// {
// HeapPush(hp, a[i]);
// }
//
// int i 0;
// while (!HeapEmpty(hp))
// {
// //printf(%d , HeapTop(hp));
// a[i] HeapTop(hp);
// HeapPop(hp);
// }
// HeapDestroy(hp);
//}//优化后直接在数组的基础上建堆
//升序/时间复杂度 nlog(n)
void HeapSort(int* a, int n)
{//向上调整建堆//排升序建大堆//原因先建大堆选出最大的再与末尾交换size--然后再来一个向下调整即可时间复杂度为logN * N//建小堆选出最小的接下来从第二个开始向上调整建堆建堆时间复杂度就是logN * N//向上调整时间复杂度logN又因为这样做会把原有堆的规律打乱每个数都需要重新建堆//算上每次要选出最小的总计时间复杂度就是logN * N * N//建堆for (int i 0; i n; i){AdjustUp(a, i);}//排序int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}//向下调整也可以建堆
//时间复杂度O(N)
//一些前提须知①该位置的左右子树必须是同类型的堆②一个节点既可以看作大堆也可以看作小堆
//运用递归的思想那我们要从最后一个节点的父节点开始向下调整即可
void HeapSort2(int* a, int n)
{//建堆int fa ((n - 1) - 1) / 2;while (fa 0){AdjustDown(a, n, fa);fa--;}//排序int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}//时间复杂度O(n^2)
//第一趟n,第二趟n-2n-4void SelectSort(int* a, int n)
{//单趟//int mini 0;//int maxi 0;//for (int i 1; i n; i)//{// if (a[i] a[maxi])// {// a[maxi] a[i];// }// if (a[i] a[mini])// {// a[mini] a[i];// }//}//a[0] a[mini];//a[n - 1] a[maxi];//多趟——写法一//for (int j 0; j (n1) / 2; j)//这里为什么是(n1)/2拿俩数试试就知道目的是只能走左右两边的数//{// int mini j;// int maxi j;// for (int i j 1; i n - j; i)// {// if (a[i] a[maxi])// {// maxi i;// }// if (a[i] a[mini])// {// mini i;// }// }// //有问题// //有可能maxi就是在begin的位置如果把begin交换走了maxi的位置也会变// Swap(a[j], a[mini]);// Swap(a[n - 1 - j], a[maxi]);//}//多趟——写法二int begin 0;int end n - 1;while (begin end){int mini begin;int maxi begin;for (int i begin 1; i end; i){if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}//有问题//有可能maxi就是在begin的位置如果把begin交换走了maxi的位置也会变//Swap(a[begin], a[mini]);//Swap(a[end], a[maxi]);Swap(a[begin], a[mini]); if (maxi begin){//本来在begin位置的最大值换到mini位置了maxi mini;}Swap(a[end], a[maxi]);begin;--end;}
}//快速排序//相遇位置比key小怎么做到的
//答案右边先走
//分析
//相遇情况①
//Right动Left不动去跟L相遇
//相遇位置是L位置L和R在上一轮交换过因此此时L位置的值还是比Key小的
//相遇情况②
//L动R不动去跟R相遇
//R先走找到比key小的停下来这是L找大没找到一直往右走直到遇到R此时R位置的值也是比key小//优化
//为了避免数组接近有序时性能很差
//我们在选key的时候采取三数取中的策略int GetKey(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right])return mid;else if (a[left] a[right])//mid是最大值return right;elsereturn left;}else//left mid{if (a[mid] a[right])return mid;else if (a[right] a[left])//mid是最小的return left;elsereturn right;}}//写法一——hoare版本写起来很复杂void QuickSort(int* a, int left,int right)
{if (left right)return;int midi GetKey(a, left, right);Swap(a[left], a[midi]);int key left;int LeftMove left 1;int RightMove right;while (LeftMove RightMove){//前面这个条件就是为了避免没有满足条件的值的情况下RighrMove一直--while(LeftMove RightMove a[RightMove] a[key])//如果这里是的话在左右两边都碰到和key相等的情况下会死循环{RightMove--;}while (LeftMove RightMove a[LeftMove] a[key]){LeftMove;}Swap(a[LeftMove], a[RightMove]);}if(a[key] a[RightMove])Swap(a[key], a[RightMove]);QuickSort(a, left, LeftMove - 1);QuickSort(a, LeftMove 1, right);
}//写法二——挖坑法//自己写的错误写法存在bug
//void QuickSort(int* a, int left, int right)
//{
// if (left right)
// return;
//
// int midi GetKey(a, left, right);
// Swap(a[left], a[midi]);
//
// int key left;
// int LeftMove left 1;
// int RightMove right;
// int* tmp a[key];//把key处的值放到tmp中形成临时变量
// int hole key;
//
// while (LeftMove RightMove)
// {
// while (LeftMove RightMove a[RightMove] *tmp)
// {
// RightMove--;
// }
// if (LeftMove RightMove)
// {
// a[hole] a[RightMove];
// hole RightMove;
// }
// while (LeftMove RightMove a[LeftMove] *tmp)
// {
// LeftMove;
// }
// if (LeftMove RightMove)
// {
// a[hole] a[LeftMove];
// hole LeftMove;
// }
// }
//
// if (key RightMove *tmp a[RightMove])
// Swap(a[RightMove], tmp);
// //if (key LeftMove a[key] a[LeftMove])
// // Swap(a[key], a[LeftMove]);
//
// QuickSort(a, left, hole - 1);
// QuickSort(a, hole 1, right);
//}//void QuickSort(int* a, int left, int right)
//{
// if (left right)
// return;
//
// int midi GetKey(a, left, right);
// Swap(a[left], a[midi]);
//
// int key a[left];
// int LeftMove left;//这里最好不要写成left1因为这样在后续递归中如果子递归只有两个数其中一个是key且不进循环的时候
// //在填坑过程会很麻烦要么直接给hole复制但是这样另外一个地方值没有改变。要么Swap但是找不到hole地址了也是会出错
// //写成left后续子递归只有俩时也会正常判断直到只有一个值在最上头的if就return了
// int RightMove right;
// int hole left;
//
// while (LeftMove RightMove)
// {
// while (LeftMove RightMove a[RightMove] key)
// {
// RightMove--;
// }
// a[hole] a[RightMove];
// hole RightMove;
// while (LeftMove RightMove a[LeftMove] key)
// {
// LeftMove;
// }
// a[hole] a[LeftMove];
// hole LeftMove;
// }
// a[hole] key;
//
// QuickSort(a, left, hole - 1);
// QuickSort(a, hole 1, right);
//}//写法三——双指针
//本质是把一段大于key的区间往右推同时把小的换到左边//void QuickSort(int* a, int left, int right)
//{
// if (left right)
// return;
//
// int midi GetKey(a, left, right);
// Swap(a[left], a[midi]);
//
// int key left;
// //prev的情况有两种
// //在cur还没遇到比key大的值的时候prev紧跟着cur
// //遇到之后prev此时在比key大的这组数前面
// int prev left;
// int cur prev 1;//cur找比key小的找到之后prev然后交换prev和cur的值
//
// while (cur right)
// { //后面的意思是如果prev之后和cur在同一个位置那就不交换
// //并且只能写在后面prev只有在满足前面条件的情况下才需要
// if (a[cur] a[key] prev ! cur)
// {
// Swap(a[prev], a[cur]);
// }
// cur;//不管哪种情况cur是一直往后走的
// }
//
// Swap(a[prev], a[key]);
//
// QuickSort(a, left, prev - 1);
// QuickSort(a, right 1, right);
//} //优化
//因为这个递归规程类似二叉树然而我们知道二叉树最下面一层约占二叉树节点数的50%倒数第二层25%
//所以这个程序75%的消耗的花在最下面两层
//所以我们可以改变一下到最下面几层递归的形式
//希尔不适合优势就是在于能让大的数快速的跳跃到后面不适合这种小区间的
//直接插入适合除非小区间完全逆序不然都只需要动几下
//int SingleSort(int* a, int left, int right)
{int midi GetKey(a, left, right);Swap(a[left], a[midi]);int prev left;int cur prev 1;int keyi left;while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyi]);return prev;
}
//
//void QuickSort(int* a, int left, int right)
//{
// if (left right)
// return;
//
// if ((right - left 1) 10)
// {
// int keyi SingleSort(a, left, right);
//
// QuickSort(a, left, keyi - 1);
// QuickSort(a, keyi 1, right);
// }
// else//优化之处
// {
// InsertSort(a left, right - left 1);
// }
//}//写法四——非递归
//借助栈来实现其实递归的写法本质也是栈结构只是我们利用非递归的栈是动态栈存放在堆中更合理堆2G栈2M
//
void QuickSort_NonR(int* a, int begin, int end)
{ST st;STInit(st);STPush(st, end);STPush(st, begin);while (!STEmpty(st)){int left STTop(st);STPop(st);int right STTop(st);STPop(st);int key SingleSort(a, left, right);if (key 1 right){STPush(st, right);STPush(st, key 1);}if (left key - 1){STPush(st, key - 1);STPush(st, left);}}STDestroy(st);
}//归并排序——递归写法
//时间复杂度O(nlogN)
//空间O(N)
//
void Merger(int* a, int* tmp, int begin, int end)
{//递归————————————if (end begin)return;int mid (end begin) / 2;Merger(a, tmp, begin, mid);Merger(a, tmp, mid 1, end);//归并————————————int index begin;int begin1 begin;int end1 mid;int begin2 mid 1;int end2 end;//归并——找小while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[index] a[begin1];elsetmp[index] a[begin2];}while (begin1 end1)tmp[index] a[begin1];while (begin2 end2)tmp[index] a[begin2];//将tmp拷贝回a数组memcpy(a begin, tmp begin, sizeof(int) * (end - begin 1));
}void MergerSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc failed);exit(-1);}Merger(a, tmp, 0, n - 1);free(tmp);
}//归并排序——非递归写法
//用不了栈或队列
//为什么快排可以因为快排是先序而归并是后序
//先序的话区间入栈之后-排完-出栈但是归并是走到底才开始排
//可能会说走到底再排也可以先把区间入进去呀
//不可以因为后续的区间是根据前面区间排完结果而来的
//那非递归的思路要来自斐波那契数列的非递归了。就是把递归倒过来走我们递归是把大化小那非递归就从小开始排然后不断扩大区间void Merger_NonR(int* a, int n)
{//创建临时数组int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc failed);exit(-1);}//11归——22归——44归for (int gap 1; gap n; gap * 2){for (int i 0; i n; i 2 * gap)//每次往后跳两个区间{int begin1 i;int end1 i gap - 1;int begin2 i gap;int end2 i 2 * gap - 1;int index i;//数组个数不是2次幂避免越界的修正1//只有end1begin2end2会发生越界begin1不会因为begin1iin//begin2 n时end1 n-1begin2 n时end1 n。都是不用归并了因此break的情况//也就是归并的第二组不存在//为什么不用归并了因为在前面的小区间归并的时候已经是有序的了if (begin2 n){break;}if (end2 n){end2 n - 1;//修正end2的下标让最后一组在合理范围内归并//这里为什么还要归并//因为end2越界而前面没越界的时候前面一组和这一组的顺序还没排好啊虽然数量不对等但还要排序啊}//归并——找小while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[index] a[begin1];elsetmp[index] a[begin2];}while (begin1 end1)tmp[index] a[begin1];while (begin2 end2)tmp[index] a[begin2];//将tmp拷贝回a数组//修正2memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));//i在这一次拷贝的过程中不变啊begin1会变}}free(tmp);
}//时间复杂度O(n range)
//空间O(range)
//适合紧凑的数列
//只适合整数
void CountSort(int* a, int n)
{int i 0;//统计数组区间int min a[0];int max a[0];for (i 0; i n; i)//n是总个数{if (a[i] min)min a[i];if (a[i] max)max a[i];}//计数int range max - min 1;//range是值的范围差,需要开这么多个位置int* count (int*)calloc(range , sizeof(int));for (i 0; i n; i)count[a[i] - min];//排序for (int j 0; j n; j){for (i 0; i range; i){while (count[i]--)a[j] imin;}}
}test.c
#define _CRT_SECURE_NO_WARNINGS 1#includeSort.h
#includeStack.hint main()
{// int a[] {0 ,100,3,4,2,1,7,88,8,5,6,9,10 };int a[] { 4,2,1,7,8,3,5,6 ,9};int size sizeof(a) / sizeof(a[0]);//InsertSort(a, size);//PrintArr(a, size);//ShellSort(a, size);//PrintArr(a, size);//BubbleSort(a, size);//PrintArr(a, size);HeapSort(a, size);PrintArr(a, size); //SelectSort(a, size);//PrintArr(a, size);//QuickSort_NonR(a, 0,size-1);//PrintArr(a, size);//MergerSort(a,size);//PrintArr(a, size);//Merger_NonR(a, size);//PrintArr(a, size);//CountSort(a, size);//PrintArr(a, size);return 0;
}Stack.h
#pragma once#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int STDataType;typedef struct Stack
{STDataType* data;int top;int capacity;
}ST;void STInit(ST* ps);
void STDestroy(ST* ps);void STPush(ST* ps, STDataType x);
void STPop(ST* ps);STDataType STTop(ST* ps);int STSize(ST* ps);
bool STEmpty(ST* ps);Stack.c
#define _CRT_SECURE_NO_WARNINGS 1#includeStack.hvoid STInit(ST* ps)
{assert(ps);ps-data NULL;ps-top -1;ps-capacity 0;
}void STDestroy(ST* ps)
{assert(ps);free(ps-data);ps-data NULL;ps-top -1;ps-capacity 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);//CheckCapacityif (ps-capacity ps-top 1){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-data, sizeof(STDataType) * newcapacity);if (NULL tmp){perror(realloc failed);exit(-1);}ps-data tmp;ps-capacity newcapacity;}ps-top;ps-data[ps-top] x;
}void STPop(ST* ps)
{assert(ps);assert(ps-top 0);ps-top--;
}STDataType STTop(ST* ps)
{assert(ps);return ps-data[ps-top];
}int STSize(ST* ps)
{assert(ps);return( ps-top 1);
}bool STEmpty(ST* ps)
{assert(ps);return ps-top -1;
}
