程式師世界 >> 編程語言 >> JAVA編程 >> JAVA編程入門知識 >> Java常用排序算法及性能測試集合

Java常用排序算法及性能測試集合

編輯：JAVA編程入門知識

現在再回過頭理解，結合自己的體會，選用最佳的方式描述這些算法，以方便理解它們的工作原理和程序設計技巧。本文適合做java面試准備的材料閱讀。

先附上一個測試報告：

Array length: 20000
bubbleSort : 766 ms
bubbleSortAdvanced : 662 ms
bubbleSortAdvanced2 : 647 ms
selectSort : 252 ms
insertSort : 218 ms
insertSortAdvanced : 127 ms
insertSortAdvanced2 : 191 ms
binaryTreeSort : 3 ms
shellSort : 2 ms
shellSortAdvanced : 2 ms
shellSortAdvanced2 : 1 ms
mergeSort : 3 ms
quickSort : 1 ms
heapSort : 2 ms

通過測試，可以認為，冒泡排序完全有理由扔進垃圾桶。它存在的唯一理由可能是最好理解。希爾排序的高效性是我沒有想到的；堆排序比較難理解和編寫，要有宏觀的思維。

代碼如下：

package algorithm.sort;

import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.Date;

/**
* Java常用排序算法及性能測試集合
*
* 本程序集合涵蓋常用排序算法的編寫，並在注釋中配合極其簡單的特例講解了各種算法的工作原理，以方便理解和吸收；
* 程序編寫過程中吸收了很多維基百科和別人blog上面的例子，並結合自己的思考，選擇並改進一個最容易讓人理解的寫法
*（尤其是快速排序，我覺得我寫的算法最好理解）。
* 同時包含一個集中式的性能測試和正確性測試方法，方便觀測。
* @author /link.php?url=http://blog.csdn.net/sunxing007
* 轉載請注明來自/link.php?url=http://blog.csdn.net/sunxing007
*/
public class SortUtil {
// 被測試的方法集合
static String[] methodNames = new String[]{
 "bubbleSort",
 "bubbleSortAdvanced",
 "bubbleSortAdvanced2",
 "selectSort",
 "insertSort",
 "insertSortAdvanced",
 "insertSortAdvanced2",
 "binaryTreeSort",
 "shellSort",
 "shellSortAdvanced",
 "shellSortAdvanced2",
 "mergeSort",
 "quickSort",
 "heapSort"
};
 public static void main(String[] args) throws Exception{
 //correctnessTest();
 performanceTest(20000);
 }

 /**
 * 正確性測試 
 * 簡單地測試一下各個算法的正確性 
 * 只是為了方便觀測新添加的算法是否基本正確； 
 * @throws Exception 主要是反射相關的Exception； 
 */
 public static void correctnessTest() throws Exception{
 int len = 10;
 int[] a = new int[len];
 for(int i=0; i<methodNames.length; i++){
 for(int j=0; j<a.length; j++){
 a[j] = (int)Math.floor(Math.random()*len*2);
 }
 Method sortMethod = null;
 sortMethod = SortUtil.class.getDeclaredMethod(methodNames[i], a.getClass());
 Object o = sortMethod.invoke(null, a);
 System.out.print(methodNames[i] + " : ");
 if(o==null){
 System.out.println(Arrays.toString(a));
 }
 else{
 //兼顧mergeSort，它的排序結果以返回值的形式出現；
 System.out.println(Arrays.toString((int[])o));
 }
 }
 }

 /**
 * 性能測試 
 * 數組長度用參數len傳入，每個方法跑20遍取耗時平均值； 
 * @param len 數組長度建議取10000以上，否則有些算法會顯示耗時為0； 
 * @throws Exception 主要是反射相關的Exception； 
 */
 public static void performanceTest(int len) throws Exception{
 int[] a = new int[len];
 int times = 20;

 System.out.println("Array length: " + a.length);
 for(int i=0; i<methodNames.length; i++){
 Method sortMethod = null;
 sortMethod = SortUtil.class.getDeclaredMethod(methodNames[i], a.getClass());
 int totalTime = 0;
 for(int j=0; j<times; j++){
 for(int k=0; k<len; k++){
 a[k] = (int)Math.floor(Math.random()*20000);
 }
 long start = new Date().getTime();
 sortMethod.invoke(null, a);
 long end = new Date().getTime();
 totalTime +=(end-start);
 }
 System.out.println(methodNames[i] + " : " + (totalTime/times) + " ms");
 //System.out.println(Arrays.toString(a));
 }
 }

 /**
 * 最原始的冒泡交換排序; 
 * 兩層遍歷，外層控制掃描的次數，內層控制比較的次數； 
 * 外層每掃描一次，就有一個最大的元素沉底；所以內層的比較次數將逐漸減小； 
 */
 public static void bubbleSort(int[] a){
 for(int i=0; i<a.length; i++){
 for(int j=0; j<a.length-i-1; j++){
 if(a[j]>a[j+1]){
 int tmp = a[j];
 a[j] = a[j+1];
 a[j+1] = tmp;
 }
 }
 }
 }

 /**
 * 改進的冒泡法 
 * 改進之處在於：設一個標志位，如果某趟跑下來，沒有發生交換，說明已經排好了； 
 */
 public static void bubbleSortAdvanced(int[] a){
 int k = a.length-1;
 boolean flag = true;
 while(flag){
 flag = false;
 for(int i=0;i<k;i++){
 if(a[i]>a[i+1]){
 int tmp = a[i];
 a[i] = a[i+1];
 a[i+1] = tmp;
 //有交換則繼續保持標志位；
 flag = true;
 }
 }
 k--;
 }
 }

 /**
 * 改進的冒泡法2 
 * 改進之處在於吸收上面的思想(沒有交換意味著已經有序)，如果局部的已經是有序的，則後續的比較就不需要再比較他們了。 
 * 比如：3142 5678，假如剛剛做完了2和4交換之後，發現這趟比較後續再也沒有發生交換，則後續的比較只需要比到4即可； 
 * 該算法就是用一個標志位記錄某趟最後發生比較的地點； 
 */
 public static void bubbleSortAdvanced2(int[] a){
 int flag = a.length - 1;
 int k;
 while(flag>0){
 k = flag;
 flag = 0;
 for(int i=0; i<k; i++){
 if(a[i] > a[i+1]){
 int tmp = a[i];
 a[i] = a[i+1];
 a[i+1] = tmp;
 //有交換則記錄該趟最後發生比較的地點；
 flag = i+1;
 }
 }
 }
 }

 /**
 * 插入排序
 *
 * 關於插入排序，這裡有幾個約定，從而可以快速理解算法： 
 * i: 無序表遍歷下標；i<n-1； 
 * j: 有序表遍歷下表；0<=j<i; 
 * a[i]:表示當前被拿出來做插入排序的無序表頭元素； 
 * a[j]:有序表中的任意元素； 
 * 
 * 算法關鍵點：把數組分割為a[0~i-1]有序表，a[i~n-1]無序表；每次從無序表頭部取一個， 
 * 把它插入到有序表適當的位置，直到無序表為空； 
 * 初始時，a[0]為有序表，a[1~n-1]為無序表； 
 */
 public static void insertSort(int[] a){
 //從無序表頭開始遍歷；
 for(int i=1; i<a.length; i++){
 int j;
 //拿a[i]和有序表元素依次比較，找到一個恰當的位置；
 for(j=i-1;j>=0; j--){
 if(a[j] < a[i]){
 break;
 }
 }
 //如果找到恰當的位置，則從該位置開始，把元素朝後移動一格，為插入的元素騰出空間；
 if(j!=(i-1)){
 int tmp = a[i];
 int k;
 for(k = i-1; k>j;k--){
 a[k+1] = a[k];
 }
 a[k+1] = tmp;
 }
 }
 }

 /**
 * 改進的插入排序1
 * 改進的關鍵在於：首先拿無序表頭元素a[i]和有序表尾a[i-1]比較，
 * 如果a[i]<a[i-1],說明需要調整；調整的過程為：
 * 從有序表尾開始，把有序表裡面比a[i]大的元素都朝後移動，直到找到恰當的位置；
 */
 public static void insertSortAdvanced(int[] a){
 //遍歷無序表；
 for(int i=1; i<a.length; i++){
 //如果無序表頭元素小於有序表尾，說明需要調整；
 if(a[i]<a[i-1]){
 int tmp = a[i];
 int j;
 //從有序表尾朝前搜索並比較，並把大於a[i]的元素朝後移動以騰出空間；
 for(j=i-1; j>=0&&a[j]>tmp;j--){
 a[j+1] = a[j];
 }
 a[j+1] = tmp;
 }
 }
 }

 /**
 * 改進的插入排序2
 * 總體思想和上面相似，拿無序表頭元素從有序表尾元素開始朝前比較，
 * 如果a[i]比a[i-1]小，則把a[i]從有序表尾用冒泡交換的方式朝前移動，直到到達恰當的位置；
 */
 public static void insertSortAdvanced2(int[] a){
 //遍歷無序表
 for(int i=1; i<a.length; i++){
 //拿a[i]從有序表尾開始冒泡；
 for(int j=i-1; j>=0 && a[j] > a[j+1]; j--){//a[j+1]就是a[i]
 int tmp = a[j];
 a[j] = a[j+1];
 a[j+1] = tmp;
 }
 }
 }

/**
 * 快速排序 
 * 算法的思想在於分而治之:先找一個元素(一般來說都是數組頭元素),把比它大的都放到右邊,把比它小的都放到左邊; 
 * 然後再按照這樣的思想去處理兩個子數組; 下面說的子數組頭元素通指用來劃分數組的元素; 
 * 
 * 下面程序關鍵點就在於!forward, low0++, high0--這些運算; 這三個運算使得a[low0],a[high0]裡面總有一個指向子數組頭元素; 
 * 可以用極端的情況來方便理解這三個值的運作: 
 * 假如我的數列為0123456789, 初始時forward=false,0作為子數組劃分依據,很顯然第一輪的時候不會發生任何交換,low0一直指向0, 
 * high0逐漸下降直到它指向0為止; 同理可思考9876543210這個例子; 
 * 
 * @param a 待排序數組 
 * @param low 子數組開始的下標; 
 * @param high 子數組結束的下標; 
 */
 public static void quickSort(int[] a, int low, int high){
 if(low>=high){
 return;
 }
 int low0 = low;
 int high0 = high;
 boolean forward = false;
 while(low0!=high0){
 if(a[low0]>a[high0]){
 int tmp = a[low0];
 a[low0] = a[high0];
 a[high0] = tmp;
 forward = !forward;
 }
 if(forward){
 low0++;
 }
 else{
 high0--;
 }
 }
 low0--;
 high0++;
 quickSort(a, low, low0);
 quickSort(a, high0, high);
 }

 /**
 * 快速排序的簡單調用形式 
 * 方便測試和調用 
 * @param a
 */
 public static void quickSort(int[] a){
 quickSort(a, 0, a.length-1);
 }

 /**
 * 歸並排序 
 * 所謂歸並，就是合並兩個有序數組；歸並排序也用了分而治之的思想，把一個數組分為若干個子數組； 
 * 當子數組的長度為1的時候，則子數組是有序的，於是就可以兩兩歸並了； 
 * 
 * 由於歸並排序需要分配空間來轉儲歸並的結果，為了算法上的方便，歸並算法的結果以返回值的形式出現； 
 */

 /**
 * 合並兩個有序數組
 * @param a 有序數組1
 * @param b 有序數組2
 * @return 合並之後的有序數組；
 */
 public static int[] merge(int[] a, int[] b){
 int result[] = new int[a.length+b.length];
 int i=0,j=0,k=0;
 while(i<a.length&&j<b.length){
 if(a[i]<b[j]){
 result[k++] = a[i];
 i++;
 }
 else{
 result[k++] = b[j];
 j++;
 }
 }
 while(i<a.length){
 result[k++] = a[i++];
 }
 while(j<b.length){
 result[k++] = b[j++];
 }
 return result;
 }

 /**
 * 歸並排序 
 * 把數組從中間一分為二，並對左右兩部分遞歸調用，直到數組長度為1的時候，開始兩兩歸並； 
 * @param 待排序數組；
 * @return 有序數組；
 */
 public static int[] mergeSort(int[] a){
 if(a.length==1){
 return a;
 }
 int mid = a.length/2;
 int[] leftPart = new int[mid];
 int[] rightPart = new int[a.length-mid];
 System.arraycopy(a, 0, leftPart, 0, leftPart.length);
 System.arraycopy(a, mid, rightPart, 0, rightPart.length);
 leftPart = mergeSort(leftPart);
 rightPart = mergeSort(rightPart);
 return merge(leftPart, rightPart);
 }

 /**
 * 選擇排序 
 * 和插入排序類似，它也把數組分割為有序區和無序區，所不同的是： 
 * 插入排序是拿無序區的首元素插入到有序區適當的位置，而 
 * 選擇排序是從無序區中挑選最小的放到有序區最後； 
 * 
 * 兩層循環，外層控制有序區的隊尾，內層用來查找無序區最小元素； 
 * @param a
 */
 public static void selectSort(int[] a){
 for(int i=0; i<a.length; i++){
 int minIndex = i;
 for(int j=i+1; j<a.length; j++){
 if(a[j]<a[minIndex]){
 minIndex = j;
 }
 }
 int tmp = a[i];
 a[i] = a[minIndex];
 a[minIndex]= tmp;
 }
 }

 /**
 * 希爾排序 
 * 其思想是把數組按等步長(/間距)劃分為多個子序列，對各個子序列做普通的插入排序， 逐次降低步長，直到為1的時候最後再做一次普通的插入排序；
 * 用一個極端的例子作比方，我有數列如下： 
 * [1,2,3,4,5,6,7,8,9,10]; 
 * 初始的時候，步長gap=5；則劃分的子數組為[1,6], [2,7], [3,8], [4,9], [5,10]; 對他們分別排序(當然由於本數組特殊，所以結果是不變的)； 
 * 然後gap=2=5/2; 子數組為[1,3,5,7,9], [2,4,6,8,10]; 
 * 最後gap=1=2/2; 做一次全局排序； 
 * 
 * 希爾排序克服了插入/冒泡排序的弱點(一次只能把元素移動一個相鄰的位置), 依靠大步長，可以把元素盡快移動到目標位置(或附近); 
 * 希爾排序實際上是插入排序的變種。它適用於：當數組總體有序，個別需要調整的情況；這時候利用插入排序的優勢，可以達到O(n)的效率； 
 * 影響希爾算法的一個重要的因素是步長選擇，一個好步長的優點是：後面的短步長排序不會破壞前面的長步長排序； 
 * 怎麼理解這種破壞呢？前面的長步長把一個較小的數移到了左面，但是在縮小步長之後有可能又被交換到了右面 (因為它被分到了一個有很多比它更小的組)； 
 * 關於步長，可以查看http://zh.wikipedia.org上面關於希爾排序的頁面； 
 * 下面的程序是希爾排序最基礎的寫法，適合用來理解希爾排序思想； 
 */
 public static void shellSort(int[] a){
 // 控制間距；間距逐漸減小，直到為1；
 for(int gap = a.length/2; gap>0; gap/=2){
 // 掃描每個子數組
 for(int i=0; i<gap; i++){
 // 對每個字數組，掃描無序區；注意增量；
 // a[i]是初始有序區；
 for(int j=i+gap; j<a.length; j+=gap){
 // 無序區首元素小於有序區尾元素，說明需要調整
 if(a[j]<a[j-gap]){
 int tmp = a[j];
 int k = j-gap;
 //從有序區尾向前搜索查找適當的位置；
 while(k>=0&&a[k]>tmp){
 a[k+gap] = a[k];
 k-=gap;
 }
 a[k+gap] = tmp;
 }
 }
 }
 }
 }

 /**
 * 改進的希爾排序 
 * 改進之處在於：上面的寫法用一個for循環來區別對待每個字數組；而實際上是不必要的； 
 * a[0,1,...gap-1]作為所有子數組的有序區，a[gap,...n-1]作為所有字數組的無序區； 
 * 
 * 該改進在時間效率上沒有改進；只是讓程序看起來更簡潔； 
 * @param a
 */
 public static void shellSortAdvanced(int[] a){
 // 控制步長
 for(int gap = a.length/2; gap>0; gap/=2){
 // 從無序區開始處理，把多個子數組放在一起處理；
 for(int j=gap; j<a.length; j++){
 // 下面的邏輯和上面是一樣的；
 if(a[j]<a[j-gap]){
 int tmp = a[j];
 int k = j-gap;
 while(k>=0&&a[k]>tmp){
 a[k+gap] = a[k];
 k-=gap;
 }
 a[k+gap] = tmp;
 }
 }
 }
 }

 /**
 * 改進的希爾排序2 
 * 在吸收shellSortAdvanced思想的基礎上，采用insertAdvanced2的做法； 即無序區首元素通過朝前冒泡的形式移動的適當的位置； 
 * @param a
 */
 public static void shellSortAdvanced2(int[] a){
 for(int gap = a.length/2; gap>0; gap/=2){
 for(int i=gap; i<a.length; i++){
 if(a[i]<a[i-gap]){
 for(int j=i-gap; j>=0&&a[j+gap]>a[j]; j-=gap){
 int tmp = a[j];
 a[j] = a[j+gap];
 a[j+gap] = tmp;
 }
 }
 }
 }
 }

 /**
 * 堆排序 
 * 堆的定義：堆是一個完全，或近似完全的二叉樹，堆頂元素的值大於左右孩子的值，左右孩子也需要滿足這個條件； 
 * 按照堆的定義，堆可以是大頂堆(maxHeap)，或小頂堆(minHeap)； 
 * 一般用數組即可模擬二叉樹，對於任意元素i，左孩子為2*i+1,右孩子為2*i+2;父節點為(i-1)/2;
 * @param a
 */
 public static void heapSort(int[] a){

// 先從最後一個非葉子節點往上調整，使滿足堆結構；
 for(int i=(a.length-2)/2; i>=0; i--){
 maxHeapAdjust(a, i, a.length);
 }
 // 每次拿最後一個節點和第一個交換，然後調整堆；直到堆頂；
 for(int i=a.length-1; i>0; i--){
 int tmp = a[i]; a[i] = a[0]; a[0] = tmp;
 maxHeapAdjust(a, 0, i);
 }
 }

 /**
 * 調整堆 
 * 把以i為跟節點的二叉樹調整為堆； 
 * 可以這麼來思考這個過程：這個完全二叉樹就像一個金字塔，塔頂的小元素沿著樹結構，往下沉降； 
 * 調整的結果是最大的元素在金字塔頂，然後把它從堆中刪除(把它交換到堆尾，然後堆收縮一格)； 
 * 堆排序快的原因就是根據二叉樹的特點，一個節點要沉降到合適的位置，只需要logn步；同時前期調整的結果(大小順序)會被記錄下來，從而加快後續的調整； 
 * @param a 待排數組
 * @param i 堆頂
 * @param len 堆長度
 */
 public static void maxHeapAdjust(int[] a, int i, int len){
 int tmp = a[i];
 // j是左孩子節點
 int j = i*2+1;
 //
 while(j<len){
 // 從左右孩子中挑選大的
 // j+1是右孩子節點
 if((j+1)<len && a[j+1]>a[j]){
 j++;
 }
 // 找到恰當的位置就不再找
 if(a[j]<tmp){
 break;
 }
 // 否則把較大者沿著樹往上移動；
 a[i] = a[j];
 // i指向剛才的較大的孩子；
 i = j;
 // j指向新的左孩子節點；
 j = 2*i + 1;
 }
 // 把要調整的節點值下沉到適當的位置；
 a[i] = tmp;
 }

 /**
 * 二叉樹排序 
 * 二叉樹的定義是嵌套的： 節點的值大於左葉子節點的值，小於右葉子節點的值；葉子節點同樣滿足這個要求； 
 * 二叉樹的構造過程就是排序的過程： 
 * 先構造跟節點，然後調用add方法添加後續節點為跟節點的子孫節點；這個過程也是嵌套的; 
 * 
 * 中序遍歷二叉樹即得到有序結果； 
 * 二叉樹排序用法特殊，使用情形要視情況而定； 
 * @param a
 */
 public static void binaryTreeSort(int[] a){
 // 構造一個二叉樹節點內部類來實現二叉樹排序算法；
 class BinaryNode{
 int value;
 BinaryNode left;
 BinaryNode right;

 public BinaryNode(int value){
 this.value = value;
 this.left = null;
 this.right = null;
 }

 public void add(int value){
 if(value>this.value){
 if(this.right!=null){
 this.right.add(value);
 }
 else{
 this.right = new BinaryNode(value);
 }
 }
 else{
 if(this.left!=null){
 this.left.add(value);
 }
 else{
 this.left = new BinaryNode(value);
 }
 }
 }
 /**
 * 按中序遍歷二叉樹，就是有序的。
 */
 public void iterate(){
 if(this.left!=null){
 this.left.iterate();
 }
 // 在測試的時候要把輸出關掉，以免影響性能；
 // System.out.print(value + ", ");
 if(this.right!=null){
 this.right.iterate();
 }
 }
 }

 BinaryNode root = new BinaryNode(a[0]);
 for(int i=1; i<a.length; i++){
 root.add(a[i]);
 }
 root.iterate();
 }
}