歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

排序算法(JAVA實現):冒泡排序法和插入排序法

為了方便擴展,先引入一個抽象的基礎類:

[html]

  1. package com.andyidea.algorithms;  
  2.   
  3. /**  
  4.  * 排序抽象基礎類  
  5.  * @author Andy.Chen  
  6.  *  
  7.  * @param <T>  
  8.  */  
  9. public abstract class Sorter<T extends Comparable<T>> {  
  10.       
  11.     public abstract void sort(T[] array,int from,int len);  
  12.       
  13.     public final void sort(T[] array){  
  14.         sort(array,0,array.length);  
  15.     }  
  16.       
  17.     protected final void swap(T[] array,int from,int to){  
  18.         T tmp = array[from];  
  19.         array[from] = array[to];  
  20.         array[to] = tmp;  
  21.     }  
  22.   
  23. }  
【一】冒泡排序:冒泡排序是一種簡單的排序算法,其平均時間復雜度為O(n2),它重復地走訪過要排序的數列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換,也就是說該數列已經排序完成。

冒泡排序算法的具體描述如下:

  1. 比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。
  2. 對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最後一對。在這一點,最後的元素應該會是最大的數。
  3. 針對所有的元素重復以上的步驟,除了最後一個。
  4. 持續每次對越來越少的元素重復上面的步驟,直到沒有任何一對數字需要比較。
冒泡排序算法源碼如下:

[html]

  1. package com.andyidea.algorithms;  
  2.   
  3. /**  
  4.  * 冒泡排序法  
  5.  * @author Andy.Chen  
  6.  *  
  7.  * @param <T>  
  8.  */  
  9. public class BubbleSort<T extends Comparable<T>> extends Sorter<T> {  
  10.       
  11.     //是否從右向左排序的標志位  
  12.     public static boolean RIGHT = true;  
  13.   
  14.     @Override  
  15.     public void sort(T[] array, int from, int len) {  
  16.         if(RIGHT){  
  17.             bubble_right(array, from, len);  
  18.         }else{  
  19.             bubble_left(array, from, len);  
  20.         }  
  21.     }  
  22.       
  23.     /**  
  24.      * 從右向左排序  
  25.      * @param array  
  26.      * @param from  
  27.      * @param len  
  28.      */  
  29.     public final void bubble_right(T[] array, int from, int len){  
  30.         for(int i=from; i<from+len; i++){  
  31.             for(int j=from+len-1;j>i;j--){  
  32.                 if(array[j].compareTo(array[j-1])<0){  
  33.                     swap(array, j-1, j);  
  34.                 }  
  35.             }  
  36.         }  
  37.     }  
  38.       
  39.     /**  
  40.      * 從左向右排序  
  41.      * @param array  
  42.      * @param from  
  43.      * @param len  
  44.      */  
  45.     public final void bubble_left(T[] array, int from, int len){  
  46.         for(int i=from+len-1; i>from;i--){  
  47.             for(int j=from;j<i;j++){  
  48.                 if(array[j].compareTo(array[j+1])>0){  
  49.                     swap(array,j,j+1);  
  50.                 }  
  51.             }  
  52.         }  
  53.     }  
  54.   
  55. }  
【二】插入排序:插入排序(Insertion Sort)的算法描述是一種簡單直觀的排序算法,其平均時間復雜度為O(n2)。它的工作原理是通過構建有序序列,對於未排序數據,在已排序序列中從後向前掃描,找到相應位置並插入。插入排序在實現上,通常采用in-place排序(即只需用到O(1)的額外空間的排序),因而在從後向前掃描過程中,需要反復把已排序元素逐步向後挪位,為最新元素提供插入空間。

插入排序都采用in-place在數組上實現。具體算法描述如下:

  1. 從第一個元素開始,該元素可以認為已經被排序
  2. 取出下一個元素,在已經排序的元素序列中從後向前掃描
  3. 如果該元素(已排序)大於新元素,將該元素移到下一位置
  4. 重復步驟3,直到找到已排序的元素小於或者等於新元素的位置
  5. 將新元素插入到該位置中
  6. 重復步驟2
[html]
  1. package com.andyidea.algorithms;  
  2.   
  3. /**  
  4.  * 插入排序法  
  5.  * @author Andy.Chen  
  6.  * @param <T>  
  7.  *  
  8.  */  
  9. public class InsertionSort<T extends Comparable<T>> extends Sorter<T> {  
  10.   
  11.     @Override  
  12.     public void sort(T[] array, int from, int len) {  
  13.         T tmp = null;  
  14.         for(int i=from+1;i<from+len;i++){  
  15.             tmp = array[i];  
  16.             int j = i;  
  17.             for( ; j>from; j--){  
  18.                 if(tmp.compareTo(array[j-1]) < 0){  
  19.                     array[j] = array[j-1];  
  20.                 }else{  
  21.                     break;  
  22.                 }  
  23.             }  
  24.             array[j] = tmp;  
  25.         }  
  26.     }  
  27.   
  28. }  
Copyright © Linux教程網 All Rights Reserved