最快排序和2分查找的实现

2， 循环查找未排序的数组，直到整个数组排序。 这需要2个嵌套的循环，意味着它的效率是O(n^2);

之所以插入排序的效率如此之地，是因为要找出整个数组中最小的数据，需要遍历整个数组的元素。

而插入排序聪明就聪明在它不查找整个数组最小、次小?的元素，而是每次仅仅把小于某个元素的值移到一边，通过迭代最终自动实现排序。这就大大节约了排序所需的计算步骤。

快速排序算法的理论：

1， 如果S中的元素个数是0或者1，那么返回。 2， 选取S中的任一元素v，称为中心点。

3， 将S集合中的元素分为2个部分：L={小于pivot 的元素+ pivot }和R={大于或者等于pivot的元素}。 4， 返回L和R。

我们使用Java使用的是就地排序的方式，因此不需要返回值。

因为Java是一种可以修改变量的语言，用函数式语言的术语来说，就是有“副作用”。我们利用这个副作用直接修改作为参数的Array，不需要返回值。

代码：

/** by 沈东良/良少 http://blog.csdn.net/shendl/ * 快速排序，有副作用 从小到大 * @param array * @param start

* @param end这是最后一个元素的索引，第一次调用应该是array.length-1 */

public static void quickSort(int[] array,int start,int end){ //有可能造成start>end 因为递归调用时j+1，可能引起j比end还

大1。 另外如果数组是空的，或者输入错误也会出现这种情况 if(end<=start){ return; }else {

//取中间元素为中心点，然后移到最右边 int sign=(start+end)/2; int tmp=array[end]; array[end]=array[sign]; array[sign]=tmp; int j=start;

for(int i=start;i<=end-1;i++){

//小于的元素和标记互换，等于的不能互换，否则会形成死循环 if(array[i]

//把标记元素和第一个>=它的元素位置互换，这样数组就分成2个部分，一个部分比中心值小，一个部分比中心值大。 tmp=array[j]; array[j]=array[end];

array[end]=tmp;

quickSort(array,start,j); quickSort(array,j+1,end); } }

Java的Arrays类也使用快速排序算法进行排序。但它的代码写得像天书一样。

提高快速排序算法执行效率的主要方法是对中心点进行检测，希望选中的中心点有更大的概率是整个数组的中值。

我的实现中简单的选择数组中间的值作为中心点，一般来说这样的选择效率还是不错的。

注意上面的一项实现技术，我们使用把中心数据元素移到数组最后的方式实现了数组的就地比较。这是比较常用的技术，把数据移到数组的最前面或者最后面，方便比较数据。

另外，我的Java快速排序代码使用了“副作用”，而在纯函数式语言，如Haskell,ErLang中是没有“副作用”的，也就是说变量不可以重新赋值。此时就需要返回值，每次都创建新的子数组。但函数式语言的数组处理功能很强，也会做很多性能优化，因此函数式语言实现快速排序代码更加简单，没有“副作用”，也更加数学化。

JDK使用二分搜索和快速排序算法实现搜索和排序，足见上述两个算法的性能优势。