企业需要做网站吗,哪里有做网站服务商,合众商道网站开发,为什么教育网站做的都很烂比较排序
插入排序#xff08;斗地主摸牌就是一个插入排序#xff09;
单纯的插入排序也叫直接插入排序
时间复杂度#xff1a;
最好O(n)最坏O(n^2)
过程
先写单趟#xff0c;再写整体
依次比较#xff0c;如果大于就往后挪动#xff0c;否则就退出循环#xff0c;插入数…比较排序
插入排序斗地主摸牌就是一个插入排序
单纯的插入排序也叫直接插入排序
时间复杂度
最好O(n)最坏O(n^2)
过程
先写单趟再写整体
依次比较如果大于就往后挪动否则就退出循环插入数据
void InsertSort(int* a, int n)
{for (int i 1; i n; i){int end i-1;int tmp a[i];//讲tmp插入到[0,end]区间保证有序//和前一次顺序有关系 所以最好的时候就是O(n)while (end 0){if (a[end] tmp){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
}希尔排序 分组插排
希尔排序也是一个插入排序不过他对原来的插入排序做了优化
时间复杂度
O(n^1.3)
过程
1.预排序 --目标 数组接近有序
2.直接插入排序
//希尔排序
//简化写法
//多组并排
//时间复杂度O(n^1.3)
void ShellSort(int* a, int n)
{int gap n;//gap 1while (gap 1){//gap / 2;gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}时间复杂度的分析
希尔排序是一个很复杂的排序他的时间复杂度是一个增量式序列问题如果我们只算边界的话它可以约等于n,但是他的中间应该是一个上升和下降的曲线。但是该怎么证明嘛这里没有明确的回答涉及到了一些数学问题。正常分析可能会认为是n*logn,但是局部的结论认为他是n^1.3次方这也是他复杂的原因因为它没有一个明确的证明过程可以记一下结论。这里如果非要深究的话和gap取值是有关的关键是gap的取值不是定值而是一直在变化。目前比较认可的取值是n/2和n/31。如果有兴趣的话可以研究一下但是这就涉及到一些数学领域的问题啦。
直接选择排序
时间复杂度
O(n^2)
直接选择排序很简单同时也是一个最烂的排序。
为什么说这是一个最烂的排序呢 因为他的时间复杂度无论是最好还是最坏的情况都是O(n^2)他的每一次排序都是从新选择和前面的排序没有关联。
选择排序和插入排序的关系就像一个是斗地主的时候边摸边排序一个是等发完所有的牌再去给牌排序。
//选择排序
//时间复杂O(n^2)
//最坏O(n^2)
//最好O(n^2)
//最垃圾的算法 他的前一次顺序调整和下一次没有关系 无论什么时候都是一个等差数列相加
void SelectSort(int* a, int n)
{int left 0, right n - 1;while (left right){int min left, max left;//单躺for (int i left 1; i right; i){if (a[i] a[max]){max i;}if (a[i] a[min]){min i;}}Swap(a[left], a[min]);//left 和 max重叠if (left max){max min;}Swap(a[right], a[max]);left;right--;}
}冒泡排序默认升序
时间复杂度
O(n^2)
冒泡排序属于交换排序的一种
不做优化的情况下时间复杂度都是O(n^2)做了优化的情况下最好的情况是O(n)
两两交换一次遍历下来肯定能能把最大值排好他和插入排序也是一个等差数列相加。
那冒泡排序和插入排序那一个更好呢答案是插入排序。
虽然都属于一个量级但是在数据是部分有序和接近有序的时候插入排序会更快比如数据13245。
大家可能不理解不是时间复杂度都一样了吗为啥还有更优的说法呢这里时间复杂只是一个量级标准就像我们都是在校大学生但是大学生就没有区别吗有的人早起备考四六级考研有的人天天宿舍打游戏通宵熬夜。出去讲我们都会说自己是大学生这是一个量级标准但是你们还是很有区别。如果你非要从时间复杂度为O(n^2)选择一个排序那插入排序绝对是YYDS。
冒泡排序其实更多的是教学意义实际中不太会用他。
堆排序
时间复杂度
O(n*logn)
结论
排升序建大堆排降序建小堆
这里排序建堆是有点反正常的。这里采用的是从下向上逐渐建堆类似于后序遍历。建好堆(升序为例)从堆顶取数据放到末尾再对剩余的数组建堆(向下调整)重复操作。这里建堆采用向上调整和向下调整都行这里推荐使用向下调整一个函数搞定这里排序见大堆还是小堆其实不是绝对这里推荐的是最佳的解法如果非要使用排升序建小堆也不是不能实现。
//向下调整
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[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}
//堆排序
//时间复杂度O(n*logn)
void HeapSort(int* a, int n)
{//模拟插入建堆//排升序 建大堆//排降序 减小堆//向下调整建堆 效率更高 一般使用向下调整建堆 o(n - log n)for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}int end n - 1;//这里的时间复杂度计算和向上建堆一样 N*logNwhile (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}快速排序
时间复杂度
O(n*logn)
1962年由Hoare提出的一种二叉树结构的交换排序它的基本思想是选基准值/关键值把他放在一个正确的位置(比他小的放在左边比它大的放在右边)递归该过程。升序为例
结论以左边为基准值先从右边找相遇位置一定是比key小的,以右边为基准值先从左边找相遇位置一定是比key大的。
这里分析是两种情况右边先遇到左边左边先遇到右边。数据分析下就可以的出来很简单。
如果你是以左边为基准值先从左边找相遇位置一定是比key小的,
这个相遇位置不一定是比key小这里随便找一个反例就可以得出来。
最原始的快排有个致命问题就是key值的选择如果固定在有序的时候就是最坏的情况。递归太深了会栈溢出。所以这里提供了两种解决方案三数选中和随机选key。这里更推荐三数选中他完美解决了有序的情况。
这里有三种实现快速排序的方法第一种就是最纯粹的Hoare版本但是Hoare版本不太好理解容易写错。所以就有大佬进行改编衍生出了挖坑法和前后指针法。这种方法只是对单趟的遍历进行了改编本质上还是快排的思想还是递归时间复杂度也是属于O(n*logn)。这里推荐使用前后指针的方法因为这个方法比较简单而且不容易写错。
这里介绍的都是递归快排的写法但是递归就有一个致命问题那就是递归太深会栈溢出这其实不是代码的问题是编译器的问题。所以我们还要学习非递归的写法。
三数选中
//选取中间的数
int GetMiduimNum(int* a,int left, int right)
{//int mid left right / 2; 错误写法int mid left (right - left) / 2;if (a[left] a[mid]) // 2 3{if (a[right] a[mid])//4 3{return mid; // 2 3 4}else if(a[left] a[right]){return left;}else{return right;}}else //a[left] a[mid]{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return right;}else{return left;}}
}Hoare
快速排序 Hoare写法 最简单最原始版本
最坏情况O(n^2)
最好情况O(n*logn)
时间复杂度n*logn 加了优化就可以解决有序的情况
int Part1Sort(int* a, int left, int right)
{//结束条件if (left right){return;}int begin left, end right;//随机选Key 版本//int randi left (rand() % (right - left));//Swap(a[left], a[randi]);//三数选中int mid GetMiduimNum(a, left, right);Swap(a[left], a[mid]);int key left;//left 这是一种错误写法 千万不要写while (left right){//右边找小while (left end a[right] a[key]){right--;}//左边找大while (left right a[left] a[key]){left;}Swap(a[left], a[right]);}Swap(a[key], a[right]);key left;return key;
}
//区间优化 减少递归次数 主要是递归深度 对性能影响不大
void QuickSort(int* a, int left, int right)
{//结束条件if (left right){return;}if (right - left 1 10){int keyi Part1Sort(a, left, right);//begin key -1 hole key1 end//递归QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);}else{InsertSort(a left, right - left 1);}
}挖坑法
//挖坑法 不再有左边先走还是右边先走 就是挖坑填坑 大思路不变
int Part2Sort(int* a, int left, int right)
{int begin left, end right;//三数选中int mid GetMiduimNum(a, left, right);Swap(a[left], a[mid]);int hole left;int key a[left];while (left right){while (left end 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;
}
//区间优化 减少递归次数 主要是递归深度 对性能影响不大
void QuickSort(int* a, int left, int right)
{//结束条件if (left right){return;}if (right - left 1 10){int keyi Part2Sort(a, left, right);//begin key -1 hole key1 end//递归QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);}else{InsertSort(a left, right - left 1);}
}前后指针
//前后指针
int Part3Sort(int* a, int left, int right)
{int begin left, end right;//三数选中int mid GetMiduimNum(a, left, right);Swap(a[left], a[mid]);int prev left, cur left 1;int keyi left;while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[cur], a[prev]);}cur;}Swap(a[prev], a[keyi]);keyi prev;return keyi;
}
//区间优化 减少递归次数 主要是递归深度 对性能影响不大
void QuickSort(int* a, int left, int right)
{//结束条件if (left right){return;}if (right - left 1 10){int keyi Part3Sort(a, left, right);//begin key -1 hole key1 end//递归QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);}else{InsertSort(a left, right - left 1);}
}递归改非递归有两种思路
直接改循环 斐波那契额数列使用栈辅助快排
非递归写法
栈里面取一段区间单排分割子区间入栈子区间只有一个值或者不存在就不入栈。这里其实就是在模拟递归而已不理解的话可以画个递归展开图。
快排其实还有一个非常致命的问题就是如果存在大量重复的问题他的效率会变得很低这个时候三数选中和随机选key也不管用。这个时候需要一个三路划分
//非递归写法
void QuickSort(int* a, int left, int right)
{ST stack;STInit(stack);STPush(stack, right);STPush(stack, left);while (!STEmpty(stack)){int begin STTop(stack);STPop(stack);int end STTop(stack);STPop(stack);//先单趟int keyi Part3Sort(a, begin, end);//begin keyi-1 keyi keyi1 endif (keyi 1 end){STPush(stack, end);STPush(stack, keyi1);}if (begin keyi -1){STPush(stack, keyi-1);STPush(stack, begin);}}STDestroy(stack);
}总结
快排类似于一个二叉树的前序遍历就像先找到根在遍历左子树和右子树。快排与普通的排序相比时间复杂度已经有了质的提升。但是快排也不是一个简单的排序。它有许多版本最原始的就是Hoare版本也是很难理解的。于是后面的挖坑法和前后指针法及诞生了。这里三种方法都要学习但是平常写建议前后指针这是一种比较简单的方法(如果你能理解)
归并排序
归并排序类似与一个二叉树的后序遍历要对一段数字排序先找到这段数字的两个有序子区间使用比较大小依次取数字进行排序。找到两个有序子区间就是一个分割归并过程。
递归实现
void _MergeSort(int* a, int begin,int end,int* tmp)
{if (begin end){return;}int mid (begin end) / 2;//[begin mid] [mid1 end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid1, end, tmp);//归并int begin1 begin, end1 mid;int begin2 mid 1, end2 end;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);_MergeSort(a, 0, n - 1,tmp);free(tmp);tmp NULL;
}非递归实现
//非递归 归并排序
void _MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc failed);return;}int gap 1;while (gap n){for (int i 0; i n; i 2*gap){int begin1 i, end1 igap-1;int begin2 igap, end2 i2*gap-1;//printf([%d %d][%d %d] , begin1, end1, begin2, end2);int j i;//修正路线/* if (end1 n){end1 end2 n - 1;begin2 n;}else if (begin2 n){end2 n - 1;begin2 n;}*/if (begin2 n){break;}else if (end2 n){end2 n - 1;}printf([%d %d][%d %d] , begin1, end1, begin2, end2);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];}//0 1 2 3memcpy(ai, tmpi, sizeof(int) * (end2-i1));}//memcpy(a, tmp, sizeof(int) * (n));printf(\n);gap * 2;}free(tmp);
}非比较排序
计数排序
时间复杂度
O(nrange)
hash映射记录坑位数字出现的次数。当范围很集中时数据为int比较适合。
局限性对于double字符串和很多其他情况无法完成。
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* CountA (int*)calloc(range, sizeof(int));//映射for (int i 0; i n; i){CountA[a[i]-min];}//排序int j 0;for (int i 0; i range; i){while (CountA[i]--){a[j] imin;}}
}总结
对于非比较排序其实还有很多比如基数排序等等但其实这些排序在实际中根本没应用而且很low不仅局限而且效率也不咋样。这里的计数排序还有点运用在某些情况他的时间复杂度是On,这已经吊打了快排这些排序。
