前言

手寫一個(gè)排序算法的效率是很慢的，當(dāng)然這也不利于我們?cè)诒荣惢蛘吖こ讨械膶?shí)戰(zhàn)，如今幾乎每個(gè)語言的標(biāo)準(zhǔn)庫中都有排序算法，今天讓我來給大家講解一下Java語言中的sort排序

升序排序

Collections類中的sort方法可以實(shí)現(xiàn)List接口的集合進(jìn)行排序

public static void main(String[] args) {
    // 定義含有5個(gè)元素的數(shù)組
    double[] scores = new double[] { 78, 45, 85, 97, 87 };
    System.out.println("排序前數(shù)組內(nèi)容如下：");

    // 對(duì)scores數(shù)組進(jìn)行循環(huán)遍歷
    for (int i = 0; i < scores.length; i++) {
        System.out.print(scores[i] + "\t");
    }
    System.out.println("\n排序后的數(shù)組內(nèi)容如下：");

    // 對(duì)數(shù)組進(jìn)行排序
    Arrays.sort(scores);

    // 遍歷排序后的數(shù)組
    for (int j = 0; j < scores.length; j++) {
        System.out.print(scores[j] + "\t");
    }
}

降序排序

Java中降序排序有倆種方法（和c++很類似，可以看我這篇博客）：

c++sort排序

利用 Collections.reverseOrder() 方法

public static void main(String[] args) {
    Integer[] a = { 9, 8, 7, 2, 3, 4, 1, 0, 6, 5 };    // 數(shù)組類型為Integer
    Arrays.sort(a, Collections.reverseOrder());
    for (int arr : a) {
        System.out.print(arr + " ");
    }
}

實(shí)現(xiàn) Comparator 接口的復(fù)寫 compare() 方法

public class Test {
    public static void main(String[] args) {
        /*
         * 注意，要想改變默認(rèn)的排列順序，不能使用基本類型（int,double,char）而要使用它們對(duì)應(yīng)的類
         */
        Integer[] a = { 9, 8, 7, 2, 3, 4, 1, 0, 6, 5 };
        // 定義一個(gè)自定義類MyComparator的對(duì)象
        Comparator cmp = new MyComparator();
        Arrays.sort(a, cmp);
        for (int arr : a) {
            System.out.print(arr + " ");
        }
    }
}

// 實(shí)現(xiàn)Comparator接口
class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        /*
         * 如果o1小于o2，我們就返回正值，如果o1大于o2我們就返回負(fù)值， 這樣顛倒一下，就可以實(shí)現(xiàn)降序排序了,反之即可自定義升序排序了
         */
        return o2 - o1;
    }
}

排序原理

對(duì)sort方法如何排序感到好奇？

通常，在看有關(guān)算法書籍的時(shí)候，會(huì)發(fā)現(xiàn)都說有關(guān)數(shù)組的排序算法，而且使用的都是隨機(jī)訪問，但是我們知道數(shù)組的隨機(jī)訪問是很快的，鏈表的隨機(jī)訪問很慢！實(shí)際上，可以使用一種歸并排序的方法對(duì)鏈表高效的排序，不過，Java并不是這樣做的，它是將所有元素轉(zhuǎn)入一個(gè)數(shù)組，對(duì)數(shù)組進(jìn)行排序，然后，將排好序 的序列復(fù)制回列表

事實(shí)上Collections.sort方法底層就是調(diào)用的Arrays.sort方法，而Arrays.sort使用了兩種排序方法，快速排序和優(yōu)化的歸并排序。

快速排序(quick)主要是對(duì)那些基本類型數(shù)據(jù)（int, short, long等）排序， 而歸并排序(merge)用于對(duì)Object類型進(jìn)行排序。
使用不同類型的排序算法主要是由于快速排序是不穩(wěn)定的，而歸并排序是穩(wěn)定的。這里的穩(wěn)定是指比較相等的數(shù)據(jù)在排序之后仍然按照排序之前的前后順序排列。對(duì)于基本數(shù)據(jù)類型，穩(wěn)定性沒有意義，而對(duì)于Object類型，穩(wěn)定性是比較重要的，因?yàn)閷?duì)象相等的判斷可能只是判斷關(guān)鍵屬性，最好保持相等對(duì)象的非關(guān)鍵屬性的順序與排序前一致；另外一個(gè)原因是由于歸并排序相對(duì)而言比較次數(shù)比快速排序少，移動(dòng)（對(duì)象引用的移動(dòng)）次數(shù)比快速排序多，而對(duì)于對(duì)象來說，比較一般比移動(dòng)耗時(shí)。
此外，對(duì)大數(shù)組排序?？焖倥判虻膕ort()采用遞歸實(shí)現(xiàn)，數(shù)組規(guī)模太大時(shí)會(huì)發(fā)生堆棧溢出，而歸并排序sort()采用非遞歸實(shí)現(xiàn)，不存在此問題。

sort()是根據(jù)需要排序的數(shù)組的長(zhǎng)度進(jìn)行區(qū)分的:

首先先判斷需要排序的數(shù)據(jù)量是否大于60。
小于60：使用插入排序，插入排序是穩(wěn)定的
大于60的數(shù)據(jù)量會(huì)根據(jù)數(shù)據(jù)類型選擇排序方式：
基本類型：使用快速排序?！敢?yàn)榛绢愋筒恍枰紤]穩(wěn)定性」
Object類型：使用歸并排序「因?yàn)闅w并排序具有穩(wěn)定性」

注意：不管是快速排序還是歸并排序。在二分的時(shí)候小于60的數(shù)據(jù)量依舊會(huì)使用插入排序

關(guān)于穩(wěn)定性，我們用下面這個(gè)例子來說明：

假設(shè)，有一個(gè)已經(jīng)按照姓名排序的員工列表，現(xiàn)在我們要按照工資進(jìn)行再次的排序，如果倆個(gè)員工的工資又剛好相同怎么辦？如果采用穩(wěn)定的排序方法，將會(huì)保留按照姓名的排序，換句話說，我們最后得到的是一個(gè)先按照姓名排序，又按照工資排序的一個(gè)表

總結(jié)

到此這篇關(guān)于Java中sort排序函數(shù)的文章就介紹到這了,更多相關(guān)Java sort排序函數(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論