Chpater 10: Sorting
Internal Sort:
Bubble O(n2)
Selection O(n2)
Insertion O(n2)
Shell O(nlogn)
Merge O(nlogn)
Heap O(nlogn)
Quick Sort O(nlogn)
Tree Sort(BST) O(nlogn)
Linear Sorting:
Counting Sort O(n)
BUcket Sort O(n)
Radix Sort O(n)
External Sorting:
K chunks of data need to be sorted and a K-way merge has to be completed. Assembly Line
Problems:
pro22: Nearly Sorted. Given a array of n elements, each which is at most K positions from its target position, devise an algorithm that sort in O(nlogK).
Insert the first K elements into a binary heap of size K. Insert the next element from the array into the heap, and delete the minimum element from the heap.\
pro35: Nuts and Bolts. We are given a box which contains bolts and nuts. Assume that there are n nuts and n bolts and that each nut matches exactly one bolt. By trying to match a bolt and a nuts we can see which one is bigger, but we cannot compare two bolts or two nuts directly.
We can use divide-and-conquer to solve. Pick a random bolt B[i], Using this bolt to rearrange the array of nuts into three groups of elements:
- Nuts smaller than B[i]
- Nuts matches B[i]
- Nuts larger than B[i]
最新文章
- 云计算下PAAS的解析一
- DevOps
- plist文件
- UWP 拉勾客户端
- paip.hibernate save 失败的解决
- 选择排序的MPI实现
- C++内存分配的五种方法
- HDU 1172 猜数字(DFS)
- javascript获取当前url中的參数
- lpc1788IO口模拟IIC
- C# 打开文件夹和保存文件夹
- Chapter 2 User Authentication, Authorization, and Security(10):创建包含数据库
- JDBC事务控制
- 工具类:mybatis中使用Threadlocal开启session及关闭session
- missing 1 required positional argument: 'on_delete'报错解决方案
- Reactnative——安装React Navigation后无法运行项目
- DOM对象,控制HTML元素
- python全栈开发day75-用户注册页面ajax实现,用户头像上传、预览、展示
- Tomcat启动分析(转自:http://docs.huihoo.com/apache/tomcat/heavyz/01-startup.html)
- source tree使用经验