网站建设以及推广提案书,静态网站公用头部 调用标题,企业邮箱域名怎么填写,国外免备案域名注册目录
冒泡排序
选择排序
堆排序
插入排序
希尔排序
快速排序 hoare版本
挖坑法
前后指针法
快速排序优化
三数取中法
小区间优化
快速排序非递归
栈版本
队列版本
归并排序
归并排序非递归
编辑
计数排序
各排序时间、空间、稳定汇总 冒泡排序
void Bub…目录
冒泡排序
选择排序
堆排序
插入排序
希尔排序
快速排序 hoare版本
挖坑法
前后指针法
快速排序优化
三数取中法
小区间优化
快速排序非递归
栈版本
队列版本
归并排序
归并排序非递归
编辑
计数排序
各排序时间、空间、稳定汇总 冒泡排序
void BubbleSort(int* a, int n)
{for (int i 0; i n; i){int flag 0;for (int j 0; j n - i - 1; j){if (a[j] a[j 1]){Swap(a[j], a[j 1]);flag 1;}}if (flag 0)break;}
}
冒泡排序相信你已经写了不少了 冒泡排序的思想是两两比较如果要排升序那么要找到最大的一直比较直到找到最大的冒到最后然后进行n次这样的流程即完成排序 这里对冒泡排序有两个优化点 1. 第二个循环里我们可以写 j n - 1但优化过后就是 j n - i - 1 要-1是因为防止下面的a[j 1]数组越界而-i则是因为已经排过了i次那么后面就有i个数是已经排好的所以不需要进入下面的if语句进行比较 2. 用了一个flag变量主要是看是否有进入过if语句若没有进入过if语句说明数据已经是排好的那么即可直接break退出循环 时间复杂度O(N^2)
空间复杂度O(1) 由于时间复杂度过高在实际应用中并无意义只有在教学中有意义 稳定性稳定
选择排序
void SelectSort(int* a, int n)
{int begin 0, end n - 1;int maxi 0, mini 0;while (begin end){int maxi begin, mini 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]);Swap(a[end], a[maxi]);if (begin maxi)maxi mini;begin;end--;}
}选择排序的思想是先找小或找大找到了就放在最后或者第一个缩小区间循环往复 但这里写的选择排序是一次找两个遍历一次即找大又找小 时间复杂度O(N^2)
空间复杂度O(1)
稳定性不稳定 理由交换时相同的数可能会交换顺序 堆排序
void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n){if (child 1 n a[child 1] a[child])child;if (a[child] a[parent]){Swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}
}void HeapSort(int* a, int n)
{for (int i (n - 1 - 1) / 2; i 0; i--)AdjustDown(a, n, i);int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
} 堆排序是选择排序的一种。 堆排序的思想是利用向下调整向上调整也可以先建大堆or小堆这样我们就能找到最大或者最小的那个数据交换到末尾即放置好第一个数的位置并接着向下调整保持堆的特性 具体细节参考
C数据结构堆实现、排序-CSDN博客
时间复杂度O(N * logN)
空间复杂度O(1) 由于堆的高度是 O(logN)每个非叶子节点的调整时间复杂度是 O(log N) 数组中有 O(N) 个非叶子节点因此构建堆的总时间复杂度是 O(N * logN) 但实际上由于树的结构这个操作通常被优化为 O(N) 稳定性不稳定
插入排序
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
}插入排序的思想就像插入扑克牌排序一样我们需要从小到大一个个排好序 end之前表示已经排好序的数组最开始1个数也算排好end1就表示我们要在[0end]这个区间里插入end1的这个值此过程循环n-1次即可 所以while循环控制的是一次一个数插入的过程tmp表示要插入的数若tmp a[end]升序即我们需要在前面这个有序区间内往前走end--若tmp a[end]则找到了我们需要插入的位置这个位置就是end1
时间复杂度O(N^2)
空间复杂度O(1) 它虽然和冒泡排序看起来差不多但它还是比冒泡排序快很多的 但是相比堆排、快排、希尔排序、归并排序这些就没法比了 稳定性稳定
希尔排序
void ShellSort(int* a, int n)
{int gap n;while (gap 1){gap gap / 3 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];end - gap;}else{break;}}a[end gap] tmp;}}
} 希尔排序是插入排序的一种但它比普通的插入排序快的多 希尔排序的思想是先选定一个间隔gap然后按照这个间隔分成gap组根据这个组内来进行排序这样就从原本的杂乱无章变成稍微有序。此时接着将gap缩小那么数组将会越来越有序最后就变成了有序的数组了 第二次由于已经是有序了所以不需要排 以此类推当全部的gap组排好之后我们的第一躺希尔排序就完成了 如果你觉得这样排序那么多次效率并没有什么提升就大错特错了 拿插入排序来比较插入排序如果想排好上面的一次组数据973那么它需要一个下标来沿途经过整个数组一个个比较当到达7的时候才能够交换然后接着跟沿途的其他数据一个个比较最后才能找到3和3交换这么一个过程就将近遍历了一整个数组 而我们的希尔排序的gap就可以让它快速的跳跃中间的数据依次效率有了极大的提升。就上图的这10个数据可能看的不太明显只需要比较几次。但是我们的计算机的效率是很高的大多数电脑一秒钟可以跑上亿的数据所以若是在实际中我们需要排个几百万上亿个数据的时候我们的gap就可以跳过很多数据的比较。 代码实现中我们可以发现其实它跟插入排序基本一致就多了一个循环然后把内部的部分数据改成gap就完成了
内层的两个循环是进行一躺gap组的排序可以将杂乱无章的数组变成逐渐有序的数组
最外层的循环是控制gap的gap越小进行一躺排序就会越有序当最后gap为1的时候它其实就是我们上面的插入排序所以gap为1的时候排序就已经完成了 gap / 3 1的原因是个人认为/3的效率比较高但是只是/3会有可能到不了1的情况例如 2 / 3 0接下来我们一直/3都到不了0 所以我们需要1 最开始Shell提出取 gap / 2后来Knuth提出gap / 3 1无论是哪一种具体是谁快还没有得到证明 时间复杂度O(N^1.3)
空间复杂度O(1)
稳定性不稳定
快速排序
void QuickSort(int* a, int left, int right)
{if (left right)return;int keyi PartSort1(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);
} PartSort是部分排序在快排中是个选key的过程 key是一个值通常把它选成数组中最左边的第一个数 我们进行一次PartSort时就可以把key的位置给确定好算是排好了一个数而且这个数大概率是在中间或者中间的旁边而且它的左右两边都会是比它小或者比它大的数 PartSort有三种版本这里我把它分成了PartSort1 PartSort2 PartSort3 PartSort1hoare版本 PartSort2挖坑法 PartSort3前后指针法 keyi位置则代表已经排好了的位置这时候我们再次划分区间将keyi的左边和右边划分再继续递归进行新一轮的部分排序选keyi一直递归下去即可完成我们的递归
时间复杂度O(N*logN)
空间复杂度O(logN)递归深度为logN
稳定性不稳定
具体PartSort如下 hoare版本
int PartSort1(int* a, int left, int right)
{int midi GetMidi(a, left, right);Swap(a[left], a[midi]);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]);}Swap(a[begin], a[keyi]);return begin;
}GetMidi属于快速排序优化下面有解释暂不考虑 该函数需要传一个指针和一段区间 [leftright]
首先选定一个keyi下标这个下标对应数组中的值则为key
然后给定两个下标记作begin和end一个指向左一个指向右
我们需要做的是先从右边开始end它找比key还要小的数字左边begin找比key还要大的数字找到之后将它们交换升序
若是begin和end相遇则该位置则为key的最终位置因为大的已经放到了右边小的已经放到了左边将key和相遇位置交换即可 我们必须要从右边开始找小然后再从左边找大因为这样才能保证最终位置是比key要小的这样才能将相遇位置的值换到左边保证了keyi位置左边都比key小右边都比key大 最后我们返回key的位置即可 挖坑法
int PartSort2(int* a, int left, int right)
{int mid GetMidi(a, left, right);Swap(a[mid], a[left]);int hole left;//key记录挖坑位置的值int key a[hole];while (left right){while (left right a[right] key)right--;a[hole] a[right];hole right;while (left right a[left] key)left;a[hole] a[left];hole left;}a[hole] key;return hole;
}
优点是比hoare方法好理解
还是跟hoare一样先找一个keyi但是这里是一个坑hole
然后一样从右边开始找小找到后填在我们挖的这个坑里找到小的那个地方就又变成一个坑了
接着左边找大找到了填到坑里然后自己变成坑以此循环往复
最后将剩下的那个坑用我们最开始挖的填上即可 前后指针法
int PartSort3(int* a, int left, int right)
{int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int keyi left;int prev left;int cur left 1;while (cur right){if (a[cur] a[keyi] prev ! cur)Swap(a[cur], a[prev]);cur;}Swap(a[prev], a[keyi]);return prev;
}
用了两个指针来走下标并不是C语言中真正意义上的指针
在if语句中由于是运算符若cur位置的值小于keyi位置上的值才会进行下一步的判断那么判断prev的时候就会让prev往前走
所以当cur位置的值小于keyi位置上的值prev和cur同时否则cur 后面的条件判断其实是为了减少Swap的次数因为相同位置的prev和cur交换并没有任何意义 最后让prev和keyi交换即可 三个方法选其一即可
本人认为hoare版本可能效率比其他的高一丢丢挖坑好理解前后指针代码简洁
快速排序优化
三数取中法
前面的hoare挖坑前后指针都使用了GetMini函数它是可以增加快排的效率的
设想一下若是一个数组里面的值全是2已有序但我们不知情的情况下使用了快排来进行排序会发生什么
这时候快排的效率会变得极低时间复杂度变成O(N^2)
这是快排比较难受的一点主要原因就是因为我们的keyi每次都是在最左边从而无法划分左右区间进行递归这样自然效率就很低
所以就其核心我们要尽量让keyi的位置尽量在中间那么就需要用到三数取中法
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{if (a[midi] a[right]){return midi;}else if (a[left] a[right]){return left;}else{return right;}}
}这段代码看起来很长但其实很简单易懂
就是先取到这段区间的中间值midi用a[left]a[right]a[midi]三个值进行比较取出大小在中间的那个即可即使它不是整段区间的最中间的那个但至少不是最差的那个
小区间优化
其实在数据很大的时候我们这样递归下去的时间才会很快若是数据量比较小的情况下我们还要递归很多的数据非常的划不来
所以我们可以制定一个标准值当这段区间到达这个标准值时就不让它递归了而是直接使用其他的排序来完成这段的排序这里直接使用插入排序
void QuickSort(int* a, int left, int right)
{if (left right)return;if (right - left 1 10){InsertSort(a, right - left 1);}else{int keyi PartSort1(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);}
}
快速排序非递归
这里是需要引入我们之前已经写好的栈和队列进来才能完成我们下面的非递归方法
栈版本
void QuickSortNonR1(int* 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 keyi PartSort1(a, begin, end);if (keyi 1 end){StackPush(st, end);StackPush(st, keyi 1);}if (keyi - 1 begin){StackPush(st, keyi - 1);StackPush(st, begin);}}StackDestroy(st);
} 我们可以用一个栈来模拟递归的过程
快排是以一个keyi为基准划分两段区间从而进行排序那么我们可以在每次PartSort选出keyi之后将区间入栈下一轮需要的时候就可以直接出栈
首先我们先将最开始的左右区间入栈 先入的右区间这样下面取出来的时候可以先取出左再取右 接下来拿到begin和end对这段区间进行PartSort选出keyi
选出了keyi后又划分出了区间我们再次将这两个区间入栈
以此往复就模拟实现了递归的快速排序
最后不要忘记了将栈销毁放置内存泄漏
队列版本
void QuickSortNonR2(int* a, int left, int right)
{Queue q;QueueInit(q);QueuePush(q, left);QueuePush(q, right);while (!QueueEmpty(q)){int begin QueueFront(q);QueuePop(q);int end QueueFront(q);QueuePop(q);int keyi PartSort1(a, begin, end);if (begin keyi){QueuePush(q, begin);QueuePush(q, keyi - 1);}if (end keyi){QueuePush(q, keyi 1);QueuePush(q, end);}}QueueDestroy(q);
} 和上面的栈版本类似
都是先入一段区间拿到这段区间的begin和end然后进行PartSort选出keyi接着入两段区间继续PartSort
最后也是不要忘记了将队列释放掉即可 栈版本和队列版本最主要的区别就是一个是深度优先一个是广度优先 栈是深度队列是广度 栈是先将最开始的[left, keyi - 1]排好再排[keyi 1, end] 而队列是[left, keyi - 1]和[keyi 1, end]同时往下排 归并排序
void _MergeSort(int* a, int* tmp, int begin, int end)
{if (begin end)return;int mid (begin end) / 2;int begin1 begin, end1 mid;int begin2 mid 1, end2 end;_MergeSort(a, tmp, begin1, end1);_MergeSort(a, tmp, begin2, end2);int i begin;while (begin1 end1 begin2 end2){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, sizeof(int) * (end - begin 1));
}void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(mallloc fail);return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);
} 归并排序的算法采用的是分治法它需要开一段长度和排序数组已有大小的空间来配合完成排序 它的思想是将已有的子序列合并得到完全有序的序列 先让将数组中的值采用”分治“分到有序的时候一个数也算有序再回到上一次分治的时候将其变成有序以此类推一直往上到最开始完整的区间即可 这个不断解决子问题的问题当然是用递归解决好了 ”分“过程 ”治“过程 在MergeSort中我们需要先开一段长度为n的空间将其传给_MergeSort函数来配合这块空间递归完成排序
MergeSort中就三个步骤一开空间二排序三释放
在这个子函数_MergeSort中我们也要传左区间和右区间
下面来进入子函数中看看 我们先定义几个变量即将该数组[leftright]再次分成两个区间由中间值mid来划分分别标记为begin1end1begin2end2 这里的end1必须为mid不能是mid1 begin2只能是mid1不能是mid 也就是end1必须为偶数否则该排序会出问题 若按照错误方法来例如begin 0end 3那么mid 1begin1 0end1 2递归左右区间为[02]也就是begin 0end 2那么mid 1begin1 0end1 2这样又递归就会出现栈溢出的情况所以必须要按照 上面代码的方式走 我们需要取递归它的左右区间从小问题开始解决 递归需要有个结束条件那就是当这个区间不存在时结束递归 我们归并下来后按循环走将两个小区间中最小的值放到我们前面传的tmp数组里然后i然后找第二小的找到接着放进tmp数组第i个位置i循环往复
第一个循环走完其中某一个数组中的元素也就全部被拷贝进了tmp数组里这时候我们只需要找到还没有全部走完的数组将其全部放到tmp数字第i个位置的后面即可 i必须从begin开始不能是0 最后用memcpy函数将tmp数组中的值全部拷贝到a数组中即可
这样我们递归版本的归并排序就完成了
时间复杂度O(N*logN)
空间复杂度O(N)
稳定性稳定 归并排序的缺点在于需要O(N)的空间复杂度 归并排序的使用更多的是使用在磁盘中的外排序问题也就是当一个文件比较大我们的一个程序不足以支撑使用如此之多的数据来排序那么这时候就可以使用归并排序分治 归并排序非递归
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;if (begin2 n)break;if (end2 n)end2 n - 1;int j i;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));}gap * 2;}free(tmp);
} 非递归相比于递归的好处就是不怕栈溢出的风险
大体思路和前面递归版本的归并排序一样
我们需要先开一段空间 下面我们要开始模拟递归的过程
我们定义了一个gap这个gap是每组的间隔模拟了从最开始的两个数据排序这个gap我们从1开始到布满整个数组为止停止循环这就是第一个while
下面的for循环就是为了完成每一组的排序
for循环下面的内容当然就是单组的排序了 还是和前面一样先定义好左右区间 这里也是和上面的递归版本一样
将小的数放到tmp数组中当第一个循环走完再去找没走完的那个区间将剩余数据一个个放到tmp数组中即可
最后再将tmp数组中的数据全部拷贝到a数组中即完成单趟排序
for循环走完后也就代表这一趟间隔gap为1的已经走完了也就是两个数据已经有序了那么要到四个数据开始排序 所以不要忘了gap * 2 以此类推当gap n时就代表已经走完了
所以循环结束条件为gap n
但是如果只做到这里是还没有完成排序的它只能完成2^n个数据的排序这里分区间的时候会存在越界的情况所以当数据不为2^n个数时我们需要调整区间 这里的越界只有两种情况一种是end2越界一种是begin2和end2都越界
若begin2和end2都越界了那么这躺排序已经不需要右区间而左区间本身就有序所以我们直接break即可
若只有end2越界那么[begin2end2]中是还存在数据需要我们排序的我们不能直接break只需让end2等于数组最大下标即可
最后不能忘记了释放掉tmp数组防止内存泄漏 这样非递归版本的归并排序就完成了
计数排序
void CountSort(int* a, int n)
{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));for (int i 0; i n; i){count[a[i] - min];}int j 0;for (int i 0; i n; i){while (count[i]--){a[j] i min;}}free(count);
} 计数排序又称鸽巢原理它的思想本质是哈希 哈希的思想就是让某一个数据与其存储位置产生某种联系 计数排序里就采用了这种思想它会对我们给的数组的每一个值用另一个数组的下标来计数 例如5536那么另一个数组count取到的值count[3] 1count[5] 2count[6] 1 首先我们需要先找到该数组的最大值和最小值这样才能确定区间
方法为用循环遍历整个数组 接下来根据这个范围来开空间因为我们开的数组是要用下标来存储数据所以要1
开的空间count使用了calloc函数该函数和malloc的区别就是它可以初始化这块空间这正是我们想要的我们需要让这块空间的值都为0
然后这个for循环做的就是遍历原数组将原数组的值减去最小值这个值映射到count数组中让这个下标的值这样就会统计这个值出现的次数而与原数组建立的关系就是减去一个min的关系 这是最后一步
我们计数完毕后就可以从0开始遍历我们count数组若这个count数组有值说明原数组min之后的值是存在的我们直接将该值加上min放到原数组中即可由于下标是从小到大的所以排出来的数据必定是有序的
这样就能排好序了 最后记得释放掉count数组即可
这就是我们的计数排序了
时间复杂度O(MAX(Nrange)) 由于我们最后一步是不仅仅要遍历原数组还要将count数组的值全部过一遍而count是根据range来开的所以该排序的时间复杂度为N和range大的那一个 空间复杂度O(range)
稳定性稳定 计数排序在数据范围集中时效率很高 但是由于条件的限制只能排序整型而且若数据不集中则会开极大的空间效率极低 所以它的使用场景有限 各排序时间、空间、稳定汇总 完
