手机网站开发多少钱,天津做流产五洲网站,抖音代运营mcn,网站设计制作上海公司#x1f493;博主个人主页:不是笨小孩#x1f440; ⏩专栏分类:数据结构与算法#x1f440; 刷题专栏#x1f440; C语言#x1f440; #x1f69a;代码仓库:笨小孩的代码库#x1f440; ⏩社区#xff1a;不是笨小孩#x1f440; #x1f339;欢迎大家三连关注… 博主个人主页:不是笨小孩 ⏩专栏分类:数据结构与算法 刷题专栏 C语言 代码仓库:笨小孩的代码库 ⏩社区不是笨小孩 欢迎大家三连关注一起学习一起进步 排序算法 排序的概念插入排序希尔排序选择排序冒泡排序堆排序快速排序归并排序计数排序 排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次 序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排 序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 常见的排序算法 除了这些排序以外该有一个很奇怪的排序计数排序我们待会将我们接下来就从第一个排序开始
插入排序 插入排序的思想很简单就是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。插入排序可以理解为就是我们打扑克牌摸排的过程摸一张排依次比较然后将它插入的合适的位置。 我们看图 这个排序很简单根据图我们就可以把第一个数据当成有序的数据然后后面的数据依次插入直到将数据插入完这样就有序了。
代码如下
void InsertSort(int* arr, int n)
{for (int i 0; i n-1; i){//end表示有序数据的最后一数的下标int end i;//tmp保存需要插入的值int tmp arr[end1]; while (end 0){//依次比较如果比需要插入的数大就往后移否则就跳出循环if (arr[end] tmp){arr[end 1] arr[end];end--;}else{break;}}//跳出循环后将需要插入的数据放到end后面的位置arr[end 1] tmp;}
}总结 元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定 希尔排序 希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数gap把待排序文件中所有记录分成gap个组所有距离为gap的记录分在同一组内并对每一组内的记录进行排序。然后重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。 插入排序第一步我们需要预排序 预排序后插入排序就很快了直接使用插入排序就可以了。但是当我们的gap1是希尔排序就相当于插入排序了。这里gap可以取很多值但是要保证最后一次gap1. 代码如下
void ShellSort(int* arr, int n)
{int gap n;//要进行多趟排序while (gap 1){//1是为了保证gap最后一次等于1gap gap / 3 1;for (int i 0; i n - gap; i){//每次分别排gap组数据每组间隔gap个数据一共gap组int end i;int tmp arr[i gap];while (end 0){if (arr[end] tmp){arr[end gap] arr[end];end - gap;}else{break;}}arr[end gap] tmp;}}
}总结 希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的 希尔排序的时间复杂度都不固定我们记住大约就等于O(N^1.3)稳定性不稳定 选择排序 选择排序是每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 我们这里实现的是依次找大的然后放到最后面和图不太一样但是思想都一样。 代码如下
void SelectSort(int* arr, int n)
{int end n - 1;while (end0){//每次初始化最大在0处防止maxi到已经在排好序的位置int maxi 0;for (int i 0; i end; i){if (arr[i] arr[maxi]){maxi i;}}//找到后和最后一个数据交换Swap(arr[maxi], arr[end]);end--;}
}选择排序我们这里可以优化一下就是每次选出最小的和最大的然后最小的放到左边最大的放到右边然后接着找剩余数据的最大最小直到结束。 代码如下
void SelectSort(int* arr, int n)
{int begin 0;int end n - 1;while (begin end){int maxi begin;int mini begin;//依次找大和找小for (int i begin; i end; i){if (arr[mini] arr[i]){mini i;}if (arr[maxi] arr[i]){maxi i;}}//找到后将大的数据放到后面Swap(arr[maxi], arr[end]);//防止最小的数据在最后面被换走了及时修正if (mini end){mini maxi;}Swap(arr[mini], arr[begin]);begin;end--;}
}总结 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定 冒泡排序 冒泡排序大多数人应该都知道它的基本思想就是依次比较将大的数据冒到最后然后重复前面的过程就可以完成排序。 代码如下
void BubbleSort(int* arr, int n)
{for (int i 0; i n - 1; i){int flag 1;for (int j 1; j n - i; j){if (arr[j] arr[j - 1]){Swap(arr j, arr j - 1);flag 0;}}if (flag 1){break;}}
}总结 冒泡排序是一种非常容易理解的排序时间复杂度O(N^2)空间复杂度O(1)稳定性稳定 堆排序 堆排序前面已经讲过一次了这里就不做过多的解释了想要详细了解请戳。 这里是引用 总结 堆排序使用堆来选数效率就高了很多。时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定 快速排序 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中 的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右 子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 我们每次可以将数组划分为两部分keyi是那个选出来的数的最终的下标然后第一次排序后就是[left,keyi-1],keyi,[keyi1,right]我们每一趟要保证的是keyi左边的数据逗比key小右边的都比它大然后左区间重复这个操作右区间也重复这个操作这就有点像二叉树的前序遍历直到每个区间只剩下一个值或者区间不存在时我们结束递归。 快排的整体框架
void QuickSort(int* arr, int left, int right)
{if (left right){return;}int keyi partSort(arr,left,right);QuickSort(arr,left, keyi - 1);QuickSort(arr,keyi 1, right);}这里的partSort就是我们的单趟排序我们讲三种方法
hoare版本 我们需要两个指针一个从左边开始走一个从右边开始走再定义一个key和keyikeyi保存key的小标如果左边左key就右边先走右边左key就左边先走然后左边找比key大的数右边找比key小的数找到后交换然后接着走直到相遇然后把相遇的位置和key交换一下。 为什么左边做key右边先走呢 因为这样可以保证相遇的位置一定是比key小等于的数相遇无非就是两种情况L遇到RR遇到L如果是L遇到R我们让右边先走R停下的位置一定是比key小的数如果是R遇L假设数组中的数都比key大所以key遇到L是就是等于key所以我们左边做key让右边先走是可以保证相遇位置一定比key小的。 代码如下
int partSort1(int* arr, int left, int right)
{int keyi left;while (left right){//右边找小while (left right arr[right] arr[keyi]){right--;}//左边找大while (left right arr[left] arr[keyi]){left;}Swap(arr[left], arr[right]);}Swap(arr[left], arr[keyi]);return left;
}
挖坑法 我们还是将左边做key然后保存它的值然后它就是一个坑还是两个指针由于左边有一个坑所以右边就要找小的数来填这个坑然后将右边的那个位置变成新的坑然后左边找大找到后接着填坑更新坑的位置L和R一定有一个是坑所以当他们相遇时那个位置一定是坑然后将key放进去即可。 代码如下
int partSort2(int* arr, int left, int right)
{int hole arr[left];int keyi left;while (left right){while (left right arr[right] hole){right--;}arr[keyi] arr[right];keyi right;while (left right arr[left] hole){left;}arr[keyi] arr[left];keyi left;}arr[keyi] hole;return keyi;
}
前后指针法 定义两个指针一个prev一个curcur用来遍历数组还是用左边的值来做key然后将cur找到比key小的值就和prev位置的数交换直到遍历结束然后再把prev位置的值可key交换即可。 代码如下
int partSort3(int* arr, int left, int right)
{int keyi left;int cur left 1;int prev left;while (cur right){if (arr[cur] arr[keyi]prev!cur){Swap(arr[prev], arr[cur]);}cur;}Swap(arr[prev], arr[keyi]);return prev;
}
快速排序的非递归版本 非递归的话我们用队列和栈都是可以的但是想要模仿递归的路径的话我们就要使用栈我们先把数组的整个区间放到栈里面然后在进行一趟排序后我们把排出来的左区间和右区间入栈由于先走左边所以就要先把右边的区间压栈然后依次进行只要区间存在我们就压只要栈不为空就代表一直有区间未处理。所以我们就一直重复操作当然单趟排序的话用上面的那种方法都可以。 代码如下
void QuickSortNonR(int* arr, 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(arr, begin, end);if (keyi 1 end){StackPush(st, end);StackPush(st, keyi 1);}if (keyi - 1 begin){StackPush(st, keyi - 1);StackPush(st, begin);}}
} 快速排序还可以优化他的效率和选的key的关系很大所以我们有种方法叫做三数取中左边的值、右边的值、中间的值然都找到这三个数中间的数把他换到左边就可以了。 总结 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序时间复杂度O(N*logN)空间复杂度O(logN)稳定性不稳定 归并排序 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序需要将区间分为两部分然后两部分都要有序才能归并那左右区间又可以分割以此类推当区间只有一个数的时候就可以认为有序这时我们可以走一个类似与二叉树后序遍历的思路我们想归并左右区间但是左右区间都无序我们就递归左边让左边有序在递归右边让右边有序最后再左右归并就可以排好了。 我们这里就需要一个数组来保存我们归并的值我们取两段区间的值依次比较拿小的尾插到tmp数组中等归并完再拷回原数组即可。 代码如下
void _MergeSort(int* arr, int left, int right,int* tmp)
{if (left right){return;}//分割区间int mid (left right) / 2;_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid1, right, tmp);int begin1 left, end1 mid;int begin2 mid 1, end2 right;int k left;while (begin1 end1 begin2 end2){//选小的来尾插if (arr[begin1] arr[begin2]){tmp[k] arr[begin1];}else{tmp[k] arr[begin2];}}//不管哪个没有拷贝完因为区间是有序地直接尾插就可以while (begin1 end1){tmp[k] arr[begin1];}while (begin2 end2){tmp[k] arr[begin2];}//拷贝回原数组memcpy(arr left, tmp left, (right - left 1) * sizeof(int));}
void MergeSort(int* arr, int left, int right)
{int* tmp (int*)malloc(sizeof(int) * (right - left 1));//不能在这个函数中递归不然每次都要开辟数组_MergeSort(arr, left, right, tmp);free(tmp);
}归并排序的非递归版本 我们会发现归并排序用队列和栈都用不了但是我们可以使用循环来解决它首先我们需要一个gap来记录每组归并的数据有几个然后控制区间来进行归并。 但是在归并中会存在很多的越界问题比如end1越界了或者begin1越界了但是这两种情况我们都很好处理等处理到这种错误时我们可以看成只剩下一组数据就可以不用动放在原数就好等待下一轮归直接break跳出就可以还有一种情况是end2越界了这时还有一部分数据需要归并那我们就调整end2为n-1就可以了。 代码如下
void MergeSortNonR(int* arr, int n)
{int* tmp (int*)malloc(sizeof(int) * n);int gap 1;//gap表示每组数据的长度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;int k i;//越界即使调整或退出if (end1 n || begin2 n){break;}if (end2 n){end2 n - 1;}while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){tmp[k] arr[begin1];}else{tmp[k] arr[begin2];}}while (begin1 end1){tmp[k] arr[begin1];}while (begin2 end2){tmp[k] arr[begin2];}//每次归并完拷贝会原数组memcpy(arri, tmpi, sizeof(int)*(end2-i1));}gap * 2;}free(tmp);
}总结 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定 计数排序 计数排序是非常奇怪的排序它不需要比较任何数据他开辟一个和最大值一样的数组然后将该数组初始化为0然后原遍历数组将原数组的值对应到我们开辟数组的下标出现一次我们就该位置然后统计每个位置出现的次数然后在依次拷贝回原数组就可以了。 但是如果数据很大很集中我们就没必要开那么大会很浪费我们需要找到最大值和最小值然后使用相对位置就可以了每个数对应到减去最小值的那个小下标这样我们数组也不用开的很大。 代码如下
void CountSort(int* arr, int n)
{int min arr[0];int max arr[0];//找最大值和最小值for (int i 0; i n; i){if (max arr[i]){max arr[i];}if (min arr[i]){min arr[i];}}//计算区间方便开数组int c max-min1;int* nums (int*)malloc(sizeof(int) * c);memset(nums, 0, c * sizeof(int));//统计for (int i 0; i n; i){nums[arr[i]-min];}int k 0;//拷贝回原数组for (int i 0; i c; i){while (nums[i]--){arr[k] imin;}}free(nums);
}总结 计数排序在数据范围集中时效率很高但是适用范围及场景有限。时间复杂度O(MAX(N,范围))空间复杂度O(范围)稳定性稳定 各大排序的比较 今天的分享就到这里感谢大家的关注和支持
