審查和測試排序方法。第一部分

有一天，在 VKontakte 的評論中，我與該計畫的其他學生發生了爭執。爭論的本質是「誰會贏」——sort()類別中的方法java.util.Arrays或簡單演算法的自寫實作：bubble、insert、Selection、shell（Shell 演算法）。 對某些人來說，這個問題的答案可能是顯而易見的，但自從爭議出現以來，儘管雙方都有「受人尊敬的消息來源」支持其觀點，但還是決定進行一項研究，將灰質延伸到過程，實現各種演算法。 TL;DR： java.util.Arrays.sort() 在 100,000 個或更多元素的陣列上，它毫無疑問是領先者；由於尺寸較小，Shell 方法有時可以與之競爭。其餘所考慮的演算法完全是空的，只有在某些特殊條件下才有用。 現在讓我們看看數組在我們的矽超級設備中是如何排序的。

選擇排序。按選擇排序

讓我們從最簡單、最明顯的方法開始。Robert Sedgwick在coursera 上的視訊講座中向我們完美地展示了它的本質（我將引用那裡的 動畫，我把它嚴重壓縮成 gif）： 因此，我們以排序的形式保留數組的最終版本。以下是用 Java 實作該演算法的程式碼：

public void sort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i ++) {
            int minIndex = min(array, i, n - 1);
            swap(array, i, minIndex);
        }
    }

public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
public static int min(int[] array, int begin, int end) {
        int minVal = array[begin];
        int minIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (array[i] < minVal) {
                minVal = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

演算法分析表明，每次遍歷都需要對數組的剩餘部分進行梳理，也就是說，我們正好需要 N + (N-1) + (N-2) + ... + 1 = N^ 2/2 比較。因此，演算法的複雜度為O(N^2)。這是什麼意思？這意味著，透過將數組中的元素數量 (N) 增加 2 倍，我們將增加演算法的運行時間不是 2 倍，而是 2^2 = 4 倍。透過將 N 增加 10 倍，我們會將操作時間增加 100 倍，依此類推。在我的 2012 年配備 Core i3 處理器、運行 Ubuntu 14.4 的筆記型電腦上，我獲得了以下正常運行時間：

插入排序。插入排序

這裡的想法略有不同。再次，讓我們轉向塞奇威克醫生的動畫： 查看 前面的內容我們甚至還沒有看到，而我們留下的一切始終保持秩序。關鍵是我們將原始數組的每個新元素「返回」到開頭，直到它「停留」在較小的元素上。因此，我們再次進行了 N 次遍歷（對於原始數組的每個元素），但在每次遍歷中，在大多數情況下，我們不會查看整個餘數，而只會查看一部分。也就是說，只有當我們必須將每個下一個元素回到最開始時，即在這種情況下，我們才會得到選項1 + (N-1) + (N-2) + … + N = N^2/2輸入排序的「反向」陣列（不幸的是，不幸的是）。在已經排序的數組的情況下（幸運的是），將有一個完整的免費贈品- 在每次傳遞中只有一次比較並將元素保留在適當的位置，也就是說，算法將在與N 成正比的時間內工作。演算法的性能將由最壞的理論情況決定，即 O(N^2)。平均而言，運行時間將與N^2/4成正比，即比之前的演算法快兩倍。在我的實作中，由於排列的非最佳化使用，運行時間比選擇的運行時間更長。我計劃盡快糾正並更新該帖子。以下是程式碼及其在同一台機器上運行的結果：

public void sort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j >= 1; j--) {
                if (array[j] < array[j - 1])
                    swap(array, j, j - 1);
                else
                    break;
            }
        }
    }

貝殼排序。希爾排序

聰明人 Donald Schell 早在 1959 年就注意到，插入演算法中最昂貴的情況是元素返回距離數組開頭很遠的情況：在某些過程中，我們將元素返回到開頭幾個位置，而在另一遍幾乎穿過整個陣列到開始處又遠又長。是否可以一次完成此操作，跳過多個元素？而他找到了這樣一個方法。它由順序執行特殊的部分排序組成，通常稱為 d 排序，或根據 Sedgwick 的說法，稱為 h 排序（我懷疑 h 意味著跳躍）。例如，3-sort 不會將有問題的元素與前一個元素進行比較，而是跳過兩個元素並與後面 3 個位置的元素進行比較。如果發生變化，它將再次與後面 3 個位置的元素進行比較，依此類推。最重要的是，產生的陣列將是「3 排序」的，即元素的錯誤位置將少於 3 個位置。使用這種插入演算法將是輕鬆愉快的。順便說一句，「1-sort」只不過是一種插入演算法 =) 透過對 h 值遞減的陣列順序應用 h-sort，我們可以更快地對大型陣列進行排序。它看起來像這樣： 查看 這裡的挑戰是如何選擇正確的部分排序順序。最終，演算法的效能取決於此。最常見的是 Donald Knuth 提出的序列：h = h*3 + 1，即 1, 4, 13, 40, ... 等等，最多為陣列大小的 1/3。該序列提供了不錯的性能並且也易於實現。分析演算法需要大量的語言，超出了我的能力。分析的廣度也取決於 h 序列的許多變體。根據經驗，我們可以說該演算法的速度非常好 - 親自看看： 不到一秒一百萬個元素！這是一個帶有 Knut 序列的 Java 程式碼。

public void sort(int[] array) {
        int h = 1;
        while (h*3 < array.length)
            h = h * 3 + 1;

        while(h >= 1) {
            hSort(array, h);
            h = h/3;
        }
    }

    private void hSort(int[] array, int h) {
        int length = array.length;
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h; j = j - h) {
                if (array[j] < array[j - h])
                    swap(array, j, j - h);
                else
                    break;
            }
        }
    }

冒泡排序。氣泡法

這是經典！幾乎每個新手程式設計師都會實作這個演算法。這是一部經典之作，塞奇威克博士甚至沒有製作動畫，所以我必須自己完成這項工作。 在 這裡，在每次遍歷中，我們從頭到尾遍歷數組，交換無序的相鄰元素。結果，最大的元素“浮動”（因此得名）到數組的末尾。我們樂觀地開始每個新的流程，希望陣列已經排序（sorted = true）。在段落結束時，如果我們發現自己犯了錯誤，我們就會開始新的段落。這裡的困難在於，我們每次都遍歷（幾乎）整個陣列。比較發生在每一步，交換幾乎發生在每一步，這使得該演算法成為最慢的演算法之一（如果我們考慮合理實現的演算法，而不是「搖動排序」和其他類似演算法）。有趣的是，形式上這裡的複雜度也等於 O(N^2)，但係數遠高於插入和選擇的係數。演算法程式碼：

public void sort(int[] array) {
        boolean isSorted;
        int nMinusOne = array.length - 1;
        for(int i = 0; i < nMinusOne; i++) {
            isSorted = true;
            for (int j = 0; j < nMinusOne - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSorted = false;
                }
            }
            if (isSorted)
                return;
        }
    }

操作時間： 感受差異：半個多小時處理一百萬個元素！結論：永遠不要使用這個演算法！

第一部分總結

因此，我建議查看這些演算法的通用表。 您也可以與內建方法的結果進行比較java.util.Arrays.sort()。它看起來就像某種魔法——還有什麼比 Shell 更快呢？我將在下一部分寫到這一點。在那裡，我們將了解廣泛使用的快速排序演算法以及合併排序，了解基元和引用類型對數組進行排序的方法的差異，並熟悉這方面的一個非常重要的介面Comparable；）下面您可以學習使用資料表建立在對數刻度上的圖表。線條越平坦，演算法就越好 =) 對於那些想要下載整個專案並自己運行測試的人，請保留連結： Java 下一部分見！=)