排序是程式設計中最常見也是最必要的操作之一。它表示某些元素集按特定順序的排序。本文介紹 Java 中數組排序的標準方法。
![Java university]()
![Java webinar]()
簡單介紹一下排序
所以，排序就是對一組資料進行排序。在我們的例子中，是數組。對數組或其他資料結構進行排序的目的是為了更輕鬆地查找、操作或解析集合中的資料。程式設計師經常需要排序，因此任何程式語言都包含用於對數組、列表和其他有序資料結構進行排序的內建方法。若要使用此類方法，請呼叫它們。操作盡可能簡化。通常，內建方法會得到最大程度的最佳化；在大多數情況下，將它們用於您的工作或專案是一個好主意。然而，幾乎每個程式設計師在學習的過程中，都需要自己實作排序演算法。因此，這些完美的練習可以教你理解程式設計的本質。另外，有時你在工作中需要非標準的排序方法。排序演算法有很多種。它們各有優缺點，取決於資料集的類型或大小。標準排序演算法包括冒泡排序、選擇排序、插入排序、合併排序和快速排序。Java 中對陣列進行排序的內建方法：Arrays.sort
讓我們從最簡單的開始。有人已經用Java為我們寫了一個陣列排序的方法。方法位於Arrays類別中，更具體地說是java.util.Arrays中。此類別包含用於處理陣列的各種方法，例如排序和搜尋。Arrays.sort方法提供了一種在 Java 中對陣列進行排序的便捷方法，無論它們包含字串、整數或其他元素。Java 中的Arrays.sort方法有多種變體。以下是Arrays類別中一些常用的排序方法：- Arrays.sort(Array)：以它對原始型別或物件的陣列依升序排序。它使用元素的自然順序。
- Arrays.sort(Array, fromIndex, toIndex)：此重載排序方法可讓您僅對 fromIndex 和 toIndex 參數指定的 Array 的一部分進行排序。
- Arrays.sort(Array, comparator)：此函數用於使用自訂比較器對物件陣列進行排序。比較器定義元素的順序。
- Arrays.parallelSort(Array)：此方法版本並行對陣列進行排序，利用多個執行緒來提高效能。這對於對大型數組進行排序很有好處。
- Arrays.parallelSort(Array, fromIndex, toIndex)：parallelSort 方法的此重載版本允許對 Array 中的特定範圍的元素進行排序。
範例 1：對字串進行排序
假設我們有一系列弦樂器：「小提琴」、「中提琴」、「大提琴」和「低音提琴」。我們可以使用Array.sort方法按字母順序排列它們。import java.util.Arrays;
//Arrays.sort example
public class StringSortExample {
public static void main(String[] args) {
String[] instruments = {"violin", "viola", "cello", "double bass"};
Arrays.sort(instruments);
System.out.println("Sorted Instruments:");
for (String instrument : instruments) {
System.out.println(instrument);
}
}
}
樂器分類： 大提琴 低音提琴 中提琴 小提琴
在此程式中，首先，我們匯入java.util.Arrays類別以存取Array.sort方法。然後我們建立一個名為instruments 的字串數組，其中包含樂器名稱。之後，我們呼叫Arrays.sort(instruments)。因此，此方法會取得數組，根據元素的自然順序（按字母順序）按升序對元素進行排序。最後，我們循環遍歷排序後的陣列並列印出每個樂器。
範例 2：對整數排序
讓我們考慮另一個範例，其中我們按升序對整數數組進行排序。import java.util.Arrays;
public class IntegerSortExample {
public static void main(String[] args) {
int[] numbers = {8, 2, 7, 3, 1, 5};
//sort an array using Arrays.sort
Arrays.sort(numbers);
System.out.println("Sorted Numbers:");
for (int number : numbers) {
System.out.println(number);
}
}
}
排序數字：1 2 3 5 7 8
在這裡，我們建立一個名為 number 的整數數組，其中包含多個未排序的元素。接下來，我們呼叫Arrays.sort(numbers)對陣列進行升序排序。請注意，Array.sort方法就地修改原始陣列。因此，要保留原始Array，請在排序之前複製一份。
範例 3：降序排列
那麼降序排序呢？使用Arrays.sort也很容易。只需使用自訂比較器即可。這是一個例子：import java.util.Arrays;
import java.util.Comparator;
//Arrays.sort with custom comparator example
public class DescendingSortExample {
public static void main(String[] args) {
Integer[] numbers = {8, 2, 7, 3, 1, 5};
//sort an Array using Arrays.sort
Arrays.sort(numbers, Comparator.reverseOrder());
System.out.println("Sorted Numbers (Descending):");
for (int number : numbers) {
System.out.println(number);
}
}
}
排序數字（降序）：8 7 5 3 2 1
這裡我們有一個名為 number 的整數陣列。透過將Comparator.reverseOrder()作為第二個參數傳遞給Arrays.sort方法，我們指定了一個自訂比較器，該比較器按降序對元素進行排序。Comparator.reverseOrder ()方法傳回一個反轉元素自然順序的比較器。請注意，這裡我們使用 Integer 包裝類別而不是原始 int 類型，因為Comparator.reverseOrder()方法需要物件。如果您有一個原始 int 值數組，則還需要在使用此方法之前將它們轉換為Integer物件。使用自訂比較器，您可以使用Java 中的 Arrays.sort方法輕鬆地按降序對陣列進行排序。
Java自寫經典排序演算法
如果您正在獨立學習電腦科學或在大學學習電腦科學，您已經看過陣列排序作業。有許多不同的排序演算法，我們將在本文中實作其中一些。一般來說，演算法越容易實現，其效率就越低。程式設計師透過演算法的運行時間和資源消耗的記憶體來衡量演算法的效率。這不是我們文章的主題，但我們提到Java 中的Arrays.sort是一種有效的演算法。冒泡排序
我們先從最受學生歡迎的演算法開始：冒泡排序。很簡單：該演算法比較兩個元素，如果順序錯誤則交換它們，依此類推，直到數組末尾。事實證明，較小的元素「漂浮」到 Array 的末尾，就像汽水中的氣泡浮到頂部一樣。public class BubbleSort {
public static void bubbleSort(int[] myArray) {
int n = myArray.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (myArray[j] > myArray[j + 1]) {
// Swap myArray[j] and myArray[j+1]
int temp = myArray[j];
myArray[j] = myArray[j + 1];
myArray[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {18, 28, 2, 7, 90, 45};
System.out.println("Array before sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
bubbleSort(arr);
System.out.println("\nArray after sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
排序前的陣列： 18 28 2 7 90 45 排序後的陣列： 2 7 18 28 45 90
選擇排序
選擇演算法透過重複從未排序部分中尋找最小元素並將其放在開頭來對陣列進行排序。我們用 Java 來寫：public class SelectionSort {
public static void selectionSort(int[] myArray) {
int n = myArray.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
// Find the index of the minimum element in the unsorted part of the array
for (int j = i + 1; j < n; j++) {
if (myArray[j] < myArray[minIndex]) {
minIndex = j;
}
}
// Swap the minimum element with the first element of the unsorted part
int temp = myArray[minIndex];
myArray[minIndex] = myArray[i];
myArray[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {18, 28, 45, 2, 90, 7};
System.out.println("Array before sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
selectionSort(arr);
System.out.println("\nArray after sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
排序前的陣列： 18 28 45 2 90 7 排序後的陣列： 2 7 18 28 45 90
讓我們逐步解釋一下。外部循環從陣列的開頭迭代到倒數第二個元素（最多 n-1）。此循環逐一選擇每個元素作為Array未排序部分的起點。在外循環內部，我們將minIndex初始化為目前索引i ，假設它是Array未排序部分中最小項的索引。內部循環從i+1開始，一直到Array的最後一個元素。它透過將每個元素與當前最小元素 ( arr[minIndex] ) 進行比較來搜尋數組未排序部分中最小項目的索引。如果我們找到一個小於目前最小元素的元素，我們將minIndex更新為新的最小元素的索引。內部循環完成後，我們在Array的未排序部分找到了最小元素的索引。然後，我們使用臨時變數 temp 將最小元素與未排序部分的第一個元素交換。外部循環繼續進行，直到所有元素都已排序，逐漸擴展Array的已排序部分。最後，在呼叫selectionSort方法之前和之後，在main方法中列印排序後的Array。
歸併排序
歸併排序是一種分而治之的演算法，它遞歸地將數組分成更小的子數組，對它們進行排序，然後將它們合併以獲得排序後的數組。歸併排序非常穩定並且被廣泛使用，特別是在需要穩定性和保證最壞情況時間複雜度的情況下。public class MergeSort {
//Merge Sort array
public static void mergeSort(int[] myArray) {
if (myArray.length <= 1) {
return;
}
int mid = myArray.length / 2;
int[] left = new int[mid];
int[] right = new int[myArray.length - mid];
System.arraycopy(myArray, 0, left, 0, mid);
System.arraycopy(myArray, mid, right, 0, myArray.length - mid);
mergeSort(left);
mergeSort(right);
merge(myArray, left, right);
}
public static void merge(int[] arr, int[] left, int[] right) {
int i = 0; // index for left subarray
int j = 0; // index for right subarray
int k = 0; // index for merged array
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left.length) {
arr[k++] = left[i++];
}
while (j < right.length) {
arr[k++] = right[j++];
}
}
public static void main(String[] args) {
int[] arr = {18, 2, 28, 7, 90, 45};
System.out.println("Array before sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
mergeSort(arr);
System.out.println("\nArray after sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
排序前的陣列： 18 2 28 7 90 45 排序後的陣列： 2 7 18 28 45 90
讓我們更準確地解釋它是如何運作的。此演算法遞歸地將數組分成兩部分，直到達到基本情況（當數組有一個或零個元素時）。然後它使用 merge 方法將排序後的兩半重新合併在一起。merge 方法接受三個陣列作為輸入：原始陣列和左右子數組（左和右）。它比較左右子數組中的元素，並將它們按排序順序 合併到原始數組中。
插入排序
插入排序的工作原理是重複地將未排序部分中的元素插入到已排序部分中的正確位置。它對於小數據集或接近排序的數據表現良好。public class InsertionSort {
public static void insertionSort(int[] myArray) {
int n = myArray.length;
for (int i = 1; i < n; i++) {
int key = myArray[i];
int j = i - 1;
while (j >= 0 && myArray[j] > key) {
myArray[j + 1] = myArray[j];
j--;
}
myArray[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {18, 90, 7, 28, 45, 2};
System.out.println("Array before sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
insertionSort(arr);
System.out.println("\nArray after sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
排序前的陣列： 18 90 7 28 45 2 排序後的陣列： 2 7 18 28 45 90
這裡的insertionSort方法實作了插入排序演算法。它迭代數組並將每個元素視為鍵。它將鍵與其前面的元素進行比較，如果它們更大，則將它們向前移動一個位置，從而有效地移動元素，以便在正確的位置為鍵騰出空間。
外循環從陣列的第二個元素 ( i = 1 ) 迭代到最後一個元素。內部循環從目前元素 ( arr[i] ) 開始並向後移動 ( j = i - 1 )，直到找到鍵的正確位置或到達 Array 的開頭。在內循環內部，如果某個元素 ( arr[j] ) 大於鍵，則會向前移動一位 ( arr[j + 1] = arr[j] ) 以為鍵騰出空間。此過程將持續進行，直到找到鑰匙的正確位置。內部循環完成後，密鑰被放置在正確的位置（arr[j + 1] = key）。在 main 方法中，在使用insertSort方法排序之前和之後建立並列印範例陣列。
快速排序
快速排序是一種分而治之的演算法，它選擇一個主元元素並圍繞該主元對陣列進行分區。一般來說，對於中小型資料集，快速排序由於其常數因子較低而比合併排序更快。public class QuickSort {
public static void quickSort(int[] myArray, int low, int high) {
if (low < high) {
int pivotIndex = partition(myArray, low, high);
quickSort(myArray, low, pivotIndex - 1);
quickSort(myArray, pivotIndex + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {18, 28, 2, 90, 7, 45};
System.out.println("Array before sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
quickSort(arr, 0, arr.length - 1);
System.out.println("\nArray after sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
排序前的陣列： 18 28 2 90 7 45 排序後的陣列： 2 7 18 28 45 90
所以這裡我們有三種方法來實現快速排序。QuickSort方法採用三個參數：要排序的陣列、子數組的低索引和子數組的高索引。首先，它檢查子數組是否有多個元素。如果是，則使用分區方法選擇一個主元，並對主元之前的子數組遞歸排序，並對主元之後的子數組遞歸排序。分區法選擇主元作為子數組的最後一個元素 ( arr[high] )。它將分區索引 (i) 設為低索引減 1。然後從低索引迭代到高索引 - 1，並檢查每個元素是否小於或等於主元。如果是，它將與分區索引 (i) 處的元素交換該元素並遞增分區索引。最後，它將主元元素與分區索引 + 1 處的元素交換並傳回分區索引。分區法選擇主元作為子數組的最後一個元素 ( arr[high] )。它將分區索引 (i) 設為低索引減 1。然後從低索引迭代到高索引 - 1，並檢查每個項目是否小於或等於主元。如果是，它將與分區索引 (i) 處的元素交換該元素並遞增分區索引。最後，它將主元元素與分區索引 + 1 處的元素交換並傳回分區索引。swap 方法是一種實用方法，用於交換Array中的兩個元素。在main方法中，在使用QuickSort方法排序之前和之後建立並列印範例陣列。