财神网2是正规平台吗

書名：自己動手寫分布式搜索引擎
作者名：羅剛
本章字數： 580字
更新時間： 2020-11-28 15:52:40

1.4.2 排序

如何得到一個排好序的詞表？首先看一下如何對整數數組排序，然后再看一下如何對字符串數組排序。

排序可以看成是減少逆序的過程。通過交換值來消除逆序。檢查任意兩個位置的元素，如果是逆序，就交換這兩個位置中的值。

        int[] scores = { 1, 6, 3, 8, 5 }; // 待排序的數組


        // 比較任意兩個數，將小數放在前面，大數放在后面
        for (int i = 0; i < scores.length; i++) {
            for (int j = 0; j < scores.length; j++) {
                //如果是逆序，就交換這兩個數
                if (i<j && scores[i] > scores[j]) { //同時滿足兩個條件
                    int temp = scores[j];
                    scores[j] = scores[i];
                    scores[i] = temp;
                }
            }
        }

這種隨意消除逆序的方法并不能保證最后得到一個完全有序的數組。對于已經排好序的數組來說，最大的元素位于數組尾部。對于子數組來說，也是如此。也就是說，第二大的元素位于數組倒數第二的位置，第三大的元素位于數組倒數第三的位置，依次類推。冒泡排序正是基于這樣的事實。

設想有一瓶汽水，溶解在水中的氣體不斷上浮，最后實現水氣分離。每次讓最重的一個元素沉到底。以后就不用再管它了。通過讓輕的氣泡不斷上浮，從而達到有序。

將一個最重的元素沉底，順便減少逆序。

        int[] scores = { 1, 6, 3, 8, 5 }; //待排序的數組
        for (int j = 0; j < scores.length -1 ; j++) {
                //循環不變式是：scores[j]存儲了數組從開始一直到j為止的最大的一個數
                //比較相鄰的兩個數，將小數放在前面，大數放在后面
                if (scores[j] > scores[j + 1]) {
                    int temp = scores[j];
                    scores[j] = scores[j + 1];
                    scores[j + 1] = temp;
                }
        }

完整的冒泡排序。

        int[] scores = { 1, 6, 3, 8, 5 }; //待排序的數組


        for (int i = 0; i < scores.length -1; i++) { //每次搞定一個最大的元素
            // 最底下已經排好序，所以逐漸減少循環次數
            for (int j = 0; j < scores.length -1- i; j++) {
                //比較相鄰的兩個數，將小數放在前面，大數放在后面
                if (scores[j] > scores[j + 1]) {
                    int temp = scores[j];
                    scores[j] = scores[j + 1];
                    scores[j + 1] = temp;
                }
            }
        }
        System.out.println("排序后的結果：");
        for (int i = 0; i < scores.length; i++) {
            System.out.println(scores[i]);
        }

兩層循環，內層循環執行一遍后，讓1個數沉底。如果數組中有n 個元素，則外層循環執行n -1遍。也就是說通過n -1次循環讓n -1個元素沉底。

想象在和很多人喝酒，要把這些人都招待好。i用來表示找每個人喝，j表示這個人每次要喝很多杯才能喝好。

首先看一下如何比較兩個字符串的大小，然后再看一下如何對字符串數組排序。比較兩個對象用compareTo()方法。字符串也是對象，所以也可以用compareTo()方法比較兩個字符串的大小。

        String a = "北京";
        String b = "廣州";
        System.out.print(a.compareTo(b)); //因為a小于b，所以返回負數

對字符串數組排序。

        String[] words = {"北京", "廣州", "上海"};


        for (int i = 0; i < words.length -1; i++) {
            // 最底下已經排好序，所以逐漸減少循環次數
            for (int j = 0; j < words.length -1- i; j++) {
                if (words[j].compareTo(words[j + 1])>0) {
                    String temp = words[j];
                    words[j] = words[j + 1];
                    words[j + 1] = temp;
                }
            }
        }

如果數組中的元素很多，則快速排序更快。所要搜索的詞往往很多，所以應該使用快速排序。

官术网_书友最值得收藏!

自己動手寫分布式搜索引擎

1.4.2 排序