时间复杂度
n^2表示n的平方,选择排序有时叫做直接选择排序或简单选择排序
排序方法 | 平均时间 | 最好时间 | 最坏时间 |
桶排序(不稳定) | O(n) | O(n) | O(n) |
基数排序(稳定) | O(n) | O(n) | O(n) |
归并排序(稳定) | O(nlogn) | O(nlogn) | O(nlogn) |
快速排序(不稳定) | O(nlogn) | O(nlogn) | O(n^2) |
堆排序(不稳定) | O(nlogn) | O(nlogn) | O(nlogn) |
希尔排序(不稳定) | O(n^1.25) | ||
冒泡排序(稳定) | O(n^2) | O(n) | O(n^2) |
选择排序(不稳定) | O(n^2) | O(n^2) | O(n^2) |
直接插入排序(稳定) | O(n^2) | O(n) | O(n^2) |
O(n)这样的标志叫做渐近时间复杂度,是个近似值.各种渐近时间复杂度由小到大的顺序如下
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
一般时间复杂度到了2^n(指数阶)及更大的时间复杂度,这样的算法我们基本上不会用了,太不实用了.比如递归实现的汉诺塔问题算法就是O(2^n).
平方阶(n^2)的算法是勉强能用,而nlogn及更小的时间复杂度算法那就是非常高效的算法了啊.
空间复杂度
冒泡排序,简单选择排序,堆排序,直接插入排序,希尔排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引)
快速排序空间复杂度为logn(因为递归调用了) ,归并排序空间复杂是O(n),需要一个大小为n的临时数组.
基数排序的空间复杂是O(n),桶排序的空间复杂度不确定
最快的排序算法是桶排序
所有排序算法中最快的应该是桶排序(很多人误以为是快速排序,实际上不是.不过实际应用中快速排序用的多)但桶排序一般用的不多,因为有几个比较大的缺陷.
1.待排序的元素不能是负数,小数.
2.空间复杂度不确定,要看待排序元素中最大值是多少.
所需要的辅助数组大小即为最大元素的值.
相关推荐
学习电脑信息常用的排序算法的时间复杂度和空间复杂度
使用插入、冒泡、选择、快排、归并、堆排共6种排序算法对同一序列进行排序,统计排序所需的平均时间并比较算法在时间上的优劣。供学习使用。
算法设计与分析 一PRESETATION 仅做参考,请勿copy冲查重塔峰 排序算法性能分析 ...但注意理论上快速排序的空间复杂度较高为O(n),且最坏情况时时间复杂度也达到了O(n2)。所以快速算法也较为常用。
排序(Sorting) 是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的...本文主要介绍快速排序算法和归并排序算法的基本概念、原理以及具体的实现方法,并对这两种排序算法的时间复杂度进行分析。
常用排序算法时间复杂度、空间复杂度总结。包括:冒泡排序、快速排序、选择排序、堆排序、插入排序、Shell排序、归并排序、基数排序。
1. 掌握各种排序的基本思想。 2. 掌握各种排序方法的算法实现。 3. 掌握各种排序方法的优劣分析及花费的...根据排序函数中的核心语句,计算出每种排序方法的时间复杂度级=及空间复杂度,分析几种排序方法的优劣。
相关知识介绍(所有定义只为帮助读者理解相关概念,并非严格定义)
对各种常用的排序技术和算法进行比较,包括算法原理、适用场合、时间和空间复杂度、常见应用等。源代码+报告。
不稳定的排序算法:快速排序、希尔排序、堆排序、选择排序(简简记记::快快些些选选堆堆) 所需辅助空间最多:归并排序 所需辅助空间最少:堆排序 平均速度最快:快速排序 当n较大,则应采用时间复杂度为O(nlogn)的...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
排序算法的总结: (1)若n较小(如n≤50),可采用直接插入或直接选择排序。 当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。 (2)若文件初始状态基本有序(指...
[问题描述]:用程序实现多种排序算法 [基本要求]:利用随机函数产生随机整数(20000),对这些数据进行多种方法进行排序。...并完成这些算法的性能分析(从时间复杂度和空间复杂度两个方面进行比较分析)报告。
描述各种数据结构算法,各种排序算法的时间空间复杂度。
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
各种排序算法的程序描写与时间复杂度分析,比较,空间复杂度的分析
首先通过图表比较不同排序算法的时间复杂度和稳定性。 排序方法 平均时间 最坏情况 最好情况 辅助空间 稳定性 直接插入排序 O(n2) O(n2) O(n) O(1) 是 冒泡排序 O(n2) O(n2) O(n...
下面的算法都打包在一个应用当中,你只需要下载安装即可,里面有算法的介绍,时间复杂度,空间复杂度,代码示例 二叉树的遍历 二叉排序树 红黑树 AVL树 图的邻接表存储构成图 有向图的创建 拓扑排序-邻接矩阵存储-...