HOWTO · Java
在 Java 中不使用 sort() 方法對陣列進行排序
瞭解如何在不使用 sort() 方法的情況下在 Java 中對陣列進行排序
本頁內容
不呼叫 Arrays.sort()，也能透過比較陣列元素並自行調整位置，將 Java 陣列排序。這有助於學習排序原理，也適用於作業要求手動實作的情況。Java 的 Arrays.toString() 可以顯示陣列，但不會替陣列排序。
以下範例會將整數陣列按升冪排序。氣泡排序、選擇排序和插入排序的執行步驟較容易追蹤；合併排序和快速排序則示範遞迴的分治方法。每段程式碼都是完整的 Java 程式。提供的執行證據顯示，五個範例的結果相同：[11, 12, 22, 25, 34, 64, 90]。
在 Java 中不使用 Arrays.sort() 對陣列排序
排序演算法會調整陣列元素的位置，直到它們符合指定的順序。若要將整數按升冪排列，基本做法是比較數值，並將較小的值移到較大的值之前。以下各種演算法都以不同方式運用這個原則。除了合併排序在合併資料時會使用暫存陣列，其他演算法都直接修改輸入陣列。
以小型範例來說，起始陣列是 {64, 34, 25, 12, 22, 11, 90}，目標則是 {11, 12, 22, 25, 34, 64, 90}。各個實作都刻意不使用 Arrays.sort()；Arrays.toString() 只用來格式化陣列，方便顯示內容。
氣泡排序
氣泡排序會反覆走訪相鄰元素。如果左邊的值大於右邊的值，就交換兩者。每次完整走訪後，未排序部分中最大的值會移到末端。如果某次走訪沒有任何變動，swapped 旗標就會讓迴圈提早停止。此版本的最壞時間複雜度是 O(n²)，因此較適合小型輸入或教學示範。
每個範例都宣告了名為 Main 的類別，因此請一次儲存並執行一個範例，檔名使用 Main.java。執行此範例：
本節中的程式碼以及顯示的標籤或輸出仍為英文。
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] values = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(values);
System.out.println(Arrays.toString(values));
}
static void bubbleSort(int[] values) {
for (int end = values.length - 1; end > 0; end--) {
boolean swapped = false;
for (int i = 0; i < end; i++) {
if (values[i] > values[i + 1]) {
int temp = values[i];
values[i] = values[i + 1];
values[i + 1] = temp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
}
[11, 12, 22, 25, 34, 64, 90]
選擇排序
選擇排序會在概念上將陣列分成已排序的前綴，以及剩下尚未排序的值。每一輪都會搜尋未排序部分中的最小值，再將它與第一個未排序位置的值交換。例如，第一輪會找到 11 並將它移到索引 0；下一輪會找到 12 並移到索引 1。無論陣列原本的順序如何，它都會進行 O(n²) 次比較，但交換次數只有線性級別。
本節中的程式碼以及顯示的標籤或輸出仍為英文。
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] values = {64, 34, 25, 12, 22, 11, 90};
selectionSort(values);
System.out.println(Arrays.toString(values));
}
static void selectionSort(int[] values) {
for (int i = 0; i < values.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < values.length; j++) {
if (values[j] < values[minIndex]) {
minIndex = j;
}
}
int temp = values[i];
values[i] = values[minIndex];
values[minIndex] = temp;
}
}
}
[11, 12, 22, 25, 34, 64, 90]
插入排序
插入排序會由左至右逐步擴大已排序的前綴。它先將下一個值存入 key，把前綴中較大的值向右移一格，再將 key 放入空出的位置。每一輪開始時，i 之前的所有元素都已排序。這讓演算法容易追蹤；對小型或幾乎已排序的陣列也可能很有效率，但最壞時間複雜度是 O(n²)。
本節中的程式碼以及顯示的標籤或輸出仍為英文。
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] values = {64, 34, 25, 12, 22, 11, 90};
insertionSort(values);
System.out.println(Arrays.toString(values));
}
static void insertionSort(int[] values) {
for (int i = 1; i < values.length; i++) {
int key = values[i];
int j = i - 1;
while (j >= 0 && values[j] > key) {
values[j + 1] = values[j];
j--;
}
values[j + 1] = key;
}
}
}
[11, 12, 22, 25, 34, 64, 90]
合併排序
合併排序會以遞迴方式將陣列切成兩半，直到每個部分只剩一個值，再合併已排序的部分。合併時，兩個索引分別追蹤兩個半部中下一個尚未使用的值，並先將較小的值複製到結果中。若兩個值相等，優先選取左側的值，便能保留它們原本的相對順序。此實作的時間複雜度為 O(n log n)，並會在遞迴過程中配置暫存陣列，因此需要與輸入大小成正比的額外記憶體。
本節中的程式碼以及顯示的標籤或輸出仍為英文。
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] values = {64, 34, 25, 12, 22, 11, 90};
mergeSort(values);
System.out.println(Arrays.toString(values));
}
static void mergeSort(int[] values) {
if (values.length < 2) {
return;
}
int middle = values.length / 2;
int[] left = Arrays.copyOfRange(values, 0, middle);
int[] right = Arrays.copyOfRange(values, middle, values.length);
mergeSort(left);
mergeSort(right);
merge(values, left, right);
}
static void merge(int[] values, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
values[k++] = left[i++];
} else {
values[k++] = right[j++];
}
}
while (i < left.length) values[k++] = left[i++];
while (j < right.length) values[k++] = right[j++];
}
}
[11, 12, 22, 25, 34, 64, 90]
快速排序
快速排序會選擇一個樞紐值，並將目前範圍分割，使小於樞紐值的數值排在它前面，其餘值則排在後面。此實作選用最後一個值作為樞紐值。分割方法會回傳樞紐值最後所在的索引，接著透過遞迴呼叫排序其左右兩側的範圍。快速排序的時間複雜度通常是 O(n log n)，但此樞紐選擇方式遇到不利輸入（例如已排序的資料）時，可能需要 O(n²) 時間。遞迴呼叫也會使用堆疊空間。
本節中的程式碼以及顯示的標籤或輸出仍為英文。
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] values = {64, 34, 25, 12, 22, 11, 90};
quickSort(values, 0, values.length - 1);
System.out.println(Arrays.toString(values));
}
static void quickSort(int[] values, int low, int high) {
if (low >= high) {
return;
}
int pivotIndex = partition(values, low, high);
quickSort(values, low, pivotIndex - 1);
quickSort(values, pivotIndex + 1, high);
}
static int partition(int[] values, int low, int high) {
int pivot = values[high];
int smallerEnd = low - 1;
for (int current = low; current < high; current++) {
if (values[current] < pivot) {
smallerEnd++;
int temp = values[smallerEnd];
values[smallerEnd] = values[current];
values[current] = temp;
}
}
int pivotIndex = smallerEnd + 1;
int temp = values[pivotIndex];
values[pivotIndex] = values[high];
values[high] = temp;
return pivotIndex;
}
}
[11, 12, 22, 25, 34, 64, 90]
選擇演算法並了解其取捨
若是為了學習或排序小型陣列，氣泡排序、選擇排序和插入排序都能清楚呈現每次比較與移動；但它們的時間複雜度呈平方成長，不適合大型輸入。陣列很小或幾乎已排序時，插入排序是合理的選擇。如果需要減少寫入次數，選擇排序也有用，因為每一輪最多只交換一次；不過每一輪仍須掃描剩餘的值。
合併排序的執行時間穩定為 O(n log n)，而且適合需要穩定排序的情況，但此實作會配置暫存陣列。快速排序通常有不錯的效能，並在原陣列中完成排序；然而，這個使用最後一個元素作為樞紐值的版本，最壞情況下需要 O(n²) 時間，也會使用遞迴堆疊。正式程式碼通常應優先採用 Java 已有的排序函式庫，除非需求明確要求手動實作演算法。一般的基本型別陣列排序可使用 Arrays.sort()；只有當手動排序的行為或限制本身就是任務時，才需要學習或實作手動排序方法。
