数据结构几种排序算法的时间和空间复杂度总结

数据结构几种排序算法的时间和空间复杂度总结

算法语言 3年前 (2014-12-30) 浏览: 1516 评论: 4

1.插入排序:每次将一个待排的记录插入到前面的已经排好的队列中的适当位置。 ①.直接插入排序 直接排序法在最好情况下(待排序列已按关键码有序),每趟排序只需作1次比较而不需要移动元素。所以n个元素比较次数为n-1,移动次数0。 最差的情况下(逆序),其中第i个元素必须和前面的元素进行比较i次,移动个数i+1,所以总共的比较次数 比较多,就不写出来了 总结:是一种稳定的排序方法,时间复杂度O(n^2),排序过程中只要一个辅助空间,所以空间复杂度O(1) ②.希尔排序 缩小增量排序,对直接插入排序的一种改进 分组插入方法。 总结:是一种不稳定的排序方法,时间复杂度O(n^1.25),空间复杂度O(1) 2.交换排序 ①.冒泡排序 最好的情况下,就是正序,所以只要比较一次就行了,复杂度O(n) 最坏的情况下,就是逆序,要比较n^2次才行,复杂度O(n^2) 总结:稳定的排序方法,时间复杂度O(n^2),空间复杂度O(1),当待排序列有序时,效果比较好。 ②.快速排序 通过一趟排序将待排的记录分割成独立的两部分,其中一部分记录的关键字均比另一个部分的关键字小,然后再分别对这两个部分记录继续进行排序,以达到整个序列有效。 总结:在所有同数量级O(nlogn)的排序方法中,快速排序是性能最好的一种方法,在待排序列无序时最好。算法的时间复杂度是O(nlogn),最坏的时间复杂度O(n^2),空间复杂度O(nlogn) 3.选择排序 ①.直接选择排序 和序列的初始状态无关 总结:时间复杂度O(n^2),无论最好还是最坏 ②.堆排序 直接选择排序的改进 总结:时间复杂度O(nlogn),无论在最好还是最坏情况下都是O(nlogn) 4.归并排序 总结:时间复杂度O(nlogn),空间复杂度O(n) 5.基数排序 按组成关键字的各个数位的值进行排序,是分配排序的一种。不需要进行排码值间的比较就能够进行排序。 总结:时间复杂度O(d(n+rd)) 总总结: n比较小的时候,适合 插入排序和选择排序 基本有序的时候,适合 直接插入排序和冒泡排序 n很大但是关键字的位数较少时,适合 链式基数排序 n很大的时候,适合 快速排序 堆排序 归并排序 无序的时候,适合 快速排序 稳定的排序:冒泡排序 插入排序 归并排序 基数排序 复杂度是O(nlogn):快速排序 堆排序 归并排序 辅助空间(大 次大):归并排序 快速排序 好坏情况一样:简单选择(n^2),堆排序(nlogn),归并排序(nlogn) 最好是O(n)的:插入排序 冒泡排序

[转载]各种字符串Hash函数

[转载]各种字符串Hash函数

算法语言 3年前 (2014-12-11) 浏览: 114 评论: 0

常用的字符串Hash函数还有ELFHash,APHash等等,都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数,这些函数几乎不可能找到碰撞。 常用字符串哈希函数有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等等。  具体的代码分享  

数据结构Exam 2:Enhanced Parking Lot Simulation

数据结构Exam 2:Enhanced Parking Lot Simulation

算法语言 3年前 (2014-12-08) 浏览: 460 评论: 0

Description   This assessment tests your ability to use the STL stack adapter, the STL vector container, and the STL find algorithm to solve a problem. You are asked to finish the implementation of a program that simulates a multiple-aisle parking lot. When cars are parked bumper-to-bumper, each aisle in this parking lot can hold three cars. There are five aisles in the parking lot. It is your task to finish the implementation of the simulation that processes the vehicle arrivals and departures. The goal of the simulation is to keep track of and report how many times individual cars are moved while handling the departure of other cars. The simulation also displays an alphabetized list of all the cars that visited the parking lot during the simulation.       答案:main.cpp

数据结构-传染病问题

数据结构-传染病问题

算法语言 3年前 (2014-11-30) 浏览: 157 评论: 1

Description This assignment asks you to finish the implementation of a program that assesses the level of infection in a tissue sample. You are given data representing a rectangular tissue sample, overlaid with a grid. Certain portions of the tissue are infected; others are not. Your goal is to help assess the extent of the infection by writing a program that, given the coordinates of a colony of infection, can determine its size. A typical use of the program follows. The user interacts with the program only through command-line arguments. The user supplies to the program a data filename and the coordinates of a cell in the grid. The coordinates are specified by row and then column, both starting at zero. The program calculates the extent of infection at that coordinate and outputs a two-dimensional representation of the tissue sample. Figure 1 depicts(叙述) the execution(执行) of the program. 代码

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

切换登录

注册