各种排序(二)
2019-12-08 16:00:44来源:博客园 阅读 ()
各种排序(二)
- 本文中 \(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);
上张图理解一下:
可用于求逆序对的个数。
堆排序
不想写,咕咕咕。
快速排序
原文链接:https://www.cnblogs.com/poi-bolg-poi/p/12006080.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 关于各种不同开发语言之间数据加密方法(DES,RSA等)的互通的 2020-06-07
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- 排序汇总 2020-05-05
- 二叉排序树 2020-05-02
- 排序算法之快速排序代码c++ 2020-04-01
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash