文章
開始
開始學習
JavaRush /Java Blog /Random-TW /排序演算法的理論與實踐
Viacheslav
等級 3

排序演算法的理論與實踐

在 Random-TW 群組發布
排序是對物件執行的活動或操作的基本類型之一。即使在童年時期，孩子們就被教導如何分類，發展他們的思維。計算機和程式也不例外。算法種類繁多。我建議您看看它們是什麼以及它們如何工作。另外，如果有一天你在面試中被問到其中一個怎麼辦？
排序演算法的理論與實踐 - 1

介紹

對元素進行排序是開發人員必須習慣的演算法類別之一。如果說以前我讀書的時候，電腦科學還沒有那麼被重視的話，那麼現在在學校他們應該能夠實現排序演算法並理解它們。基本演算法（最簡單的演算法）是使用循環實現的for。當然，為了對元素集合（例如陣列）進行排序，您需要以某種方式遍歷該集合。例如： 
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
	System.out.println(array[i]);
}
對於這段程式碼你有什麼想說的嗎？我們有一個循環，在該循環中我們將索引值 ( int i) 從 0 更改為數組中的最後一個元素。事實上，我們只是獲取數組中的每個元素並列印其內容。數組中的元素越多，執行程式碼所需的時間就越長。也就是說，如果 n 是元素的數量，則 n=10 時程式的執行時間將是 n=5 時的 2 倍。當我們的程式有一個循環時，執行時間會線性增加：元素越多，執行時間就越長。事實證明，上述程式碼的演算法在線性時間 (n) 內工作。在這種情況下，「演算法複雜度」被稱為 O(n)。這種表示法也稱為“大O”或“漸近行為”。但你可以簡單地記住「演算法的複雜性」。
排序演算法的理論與實踐 - 2

最簡單的排序（冒泡排序）

所以，我們有一個陣列並且可以迭代它。偉大的。現在讓我們嘗試按升序對其進行排序。這對我們意味著什麼？這意味著給定兩個元素（例如，a=6，b=5），如果 a 大於 b（如果 a > b），我們必須交換 a 和 b。當我們按索引處理集合時（就像數組一樣），這對我們意味著什麼？這表示如果索引 a 的元素大於索引 b 的元素（array[a] > array[b]），則必須交換這些元素。改變位置通常稱為交換。有多種方法可以改變位置。但我們使用簡單、清晰、易記的程式碼： 
private void swap(int[] array, int ind1, int ind2) {
    int tmp = array[ind1];
    array[ind1] = array[ind2];
    array[ind2] = tmp;
}
現在我們可以編寫以下內容： 
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
	if (array[i] < array[i - 1]) {
		swap(array, i, i-1);
	}
}
System.out.println(Arrays.toString(array));
正如我們所看到的，元素確實改變了位置。我們從一個元素開始，因為… 如果陣列僅包含一個元素，則表達式 1 < 1 將不會傳回 true，因此我們可以保護自己免受陣列只有一個元素或根本沒有元素的情況的影響，而且程式碼看起來會更好。但我們的最終數組無論如何都沒有排序，因為...... 不可能一次性對所有人進行排序。我們必須新增另一個循環，在其中我們將逐一執行傳遞，直到獲得排序的陣列： 
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
	needIteration = false;
	for (int i = 1; i < array.length; i++) {
		if (array[i] < array[i - 1]) {
			swap(array, i, i-1);
			needIteration = true;
		}
	}
}
System.out.println(Arrays.toString(array));
所以我們的第一次排序成功了。我們在外循環 ( while) 中進行迭代，直到我們決定不再需要迭代。預設情況下，在每次新迭代之前，我們假設數組已排序，並且我們不想再迭代。因此，我們按順序檢查元素並檢查這個假設。但是，如果元素無序，我們交換元素並意識到我們不確定元素現在的順序是否正確。因此，我們想要再執行一次迭代。例如，[3,5,2]。5已經超過3了，一切都很好。但 2 小於 5。然而，[3, 2, 5] 還需要一輪，因為 3 > 2 並且需要交換它們。由於我們在循環中使用循環，因此我們的演算法的複雜性增加了。如果有 n 個元素，則變為 n * n，即 O(n^2)。這種複雜性稱為二次複雜性。據我們了解，我們無法確切知道需要多少次迭代。演算法複雜度指標的目的是顯示複雜度增加的趨勢，最壞的情況。當元素數量n改變時，運行時間會增加多少。冒泡排序是最簡單且效率最低的排序之一。有時也稱為“愚蠢排序”。相關資料：
排序演算法的理論與實踐 - 3

選擇排序

另一種排序是選擇排序。它也具有二次複雜度，稍後會詳細介紹。所以這個想法很簡單。每一遍都會選擇最小的元素並將其移動到開頭。在這種情況下，透過向右移動開始每個新通道，即，第一個通道 - 從第一個元素開始，第二通道 - 從第二個元素開始。它看起來像這樣： 
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
	int minInd = left;
	for (int i = left; i < array.length; i++) {
		if (array[i] < array[minInd]) {
			minInd = i;
		}
	}
	swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
這種排序是不穩定的，因為 相同的元素（從我們對元素進行排序的特徵的角度來看）可以改變它們的位置。維基百科文章中給了一個很好的例子：Sorting_by-selection。相關資料：
排序演算法的理論與實踐 - 4

插入排序

插入排序也具有二次複雜度，因為我們再次有一個循環中的循環。它與選擇排序有什麼不同？這種排序是「穩定的」。這意味著相同的元素不會改變它們的順序。我們排序所依據的特徵是相同的。
Java-университет 
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
	// Retrieve the value of the element
	int value = array[left];
	// Move through the elements that are before the pulled element
	int i = left - 1;
	for (; i >= 0; i--) {
		// If a smaller value is pulled out, move the larger element further
		if (value < array[i]) {
			array[i + 1] = array[i];
		} else {
			// If the pulled element is larger, stop
			break;
		}
	}
	// Insert the extracted value into the freed space
	array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
相關資料：
排序演算法的理論與實踐 - 5

穿梭排序

在簡單的排序中，還有一種──穿梭排序。但我更喜歡穿梭巴士。在我看來，我們很少談論太空梭，太空梭更多的是跑步。因此，更容易想像太空梭是如何發射到太空的。這是與該演算法的關聯。演算法的本質是什麼？這個演算法的本質是我們從左到右迭代，在交換元素時，我們檢查剩餘的所有其他元素，看看是否需要重複交換。 
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
	if (array[i] < array[i - 1]) {
		swap(array, i, i - 1);
		for (int z = i - 1; (z - 1) >= 0; z--) {
			if (array[z] < array[z - 1]) {
				swap(array, z, z - 1);
			} else {
				break;
			}
		}
	}
}
System.out.println(Arrays.toString(array));
相關資料：
排序演算法的理論與實踐 - 6

希爾排序

另一種簡單的排序是希爾排序。它的本質類似於冒泡排序，但是每次迭代我們所比較的元素之間都有不同的差距。每次迭代它都會減半。這是一個範例實作： 
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a difference between the elements
while (gap >= 1) {
    for (int right = 0; right < array.length; right++) {
        // Shift the right pointer until we can find one that
        // there won't be enough space between it and the element before it
       for (int c = right - gap; c >= 0; c -= gap) {
           if (array[c] > array[c + gap]) {
               swap(array, c, c + gap);
           }
        }
    }
    // Recalculate the gap
    gap = gap / 2;
}
System.out.println(Arrays.toString(array));
相關資料：
排序演算法的理論與實踐 - 7

歸併排序

除了所示的簡單排序之外，還有更複雜的排序。例如，歸併排序。首先，遞歸會對我們有幫助。其次，我們的複雜性將不再像我們習慣的那樣是二次的。此演算法的複雜度是對數的。寫成 O(n log n)。那麼就讓我們這樣做吧。首先，讓我們來寫一個對排序方法的遞歸呼叫： 
public static void mergeSort(int[] source, int left, int right) {
        // Choose a separator, i.e. split the input array in half
        int delimiter = left + ((right - left) / 2) + 1;
        // Execute this function recursively for the two halves (if we can split(
        if (delimiter > 0 && right > (left + 1)) {
            mergeSort(source, left, delimiter - 1);
            mergeSort(source, delimiter, right);
        }
}
現在，讓我們為其添加一個主要操作。這是我們的超級方法及其實現的範例： 
public static void mergeSort(int[] source, int left, int right) {
        // Choose a separator, i.e. split the input array in half
        int delimiter = left + ((right - left) / 2) + 1;
        // Execute this function recursively for the two halves (if we can split(
        if (delimiter > 0 && right > (left + 1)) {
            mergeSort(source, left, delimiter - 1);
            mergeSort(source, delimiter, right);
        }
        // Create a temporary array with the desired size
        int[] buffer = new int[right - left + 1];
        // Starting from the specified left border, go through each element
        int cursor = left;
        for (int i = 0; i < buffer.length; i++) {
            // We use the delimeter to point to the element from the right side
            // If delimeter > right, then there are no unadded elements left on the right side
            if (delimiter > right || source[cursor] > source[delimiter]) {
                buffer[i] = source[cursor];
                cursor++;
            } else {
                buffer[i] = source[delimiter];
                delimiter++;
            }
        }
        System.arraycopy(buffer, 0, source, left, buffer.length);
}
讓我們透過呼叫 來運行該範例mergeSort(array, 0, array.length-1)。正如您所看到的，本質在於我們將一個陣列作為輸入，該數組指示要排序的部分的開頭和結尾。當排序開始時，這是數組的開頭和結尾。接下來我們計算 delimiter - 分隔符號的位置。如果除法器可以分成兩個部分，那麼我們會對除法器將陣列分成的部分進行遞歸排序。我們準備一個額外的緩衝區數組，在其中選擇已排序的部分。接下來，我們將遊標放在要排序的區域的開頭，並開始遍歷我們準備好的空數組中的每個元素，並用最小的元素填充它。如果遊標指向的元素小於除數指向的元素，我們將該元素放入緩衝區數組中並移動遊標。否則，我們將分隔符號指向的元素放入緩衝區數組中並移動分隔符號。一旦分隔符號超出排序區域的邊界或填入整個數組，指定的範圍就被認為是排序的。 相關資料：
排序演算法的理論與實踐 - 8

計數排序和基數排序

另一個有趣的排序演算法是計數排序。這種情況下的演算法複雜度將為 O(n+k)，其中 n 是元素的數量，k 是元素的最大值。這個演算法有一個問題：我們需要知道數組中的最小值和最大值。以下是計數排序的範例實作： 
public static int[] countingSort(int[] theArray, int maxValue) {
        // Array with "counters" ranging from 0 to the maximum value
        int numCounts[] = new int[maxValue + 1];
        // In the corresponding cell (index = value) we increase the counter
        for (int num : theArray) {
            numCounts[num]++;
        }
        // Prepare array for sorted result
        int[] sortedArray = new int[theArray.length];
        int currentSortedIndex = 0;
        // go through the array with "counters"
        for (int n = 0; n < numCounts.length; n++) {
            int count = numCounts[n];
            // go by the number of values
            for (int k = 0; k < count; k++) {
                sortedArray[currentSortedIndex] = n;
                currentSortedIndex++;
            }
        }
        return sortedArray;
    }
據我們了解，當我們必須事先知道最小值和最大值時，這是非常不方便的。還有另一種演算法——基數排序。我在這裡僅以視覺方式展示該演算法。實現方式見材料：
排序演算法的理論與實踐 - 9
材料：
排序演算法的理論與實踐 - 10

Java快速排序

好吧，甜點 - 最著名的演算法之一：快速排序。它具有演算法複雜性，即我們有 O(n log n)。這種排序也稱為霍爾排序。有趣的是，該演算法是霍爾在蘇聯期間發明的，他在莫斯科大學學習電腦翻譯，並正在開發一本俄英短語手冊。該演算法也用於 Java 中 Arrays.sort 中更複雜的實作。Collections.sort 怎麼樣？我建議您親自看看它們是如何“在幕後”排序的。所以，代碼： 
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
        int leftMarker = leftBorder;
        int rightMarker = rightBorder;
        int pivot = source[(leftMarker + rightMarker) / 2];
        do {
            // Move the left marker from left to right while element is less than pivot
            while (source[leftMarker] < pivot) {
                leftMarker++;
            }
            // Move the right marker until element is greater than pivot
            while (source[rightMarker] > pivot) {
                rightMarker--;
            }
            // Check if you don't need to swap elements pointed to by markers
            if (leftMarker <= rightMarker) {
                // The left marker will only be less than the right marker if we have to swap
                if (leftMarker < rightMarker) {
                    int tmp = source[leftMarker];
                    source[leftMarker] = source[rightMarker];
                    source[rightMarker] = tmp;
                }
                // Move markers to get new borders
                leftMarker++;
                rightMarker--;
            }
        } while (leftMarker <= rightMarker);

        // Execute recursively for parts
        if (leftMarker < rightBorder) {
            quickSort(source, leftMarker, rightBorder);
        }
        if (leftBorder < rightMarker) {
            quickSort(source, leftBorder, rightMarker);
        }
}
這裡的一切都很可怕，所以我們會弄清楚的。對於輸入數組int[]來源，我們設定兩個標記，左 (L) 和右 (R)。第一次呼叫時，它們會符合陣列的開頭和結尾。接下來，確定支撐元素，即pivot。之後，我們的任務是將小於 的值pivot向左移動pivot，將大於的值向右移動。為此，首先移動指針，L直到找到大於 的值pivot。如果沒有找到更小的值，則 L совпадёт с pivot. Потом двигаем указатель R пока не найдём меньшее, чем pivot meaning. Если меньшее meaning не нашли, то R совпадёт с pivot. Далее, если указатель L находится до указателя R or совпадает с ним, то пытаемся выполнить обмен элементов, если элемент L меньше, чем R. Далее L сдвигаем вправо на 1 позицию, R сдвигаем влево на одну позицию. Когда левый маркер L окажется за правым маркером R это будет означать, что обмен закончен, слева от pivot меньшие значения, справа от pivot — большие значения. После этого рекурсивно вызываем такую же сортировку для участков массива от начала сортируемого участка до правого маркера и от левого маркера до конца сортируемого участка. Почему от начала до правого? Потому что в конце итерации так и получится, что правый маркер сдвинется настолько, что станет границей части слева. Этот алгоритм более сложный, чем простая sorting, поэтому его лучше зарисовать. Возьмём белый лист бумаги, запишем: 4 2 6 7 3 , а Pivot по центру, т.е. число 6. Обведём его в круг. Под 4 напишем L, под 3 напишем R. 4 меньше чем 6, 2 меньше чем 6. Total, L переместился на положение pivot, т.к. по условию L не может уйти дальше, чем pivot. Напишем снова 4 2 6 7 3 , обведём 6 вкруг ( pivot) и поставим под ним L. Теперь двигаем указатель R. 3 меньше чем 6, поэтому ставим маркер R на цифру 3. Так How 3 меньше, чем pivot 6 выполняем swap, т.е. обмен. Запишем результат: 4 2 3 7 6 , обводим 6 вкруг, т.к. он по прежнему pivot. Указатель L на цифре 3, указатель R на цифре 6. Мы помним, что двигаем указатели до тех пор, пока L не зайдём за R. L двигаем на следующую цифру. Тут хочется разобрать два варианта: если бы предпоследняя цифра была 7 и если бы она была не 7, а 1. Предпоследня цифра 1: Сдвинули указатель L на цифру 1, т.к. мы можем двигать L до тех пор, пока указатель L указывает на цифру, меньшую чем pivot. А вот R мы не можем сдвинуть с 6, т.к. R не мы можем двигать только если указатель R указывает на цифру, которая больше чем pivot. swap не делаем, т.к. 1 меньше 6. Записываем положение: 4 2 3 1 6, обводим pivot 6. L сдвигается на pivot и больше не двигается. R тоже не двигается. Обмен не производим. Сдвигаем L и R на одну позицию и подписываем цифру 1 маркером R, а L получается вне числа. Т.к. L вне числа — ничего не делаем, а вот часть 4 2 3 1 выписываем снова, т.к. это наша левая часть, меньшая, чем pivot 6. Выделяем новый pivot и начинаем всё снова ) Предпоследняя цифра 7: Сдвинули указать L на цифру 7, правый указатель не можем двигать, т.к. он уже указывает на pivot. т.к. 7 больше, чем pivot, то делаем swap. Запишем результат: 4 2 3 6 7, обводим 6 кружком, т.к. он pivot. Указатель L теперь сдвигается на цифру 7, а указатель R сдвигается на цифру 3. Часть от L до конца нет смысла сортировать, т.к. там всего 1 элемент, а вот часть от 4 до указателя R отправляем на сортировку. Выбираем pivot и начинаем всё снова ) Может на первый взгляд показаться, что если расставить много одинаковых с pivot значений, это сломает алгоритм, но это не так. Можно напридумывать каверзных вариантов и на бумажке убедиться, что всё правильно и подивиться, How такие простые действия предоставляют такой надёжный механизм. Единственный минус — такая sorting не является стабильной. Т.к. при выполнении обмена одинаковые элементы могут поменять свой порядок, если один из них встретился до pivot до того, How другой элемент попал в часть до pivot при помощи обмена. Материал:

Итог

Выше мы рассмотрели "джентельменский" набор алгоритмов сортировки, реализованных на Java. Алгоритмы вообще штука полезная, How с прикладной точки зрения, так и с точки зрения развития мышления. Некоторые из них попроще, некоторые посложнее. По Howим-то умные люди защищали различные работы на степени, а по другим писали толстые-толстые книги. Надеюсь, приложенный к статье материал позволит вам узнать ещё больше, так How это обзорная статья, которая и так получилась увесистой. И цель её — дать небольшое вступление. Про введение в алгоритмы можно так же прочитать ознакомиться с книгой " Грокаем Алгоримы". Также мне нравится плэйлист от Jack Brown — AQA Decision 1 1.01 Tracing an Algorithm. Ради интереса можно посмотреть на визуализацию алгоритмов на sorting.at и visualgo.net. Ну и весь Youtube к вашим услугам.
留言
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION