写一个快排序，堆排序需要多少时间？
排序，作为计算机算法的基础知识之一，是每个程序员必备的技能之一，也许你不经常自己写排序，但是，如果自己写，试试需要多长时间，完整，正确的写好排序了？最简单的莫过于冒泡，选择排序。说白了，排序，莫过于三部走，一是如何遍历，二是比较，三是交换。其中遍历是关键！
下面，对常用的快排序和堆排序进行实现，争取5分钟只能完成一个算法的书写。天下武功，唯快不破！快速实现而熟练的实现是一个程序员基本功底的体现。
如何最简单，最快，而正确的实现了？那就是对10以内的整数排序，是最快的，最能看到效果的。首先了明确输入和输出。记住快排序的思想是找一个标杆，让后左右开工，分别找比标杆大小的进行交换。确定新的区间，然后递归实现。话不多说，开始：需要设计两个方法，一个实现一趟的操作，一个递归调用，完事。一下为java实现：（只要思路清晰，什么语言实现都无关紧要啦！）计时开始！
1 2 /** 3 * filename：TestQuickSortS.java 4 * CopyRight： 5 * Date：2013-11-21 6 * Copyright JanneLee Corporation 2013 7 * Copyright 8 * version 1.0 9 */ 10 11 package com.lee.sort; 12 13 14 /** 15 * Description： 16 * @author: JanneLee@gmail.com 17 * @date:2013-11-21 下午02:03:47 18 * @version:1.0 19 */ 20 21 public class TestQuickSortS { 22 private int Partion(int arr[],int low,int high){ 23 int pivotkey=arr[low]; 24 while(low<high){ 25 while(low<high&&arr[high]>=pivotkey){ 26 --high; 27 } 28 arr[low]=arr[high]; 29 while(low<high&&arr[low]<=pivotkey){ 30 ++low; 31 } 32 arr[high]=arr[low]; 33 } 34 arr[low]=pivotkey; 35 return low; 36 } 37 38 public void QuickSort(int arr[],int low,int high) { 39 if(low<high){ 40 int pivot=Partion(arr, low, high); 41 QuickSort(arr, low, pivot-1); 42 QuickSort(arr,pivot+1,high); 43 } 44 } 45 /** 46 *Description：[the test code] 47 *@author: JanneLeeMAC@gmail.com 48 *@date:2013-11-21 下午02:09:36 49 *@version: 1.0 50 */ 51 public static void main(String args[]) { 52 int arr[]={2,3,1,4,5}; 53 TestQuickSortS s = new TestQuickSortS(); 54 s.QuickSort(arr, 0, arr.length-1); 55 for(int i=0;i<arr.length;++i){ 56 System.out.print(arr[i]+" "); 57 } 58 } 59 }
事实证明，这次没有超过5分。nice啊，不过，只能对整数排序，似乎不太爽，还有浮点，字符串等等啊。c++中有模板非常的棒，java中可以借助泛型，不过java中有Object类，还有一个非常爽的Compareable接口，好了，有了比较的工具。那就再改进一下比较方式呗。动手：
package com.lee.sort; public class TestQuickSort { @SuppressWarnings("unchecked") private static int Partion(Object [] arr,int low,int high){ Object pivotkey=arr[low]; while(low<high){ while(low<high&&((Comparable<Object>)arr[high]).compareTo((Comparable<Object>)pivotkey)>=0){ --high; } arr[low]=arr[high]; while(low<high&&((Comparable<Object>)pivotkey).compareTo((Comparable<Object>)arr[low])>=0){ ++low; } arr[high]=arr[low]; } arr[low]=pivotkey; return low; } public static void QuickSort(Object arr[],int low,int high){ if(low<high){ int pivot=Partion(arr, low, high); QuickSort(arr, low, pivot-1); QuickSort(arr, pivot+1, high); } } public static void main(String args[]){ Object arr[]={1,3,4,2,0,-5,6,7}; // Object arr[]={1.1,3.3,4.2,2.2,0.1,-5.0,6.99999,7.0}; // Object arr[]={"how","are","you","i","am","fine","thanks","!"}; // Object arr[]={"123","432","213","124","a123","432","23412","adfa"}; QuickSort(arr,0,arr.length-1); for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+" "); } } }
这次感觉是不是更爽了啊，哈哈。那就接着开始堆。基本的思想也是一样的，先简单写出来，再进行调整，堆是一颗完全二叉树。比较的规则是老子比两个儿子都大，或者老子比两个儿子都小。主要是遍历的技巧性。要先知道怎么调整一个堆，然后开始构造，不断的调整。也就是一个调整的方法，一个构造的方法，话不多说，开始：
1 package com.lee.sort; 2 3 public class TestHespSortS { 4 private void HeapAdjust(int arr[],int start,int end){ 5 int temp=arr[start]; 6 int i=2*start+1; 7 while(i<=end-1){ 8 if(i<end-1&&arr[i]<arr[i+1]){ 9 ++i; 10 } 11 if(i<end-1&&temp<arr[i]){ 12 arr[start]=arr[i]; 13 start=i; 14 i=start+1; 15 }else { 16 break; 17 } 18 } 19 arr[start]=temp; 20 } 21 public void HeapSort(int arr[]) { 22 int len=arr.length; 23 for(int i=(len>>1)-1;i>=0;--i){ 24 HeapAdjust(arr, i,len); 25 } 26 int temp=0; 27 while(len>0){ 28 temp=arr[0]; 29 arr[0]=arr[len-1]; 30 arr[len-1]=temp; 31 HeapAdjust(arr, 0, --len); 32 } 33 } 34 public static void main(String sags[]){ 35 int arr[]={1,3,2,4,6,5}; 36 TestHespSortS s = new TestHespSortS(); 37 s.HeapSort(arr); 38 39 for(int i=0;i<arr.length;++i){ 40 System.out.print(arr[i]+" "); 41 } 42 } 43 }
丫的，堆排序就是麻烦，都写了10几分钟。主要是各种边界的问题。同样，写出适合跟多种类的堆排序。如下：
package com.lee.sort; public class TestHeapSort{ public static void main(String args[]){ Object arr[]={1,3,4,2,6,-5,6,7}; //最开始测试数组 // Object arr[]={1.1,3.1,4.0,2.5,6.2,-5.2,6.2,7.2}; //最开始测试数组 // Object arr[]={"we","are","the","best","one","In","the","china"}; //最开始测试数组 HeapSort(arr); for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+" "); } } @SuppressWarnings("unchecked") public static void HeapAdjust(Object []arr,int start,int end){ Object temp=arr[start]; int i=2*start+1; while(i<=end-1){ if(i<end-1&&((Comparable<Object>)arr[i]).compareTo((Comparable<Object>)arr[i+1])<0){ ++i; } if(((Comparable<Object>)temp).compareTo(((Comparable<Object>)arr[i]))<0){ arr[start]=arr[i]; start=i; i=2*start+1; }else{ break; } } arr[start]=temp; } public static void HeapSort(Object []arr) { int n=arr.length; for(int i=(n/2-1);i>=0;i--){ HeapAdjust(arr, i, n); } Object tempObject=null; while(n>0){ tempObject=arr[0]; arr[0]=arr[n-1]; arr[n-1]=tempObject; HeapAdjust(arr, 0, --n); } } }
要牛，无他，但手熟尔。