Coursera 高级数据结构与算法,北京大学
2022/6/4 1:22:24
本文主要是介绍Coursera 高级数据结构与算法,北京大学,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
排序算法
着重注意研究排序算法的稳定性 : 一个排序算法是稳定的,意即有相同权值的元素在排序前后键值的相对关系不变
-
插入排序
每个新添加的元素在之前的已排序子序列中找到自己的位置并插入
算法是稳定的 (若新添加的元素与已排序子序列中的某些元素权值相等,插到这段元素末尾即可)
时间复杂度 \(O(N^2)\) -
插入变种:Shell 排序 (不稳定)
采用 Hibbard 增量序列的 Shell 排序时间复杂度可以达到 \(O(N^{1.5})\)
采取特殊的增量序列甚至可以达到 \(O(NlogN)\) -
选择排序
依次选择待排序序列中的最小元素并直接插入已排序序列的尾部直到所有元素处理完
算法 不稳定 :因为具体在算法实现时,我们采取的方法是给每个位置选择当前元素最小的,即找到合适的元素后将其与当前位置上的元素进行swap
例如这样一个序列5 8 5 2 9
第一次交换是在位置 \(1\) 的 \(5\) 与序列中的最小元素 \(2\) 交换,交换过后两个 \(5\) 的相对顺序被破坏
不使用swap
操作的选择排序可以是稳定的
时间复杂度 \(O(N^2)\) -
堆排序
一次建堆 \(O(N)\) \(+\) \(N\) 次取堆顶 \(O(logN)\)
总时间复杂度 \(O(NlogN)\) -
冒泡排序
每次交换存在的逆序对直到不存在逆序对为止
可以证明对于完全逆序序列时时间复杂度是 \(O(N^2)\)
冒泡排序是 稳定的 -
快速排序
算法思想:分治 \(+\) 归并
通过一趟排序将数组分成两个部分,其中一个部分都比轴值小,另一个部分都比轴值大,然后再分别对这两部分进行递归操作,最后就可以达到全部有序
选择好的轴值可以优化快速排序的效率
算法不稳定,时间复杂度稳定在 \(O(NlogN)\) 很优越
代码:18 年 7 月写的,好怀念!
void qsort(int l, int r) { int mid = num[(l + r) / 2]; int i = l, j = r; while(i <= j) { while(num[i] < mid) i++; while(num[j] > mid) j--; if(i <= j) { swap(num[i], num[j]); i++; j--; } } if(i < r) qsort(i, r); // i ~ r 的所有元素都大于 mid if(l < j) qsort(l, j); // l ~ j 的所有元素都小于 mid }
这篇关于Coursera 高级数据结构与算法,北京大学的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享