各种排序(二)
程序员文章站
2022-07-02 12:31:54
本文中 $n$ 代表着待排序序列的长度。 算法是否稳定:若 $a_i = a_j \ , \ i 1; merge(l,mid),merge(mid+1,r); mergesort(l,r,mid);return;//递归,先给小区间排序后大区间。 } merge(1,n); 上张图理解一下: 可用 ......
- 本文中 \(n\) 代表着待排序序列的长度。
- 算法是否稳定:若 \(a_i = a_j \ , \ i < j\),排序后若\(i < j\) 则稳定,反之不稳定。(可能有点歧义凑活看)
归并排序
用了二分的思想。
在递归的过程中不断将需要排序的区间缩小,使小区间有序后,再使大区间变得有序会简单很多。
最差时间复杂度:\(o(nlogn)\)
最优时间复杂度:\(o(nlogn)\)
平均时间复杂度:\(o(nlogn)\)
算法是否稳定:是
void mergesort(int l,int r,int mid) {//将[l,r]区间排好序 int i=l,j=mid+1,cnt=0;//[l,mid]与[mid+1,r]已经有序了,所以可以进行下面的操作。 while(i<=mid&&j<=r) temp[++cnt]=a[i]<=a[j]?a[i++]:a[j++]; while(i<=mid) temp[++cnt]=a[i++]; while(j<=r) temp[++cnt]=a[j++]; for(int i=l;i<=r;++i) a[i]=temp[i-l+1]; } void merge(int l,int r) {//不断将区间缩小 if(l==r) return; int mid=(l+r)>>1; merge(l,mid),merge(mid+1,r); mergesort(l,r,mid);return;//递归,先给小区间排序后大区间。 } merge(1,n);
上张图理解一下:
可用于求逆序对的个数。
堆排序
不想写,咕咕咕。
快速排序
上一篇: pymysql连接
下一篇: 18.JAVA-pull解析XML
推荐阅读
-
全国好的二本计算机专业排名:学计算机去哪个二本大学好?
-
百度浏览器扫描二维码以便加入会员或者查看详情
-
四川二本压线的公办大学及分数线-理科二本压线生填报学校(2021高考)
-
Android自定义View简易折线图控件(二)
-
2021适合捡漏的二本公办大学:录取分数线下降的大学有哪些?
-
甘肃省师范类二本院校有哪些?甘肃二本师范最低多少分?(附2021最新排名)
-
2021年山东10所好大学排名:山东实力最强二本大学
-
全国二本公办本科大学-公办本科最低分数线的学校(2021理科参考)
-
400分左右的公办二本大学有哪些?2021高考公立二本学校最低多少分?
-
sqlServer使用ROW_NUMBER时不排序的解决方法