排序是我們對對象執行的基本操作之一。即使在孩提時代，孩子們在培養思維能力的過程中也被教導要進行分類。計算機和軟件也不例外。Java 中有各種各樣的排序算法。我建議您檢查一下它們是什麼以及它們是如何工作的。如果有一天你在面試中被問及其中一個怎麼辦？
L 變得等於
介紹
對元素進行排序是開發人員必須了解的算法類別之一。如果說我在學校的時候計算機科學曾經不被重視，那麼今天的學生必須能夠實現和理解排序算法。最簡單的基本算法是使用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 更改為數組中的最後一個元素。事實上，我們只是獲取數組中的每個元素並打印其內容。數組中的元素越多，代碼完成所需的時間就越長。也就是說，ifn是元素的數量，whenn = 10程序的運行時間是 when 的兩倍n = 5。如果我們的程序只有一個循環，執行時間會線性增長：元素越多，執行時間越長。事實證明，上述算法在線性時間內工作（n 的線性函數）。在這種情況下，我們稱算法的複雜度為“O(n)”。這種表示法也稱為“大 O”或“漸近行為”。但你只能記住“
最簡單的排序算法（冒泡排序）
假設我們有一個數組，我們可以遍歷它。偉大的。現在讓我們嘗試按升序對其進行排序。這是什麼意思？這意味著給定兩個元素（例如，a = 6, b = 5），我們必須重新排列aifb大於a（bif 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));
array[i] < array[i-1]對索引無效0。這樣做還可以保護我們免受數組沒有元素或只有一個元素的情況的影響，並且它使代碼看起來更好。但是生成的數組仍然沒有排序，因為一次傳遞不足以進行排序。我們將不得不添加另一個循環，在這個循環中我們將一次又一次地執行遍歷，直到我們得到一個排序的數組：
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變化，執行時間會增加多少。冒泡排序是最簡單且效率最低的排序算法之一。它有時也被稱為“愚蠢的排序”。關於這個主題的材料：
選擇排序
另一種排序算法是選擇排序。它還具有二次復雜性，但稍後會詳細介紹。所以這個想法很簡單。在每次傳遞中，我們選擇最小的元素並將其移動到開頭。此外，每次通過都開始向右邁出一步。換句話說，第一遍從第零個元素開始，第二遍從第一個元素開始，依此類推。它看起來像這樣：
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));
插入排序
插入排序也有二次復雜度，因為我們又在一個循環中有一個循環。是什麼讓插入排序不同？這種排序算法是“穩定的”。這意味著相同的元素不會改變它們的相對順序。同樣，我們的意思是根據我們排序所依據的特徵來表示相同。
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
穿梭排序
還有另一種簡單的排序算法：穿梭排序。這也稱為雙向冒泡排序或調酒器排序。這些替代名稱告訴我們，航天飛機類型與航天飛機無關。這是關於來回移動的東西。現在，當您想到這個算法時，您可以想到這一點。算法的本質是什麼？該算法的本質是我們從左到右迭代，交換元素並檢查是否需要交換另一個方向上剩餘的任何元素。
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));
殼排序
另一種簡單的排序算法是 shell 排序。它的要點類似於冒泡排序，但在每次迭代中，我們在比較元素之間有不同的差距。每次迭代都會將其減半。這是一個實現：
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 gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap 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));
合併排序
除了這些簡單的排序算法，還有更複雜的排序算法。例如歸併排序。有兩點需要注意。首先，遞歸在這裡拯救了我們。其次，算法的複雜度不再像我們習慣的那樣是二次的。該算法的複雜度是對數的。這寫成O(n log n). 因此，讓我們實施它。首先，我們將編寫對排序方法的遞歸調用：
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
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) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
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). 如您所見，該過程歸結為接受輸入數組以及需要排序的部分的開頭和結尾的指示。當排序開始時，這些是數組的開頭和結尾。然後我們計算定界符，這是我們將拆分數組的索引。如果數組可以分為兩部分，那麼我們對數組的兩半遞歸調用sort方法。我們準備了一個輔助緩衝區，我們將在其中插入已排序的部分。接下來，在要排序的部分的開頭設置索引，並開始遍歷空緩衝區的每個元素，用最小的元素填充它。如果索引指向的元素小於定界符指向的元素，我們將元素放入緩衝區並移動索引。否則，我們將分隔符指向的元素放入緩衝區並移動分隔符。一旦分隔符超出了正在排序的部分的邊界，或者我們填充了整個數組，指定的範圍就被認為是已排序的。關於這個主題的材料：
計數排序和基數排序
另一個有趣的排序算法是計數排序。這裡的算法複雜度為O(n+k)，其中n是元素個數，k是元素的最大值。該算法確實有一個缺點：我們需要知道數組中的最小值和最大值。下面是計數排序的例子：
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
快速排序
好了，甜點時間到了——快速排序，最著名的排序算法之一。它具有對數複雜度：O(n log n)。這種排序算法是由 Tony Hoare 開發的。有趣的是，他在蘇聯生活期間發明了它，在那裡他在莫斯科大學學習機器翻譯並開發了一本俄英短語手冊。更重要的是，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 as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
int[]source)，我們創建兩個標記：左 ( L) 和右 ( R)。在第一次方法調用期間，它們對應於數組的開頭和結尾。然後我們確定樞軸元素，它被恰當地命名為pivot。此後，我們的任務是將小於 的值移到pivot的左側pivot，將大於 的值移到右側。為此，我們首先移動L標記，直到找到大於 的值pivot。如果沒有找到更小的值，則pivot。然後我們移動
R標記，直到找到一個小於 的值
pivot。如果沒有找到更大的值，則
R變為等於
pivot。接下來，如果
L標記在
R標記之前或與其重合，那麼如果
L元素小於
R元素，我們將嘗試交換元素。然後我們
L向右移動 1，我們
R向左移動 1。當
L標記超出
R標記時，表示交換完成：較小的值在 的左側
pivot，較大的值在 的右側
pivot. 在此之後，我們在子數組上遞歸調用相同的排序方法——從要排序的部分的開頭到右標記，從左標記到要排序的部分的末尾。為什麼從開始到右邊的標記？因為在迭代結束時，事實證明右側標記移動到足以成為左側部分的邊界。這個算法比簡單的排序要復雜，所以最好畫個草圖。拿一張白紙，寫上：4 2 6 7 3。然後寫
pivot在中間，也就是數字6下面。把它圈起來。在 4 下，寫
L，在 3 下，寫
R。4 小於 6，2 小於 6。我們最終移動
L到該
pivot位置，因為
L不能移動過去
pivot, 根據條件。再寫 4 2 6 7 3。圈出 6 (
pivot) 並放在
L它下面。現在移動
R標記。3 小於 6，所以將
R標記放在 3 上。由於 3 小於 6 (
pivot)，我們執行
swap. 寫出結果：4 2 3 7 6。圈出6，因為還是那個
pivot。標記
L在 3 上。
R標記在 6 上。請記住，我們移動標記直到
L超出
R。移動
L到下一個數字。在這裡我想探討兩種可能性：1）倒數第二個數字為 7 的情況和 2）倒數第二個數字為 1 而不是 7 的情況。
如果倒數第二個數字為 1：將標記移動
L到 1，因為我們可以移動
L只要
Lmarker 指向一個小於
pivot. 但是我們不能離開
R6，因為只有當標記指向大於 的數字時，我們才能移動
RR。
pivot我們不執行 a
swap，因為 1 小於 6。寫出當前情況：4 2 3 1 6。圈出 6 (
pivot)。
L移動
pivot並停止移動。
R不動。我們不執行交換。移動一個位置
L。
R將標記寫
R在 1 下。
L標記超出範圍。因為
L是越界的，我們什麼都不做。但是，我們再次寫 4 2 3 1，因為這是我們的左側，小於
pivot(6)。選擇新的
pivot並重新開始一切:)
如果倒數第二個數字是 7：將標記移動
L到 7。我們無法移動右側標記，因為它已經指向軸心。7 大於
pivot，所以我們執行 a
swap。寫出結果：4 2 3 6 7。圈出6，因為它是
pivot。標記
L現在移到 7，標記
R移到 3。從頭到尾對部分進行排序沒有意義
L，因為只有 1 個元素。但是，我們將 4 中的部分發送到
R標記器進行排序。我們選擇 a
pivot並重新開始 :) 乍一看，如果你添加很多等於
pivot，那麼你就會破壞算法。但事實並非如此。您可以想出巧妙的組合，並在紙上說服自己一切都是正確的，並驚嘆如此簡單的操作實現瞭如此可靠的排序機制。唯一的缺點是這種排序算法不穩定。
pivot因為如果在另一個元素交換到之前的部分之前遇到其中一個元素，交換可能會改變相同元素的相對順序
pivot。
GO TO FULL VERSION