http://awed.javaeye.com/blog/108117
幾種排序方法的比較
關(guān)鍵字: JAVA 
java 代碼
public class Sort {    
   
    /**   
     * 插入法:遍歷排序集合，每到一個元素時，都要將這個元素與所有它之前的元素遍歷比較一遍， 讓符合排序順序的元素挨個移動到當(dāng)前范圍內(nèi)它最應(yīng)該出現(xiàn)的位置。交換是相鄰遍歷移動，   
     * 雙重循環(huán)控制實現(xiàn).這種排序法屬于地頭蛇類型,在我的地牌上我要把所有的東西按一定的順序 規(guī)整,過來一個,規(guī)整一個.   
     */   
    public static int[] sort(int[] data) {    
        int temp;    
        for (int i = 1; i < data.length; i++) {    
            for (int j = i; (j > 0) && (data[j] > data[j - 1]); j--) {    
   
                temp = data[j];    
                data[j] = data[j - 1];    
                data[j - 1] = temp;    
            }    
        }    
        return data;    
    }    
   
    /**   
     * 冒泡法:比較容易，它的內(nèi)層循環(huán)保證遍歷一次后，集合中最小（大）元素出現(xiàn)在它的正確位置， 下一次就是次小元素。。。該方法在集合分布的各種情況下交換移動的次數(shù)基本不變，   
     * 屬于最慢的一種排序。實現(xiàn)也是雙重循環(huán)控制。這種排序法屬于過江龍,就是要找到極端, 但是過獎龍也有大哥,二哥等,所以他們只能是大哥挑了二哥挑.   
     */   
    public static int[] maopao(int[] data) {    
        int temp;    
        for (int i = 0; i < data.length - 1; i++) {    
            for (int j = i + 1; j < data.length; j++) {    
                if (data[i] < data[j]) {    
                    temp = data[i];    
                    data[i] = data[j];    
                    data[j] = temp;    
                }    
            }    
        }    
        return data;    
    }    
   
    /**   
     * 選擇法:該方法只是通過遍歷集合記錄最?。ù螅┰氐奈恢?，一次遍歷完后 ，再進(jìn)行交換位置操作，類似冒泡，但在比較過程中，不進(jìn)行交換操作，   
     * 只記錄元素位置。一次遍歷只進(jìn)行一次交換操作。這個對與交換次序比較費時的元素比較 適合。這種排序法比冒泡法要城府要深的多,我先記住極端數(shù)據(jù),待遍歷數(shù)據(jù)完了之后,   
     * 我再處理,不像冒泡法那樣只要比自己極端一點的就要處理,選擇法只處理本身范圍內(nèi)的 最極端數(shù)據(jù).   
     */   
    public static int[] xuanze(int[] data) {    
        int temp;    
        for (int i = 0; i < data.length; i++) {    
            int lowIndex = i;    
            for (int j = data.length - 1; j > i; j--) {    
                if (data[j] > data[lowIndex]) {    
                    lowIndex = j;    
                }    
            }    
            temp = data[i];    
            data[i] = data[lowIndex];    
            data[lowIndex] = temp;    
        }    
        return data;    
    }    
   
    /**   
     * Shell排序:它是對插入排序的一種改進(jìn)，是考慮將集合元素按照一定的基數(shù)劃分成組去排序， 讓每一組在局部范圍內(nèi)先排成基本有序，最后在進(jìn)行一次所有元素的插入排序。   
     */   
    public static int[] sort2(int[] data) {    
        for (int i = data.length / 2; i > 2; i /= 2) {    
            for (int j = 0; j < i; j++) {    
                insertSort(data, j, i);    
            }    
        }    
        insertSort(data, 0, 1);    
        return data;    
    }    
   
    private static void insertSort(int[] data, int start, int inc) {    
        int temp;    
        for (int i = start + inc; i < data.length; i += inc) {    
            for (int j = i; (j >= inc) && (data[j] > data[j - inc]); j -= inc) {    
                temp = data[j];    
                data[j] = data[j - inc];    
                data[j - inc] = temp;    
            }    
        }    
    }    
   
    public static void main(String args[]) {    
        Sort s = new Sort();    
        int str[] = {1, 5, 9, 2, 56, 89, 98, 74, 52, 65, 30, 25, 78, 10, 12, 31, 25, 46};    
        // 冒泡法排序所花時間    
        Long star = System.currentTimeMillis();    
        for (int j = 0; j < 100000; j++)    
            str = s.maopao(str);    
        Long end = System.currentTimeMillis();            
        for (int i = 0; i < str.length; i++) {    
            System.out.print(str[i] + " ");    
        }    
        System.out.println("冒泡排序所花時間: " + (end - star));    
   
        // 插入法排序所花時間    
        star = System.currentTimeMillis();    
        for (int j = 0; j < 100000; j++)    
            str = s.sort(str);    
        end = System.currentTimeMillis();    
        for (int i = 0; i < str.length; i++) {    
            System.out.print(str[i] + " ");    
        }    
        System.out.println("插入法排序所花時間: " + (end - star));    
   
        // Shell排序法排序所花時間    
        star = System.currentTimeMillis();    
        for (int j = 0; j < 100000; j++)    
            str = s.sort2(str);    
        end = System.currentTimeMillis();    
        for (int i = 0; i < str.length; i++) {    
            System.out.print(str[i] + " ");    
        }    
        System.out.println("Shell排序法排序所花時間: " + (end - star));    
   
        // 選擇法排序所花時間    
        star = System.currentTimeMillis();    
        for (int j = 0; j < 100000; j++)    
            str = s.xuanze(str);    
        end = System.currentTimeMillis();    
        for (int i = 0; i < str.length; i++) {    
            System.out.print(str[i] + " ");    
        }    
        System.out.println("選擇法排序所花時間: " + (end - star));    
    }    
}   

比較結(jié)果是:

98 89 78 74 65 56 52 46 31 30 25 25 12 10 9 5 2 1 冒泡排序所花時間: 125
98 89 78 74 65 56 52 46 31 30 25 25 12 10 9 5 2 1 插入法排序所花時間: 15
98 89 78 74 65 56 52 46 31 30 25 25 12 10 9 5 2 1 Shell排序法排序所花時間: 63
98 89 78 74 65 56 52 46 31 30 25 25 12 10 9 5 2 1 選擇法排序所花時間: 94