基于比较排序的算法的性能是有上限的，大部分人都知道是nlgn，但是为什么多年的研究都突破不了nlgn呢，其实数学早已给出了答案。
每一种基于比较的排序算法，都可以看作一棵二叉排序树，叶子节点代表每一种排序结果，算法的不同就体现在构造这棵树的不同方法。叶子到树根的距离表示比较次数，也就是时间。由二叉树的性质，2^h>=k，k为叶子节点，且所有的排序结果有n!个，所以h>=lg(n!)，即T(n)>=lg(n!)，由斯特林公式，可以得到，T(n)>=O(nlgn)，或者近似地看，lg(n!)=lgn+lg(n-1)+…+lg1，复杂度就是nlgn，这便是问题所在。
但是不论是什么排序算法，都不可能小于O(n)，因为你至少每个元素看一眼都是线性时间。又因为上次说到，lgn接近常数级，所以nlgn的排序算法已经很优秀了。
同为nlgn，为什么快排的性能要优于归并排序呢，这是因为除了比较，还有一个开销便是搬动元素，归并排序需要大量读入写出，而快排只需要把比pivot大的向后挪就行了。但是归并排序很适合外部排序，因为一次将两个队首元素读入就OK了。
排序算法 排序算法冒泡排序鸡尾酒排序选择排序插入排序希尔排序归并排序快速排序堆排序 先说一些 关于排序的定义吧 排...
关于排序和二分查找的几个必知必会的代码实现排序实现归并排序、快速排序、插入排序、冒泡排序、选择排序编程实现O(n)...
1. 冒泡 -(void)maopao{ int i,j,temp, arr[8] = {8,5,4,6,1,...
这个很早就想开始自己整理一下，但是一直在自学，导致耽误了，但是昨天晚上突然一下子忘记了什么是计数排序，干脆复习一波...
首先：排序从大的方面可以分为内排序和外排序。 第一个问题： 什么是内排序？ 内部排序：待排序记录存放在计算机随机存...
今天我们中级班课堂讲到了关于排序，排序是一个很简单容易操作的一个技术，这是在台湾版的焦点书籍上常常提到的。很实用的...
基于比较排序的算法的性能是有上限的，大部分人都知道是nlgn，但是为什么多年的研究都突破不了nlgn呢，其实数学早...
排序的方法非常多，先看维基百科中的一张关于排序算法的表，这里列了50多种排序方式。 内排序和外排序的概念 内部排序...
关于算法： 基础技巧：分治、二分、贪心排序算法：快速排序、归并排序、计数排序搜索算法：回溯、递归、深度优先遍历，广...
十二生肖趣谈（3） 关于十二生肖的排序 关于十二生肖的排序，民间有各种各样的传法。真实的十二生肖排序，可是大有学问...
本文标题：关于排序
本文链接：https://www.haomeiwen.com/subject/einniltx.html
网友评论