Java中的排序

排序方法的選擇

1.若n較小(如n≤50)，可采用直接插入或直接選擇排序。當記錄規模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數少于直接插入，應選直接選擇排序為宜。

2.若文件初始狀態基本有序(指正序)，則應選用直接插入、冒泡或隨機的快速排序為宜；

3.若n較大，則應采用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。

衡量排序算法的優劣：

1.時間復雜度：分析關鍵字的比較次數和記錄的移動次數

2.空間復雜度：分析排序算法中需要多少輔助內存

3.穩定性：若兩個記錄A和B的關鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩定的。

排序算法分類：內部排序和外部排序。

1.內部排序：整個排序過程不需要借助于外部存儲器（如磁盤等），所有排序操作都在內存中完成。

2.外部排序：參與排序的數據非常多，數據量非常大，計算機無法把整個排序過程放在內存中完成，必須借助于外部存儲器（如磁盤）。外部排序最常見的是多路歸并排序。可以認為外部排序是由多次內部排序組成。

常用的內部排序

選擇排序

基本原理：將待排序的元素分為已排序（初始為空）和未排序兩組，依次將未排序的元素中值最小的元素放入已排序的組中。直接選擇排序簡單直觀，但性能略差；堆排序是一種較為高效的選擇排序方法，但實現起來略微復雜。

基本過程：1.在一組元素R[i]到R[n]中選擇具有最小關鍵字的元素。2.若它與這組元素中的第一個元素，則將它與這組元素中的第一個元素對調。3.去除具有最小關鍵字的元素，在剩下的元素中重復1、2步，直到剩余元素只有一個為止。

算法的時間效率：無論初始狀態如何，在第i趟排序中選擇最小關鍵碼的元素，需做n-i次比較，因此總的比較次數為：n(n-1)/2 = O(n^2)

算法的空間效率：空間效率很高，只需要一個附加程序單元用于交換，其空間效率為：O(1)

算法的穩定性：不穩定

public class SelectSort {public static void selectSort(DataWrap[] data) {System.out.println("開始排序");int arrayLength = data.length;for (int i = 0; i < arrayLength - 1; i++) {for (int j = i + 1; j < arrayLength; j++) {if (data[i].compareTo(data[j]) > 0) {DataWrap temp = data[i];data[i] = data[j];data[j] = temp;}}System.out.println(java.util.Arrays.toString(data));}}public static void main(String[] args) {DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),new DataWrap(21, "*"), new DataWrap(23, ""),new DataWrap(-30, ""), new DataWrap(-49, ""),new DataWrap(21, ""), new DataWrap(30, "*"),new DataWrap(30, "") };System.out.println("排序之前：\n" + java.util.Arrays.toString(data));selectSort(data);System.out.println("排序之后：\n" + java.util.Arrays.toString(data));}
}

堆排序

算法的時間效率：假設有n個數據，需要進行n-1次建堆，每次建堆本身耗時 logn，則其時間效率為O(nlogn)

算法的空間效率：空間效率很高，只需要一個附加程序單元用于交換，其空間效率為O(1)

算法的穩定性：不穩定

public class HeapSort {public static void heapSort(DataWrap[] data) {System.out.println("開始排序");int arrayLength = data.length;// 循環建堆for (int i = 0; i < arrayLength - 1; i++) {// 建堆builMaxdHeap(data, arrayLength - 1 - i);// 交換堆頂和最后一個元素swap(data, 0, arrayLength - 1 - i);System.out.println(java.util.Arrays.toString(data));}}// 對data數組從0到lastIndex建大頂堆private static void builMaxdHeap(DataWrap[] data, int lastIndex) {// 從lastIndex處節點（最后一個節點）的父節點開始for (int i = (lastIndex - 1) / 2; i >= 0; i--) {// k保存當前正在判斷的節點int k = i;// 如果當前k節點的子節點存在while (k * 2 + 1 <= lastIndex) {// k節點的左子節點的索引int biggerIndex = 2 * k + 1;// 如果biggerIndex小于lastIndex，即biggerIndex +1// 代表k節點的右子節點存在if (biggerIndex < lastIndex) {// 如果右子節點的值較大if (data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0) {// biggerIndex總是記錄較大子節點的索引biggerIndex++;}}// 如果k節點的值小于其較大子節點的值if (data[k].compareTo(data[biggerIndex]) < 0) {// 交換它們swap(data, k, biggerIndex);// 將biggerIndex賦給k，開始while循環的下一次循環// 重新保證k節點的值大于其左、右節點的值k = biggerIndex;} else {break;}}}}// 交換data數組中i、j兩個索引處的元素private static void swap(DataWrap[] data, int i, int j) {DataWrap temp = data[i];data[i] = data[j];data[j] = temp;}public static void main(String[] args) {DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),new DataWrap(21, "*"), new DataWrap(23, ""),new DataWrap(-30, ""), new DataWrap(-49, ""),new DataWrap(21, ""), new DataWrap(30, "*"),new DataWrap(30, "")};System.out.println("排序之前：\n" + java.util.Arrays.toString(data));heapSort(data);System.out.println("排序之后：\n" + java.util.Arrays.toString(data));}
}

冒泡排序

相鄰兩元素進行比較，如有需要則進行交換，每完成一次循環就將最大元素排在最后（如從小到大排序），下一次循環是將其它的數進行類似操作。

算法的時間效率：從冒泡排序的算法可以看出，若待排序的元素為正序，則只需進行一趟排序，比較次數為n-1次，移動元素次數為0；若待排序的元素為逆序，則需要進行n-1趟排序，比較次數為(n^2-n)/2 ，移動次數為3(n^2-n)/2，因此時間復雜度為O(n^2)

算法的空間效率：空間效率很高，只需要一個附加程序單元用于交換，其空間效率為O(1)

算法的穩定性：穩定

public class BubbleSort {public static void bubbleSort(DataWrap[] data) {System.out.println("開始排序");int arrayLength = data.length;for (int i = 0; i < arrayLength - 1; i++) {boolean flag = false;for (int j = 0; j < arrayLength - 1 - i; j++) {if (data[j].compareTo(data[j + 1]) > 0) {DataWrap temp = data[j + 1];data[j + 1] = data[j];data[j] = temp;flag = true;}}System.out.println(java.util.Arrays.toString(data));if (!flag)break;}}public static void main(String[] args) {DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),new DataWrap(21, "*"), new DataWrap(23, ""),new DataWrap(-30, ""), new DataWrap(-49, ""),new DataWrap(21, ""), new DataWrap(30, "*"),new DataWrap(30, "")};System.out.println("排序之前：\n" + java.util.Arrays.toString(data));bubbleSort(data);System.out.println("排序之后：\n" + java.util.Arrays.toString(data));}
}

快速排序

算法的時間效率：時間效率很好，因為每趟能確定的元素都呈指數增長，故時間復雜度為log(n+1)

算法的空間效率：由于使用遞歸，而遞歸使用棧，因此空間效率最優時為log(n)

算法的穩定性：由于包含跳躍式交換，因此不穩定

public class QuickSort {private static void swap(DataWrap[] data, int i, int j) {DataWrap temp = data[i];data[i] = data[j];data[j] = temp;}private static void subSort(DataWrap[] data, int start, int end) {if (start < end) {DataWrap base = data[start];int i = start;int j = end + 1;while (true) {while (i < end && data[++i].compareTo(base) <= 0);while (j > start && data[--j].compareTo(base) >= 0);if (i < j) {swap(data, i, j);} else {break;}}swap(data, start, j);subSort(data, start, j - 1);subSort(data, j + 1, end);}}public static void quickSort(DataWrap[] data){subSort(data,0,data.length-1);}public static void main(String[] args) {DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),new DataWrap(21, "*"), new DataWrap(23, ""),new DataWrap(-30, ""), new DataWrap(-49, ""),new DataWrap(21, ""), new DataWrap(30, "*"),new DataWrap(30, "") };System.out.println("排序之前：\n" + java.util.Arrays.toString(data));quickSort(data);System.out.println("排序之后：\n" + java.util.Arrays.toString(data));}
}