排序是計算機科學中的重要概念之一,而在排序算法中,穩定排序和不穩定排序是兩種常見的分類方式。Java中也有多種排序算法,其中包括了穩定排序和不穩定排序。
穩定排序是指,如果有兩個元素a和b,它們在原數組中的位置為 i 和 j (i< j),并且排序后,a元素在b元素前面,那么在排序后的數組中,a元素依然會在b元素前面。也就是說,穩定排序會保持相等元素的相對位置不變。
// Java使用歸并排序(Merge Sort)作為穩定排序算法,示例代碼如下: public static void mergeSort(int[] arr, int low, int high) { if (low< high) { int mid = (low + high) / 2; mergeSort(arr, low, mid); mergeSort(arr, mid + 1, high); merge(arr, low, mid, high); } } public static void merge(int[] arr, int low, int mid, int high) { int[] temp = new int[high - low + 1]; int i = low, j = mid + 1, k = 0; while (i<= mid && j<= high) { if (arr[i]< arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i<= mid) { temp[k++] = arr[i++]; } while (j<= high) { temp[k++] = arr[j++]; } for (int x = 0; x< temp.length; x++) { arr[x + low] = temp[x]; } }
不穩定排序則是指,相等元素的順序會在排序后發生變化,即會出現原本前后順序相同的元素,排序后會出現互相顛倒的情況。
// Java使用快速排序(Quick Sort)作為不穩定排序算法,示例代碼如下: public static void quickSort(int[] arr, int low, int high) { if (low< high) { int index = partition(arr, low, high); quickSort(arr, low, index - 1); quickSort(arr, index + 1, high); } } public static int partition(int[] arr, int low, int high) { int pivot = arr[high]; int i = low; for (int j = low; j< high; j++) { if (arr[j]< pivot) { swap(arr, i, j); i++; } } swap(arr, i, high); return i; } public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
在實際使用中,我們需要根據具體的需求來選擇使用是穩定排序還是不穩定排序算法,以此來保證程序最佳性能。