锐客网

  1. 首页 > 睿知 > it技术 > >

二叉索引树java代码 二叉搜索树代码( 六 )

代码IT技术


希尔排序 （shell sort）— O(n log n) 如果使用最佳的现在版本
Comb sort — O(n log n)
堆排序 （heapsort）— O(n log n)
Smoothsort — O(n log n)
快速排序 （quicksort）— O(n log n) 期望时间, O(n2) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最外情况时间, 需要 额外的 O(n + k) 空间, 也需要找到最长的递增子序列（longest increasing subsequence）
不实用的排序算法
Bogo排序 — O(n × n!) 期望时间, 无穷的最坏情况 。
Stupid sort — O(n3); 递回版本需要 O(n2) 额外记忆体
Bead sort — O(n) or O(√n), 但需要特别的硬体
Pancake sorting — O(n), 但需要特别的硬体
排序的算法
排序的算法有很多，对空间的要求及其时间效率也不尽相同 。下面列出了一些常见的排序算法 。这里面插入排序和冒泡排序又被称作简单排序 ， 他们对空间的要求不高，但是时间效率却不稳定；而后面三种排序相对于简单排序对空间的要求稍高一点 ， 但时间效率却能稳定在很高的水平 。基数排序是针对关键字在一个较小范围内的排序算法 。
插入排序
冒泡排序
选择排序
快速排序
堆排序
归并排序
基数排序
希尔排序
插入排序
插入排序是这样实现的：
首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"） 。
从原数列中取出一个数，将其插入"有序列表"中 ， 使其仍旧保持有序状态 。
重复2号步骤，直至原数列为空 。
插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现 。它借助了"逐步扩大成果"的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度 。
冒泡排序
冒泡排序是这样实现的：
首先将所有待排序的数字放入工作列表中 。
从列表的第一个数字到倒数第二个数字 ， 逐个检查：若某一位上的数字大于他的下一位 ， 则将它与它的下一位交换 。
重复2号步骤，直至再也不能交换 。
冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法 。
选择排序
选择排序是这样实现的：
设数组内存放了n个待排数字，数组下标从1开始 ， 到n结束 。
i=1
从数组的第i个元素开始到第n个元素 ， 寻找最小的元素 。
将上一步找到的最小元素和第i位元素交换 。
如果i=n－1算法结束，否则回到第3步
选择排序的平均时间复杂度也是O(n2)的 。
快速排序
现在开始，我们要接触高效排序算法了 。实践证明，快速排序是所有排序算法中最高效的一种 。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了 。这是一种先进的思想，也是它高效的原因 。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较 。但查找数据得另当别论了 。
堆排序
堆排序与前面的算法都不同，它是这样的：
首先新建一个空列表 ， 作用与插入排序中的"有序列表"相同 。
找到数列中最大的数字 ， 将其加在"有序列表"的末尾，并将其从原数列中删除 。
重复2号步骤，直至原数列为空 。

推荐阅读


上一篇：html5具有那些优势，html5有哪些新特性和优点

下一篇：网站服务器怎么关闭 在服务器怎么关闭ie