深入解析十大經典排序算法原理與實現

排序算法示例說明文檔

概述

本文檔詳細說明了排序算法示例的實現原理、性能特點和使用方法。

功能概要：提供各種排序算法的完整實現，包括基礎排序算法和高級排序算法，幫助理解算法原理和性能特點

排序算法分類

1. 基礎排序算法 (Basic Sorting Algorithms)

1.1 冒泡排序 (Bubble Sort)

算法思想：比較相鄰的兩個元素，如果第一個比第二個大，則交換它們
時間復雜度：O(n2)
空間復雜度：O(1)
穩定性：穩定
適用場景：小規模數據排序，教學演示

算法步驟：

比較相鄰的兩個元素，如果第一個比第二個大，則交換它們
對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對
重復以上步驟，直到沒有任何一對數字需要比較

優化點：

添加swapped標志，如果一輪比較中沒有發生交換，說明數組已經有序，可以提前退出

/*** 冒泡排序算法* * 算法思想：通過相鄰元素比較和交換，將最大的元素逐步"冒泡"到數組末尾* 具體邏輯：* 1. 外層循環控制排序輪數，每輪將當前范圍內最大的元素放到末尾* 2. 內層循環比較相鄰元素，如果前一個大于后一個則交換* 3. 使用swapped標志優化：如果一輪中沒有發生交換，說明數組已有序，可以提前退出* * 時間復雜度：O(n2) - 最壞情況下需要n-1輪，每輪比較n-i-1次* 空間復雜度：O(1) - 只使用常數個額外變量* 穩定性：穩定 - 相等元素不會改變相對位置* * @param arr 待排序的整數數組*/
public static void bubbleSort(int[] arr) {// 邊界條件檢查：空數組或長度為1的數組無需排序if (arr == null || arr.length <= 1) {return;}int n = arr.length;// 優化標志：如果一輪中沒有發生交換，說明數組已經有序boolean swapped;// 外層循環：控制排序輪數，每輪將當前范圍內最大的元素放到末尾for (int i = 0; i < n - 1; i++) {// 初始化交換標志為falseswapped = false;// 內層循環：比較相鄰元素，范圍是[0, n-1-i)// 每輪結束后，最后i個元素已經有序，無需再比較for (int j = 0; j < n - 1 - i; j++) {// 如果前一個元素大于后一個元素，則交換它們if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1);// 標記發生了交換swapped = true;}}// 優化：如果一輪中沒有發生交換，說明數組已經有序，可以提前退出if (!swapped) {break;}}
}

1.2 選擇排序 (Selection Sort)

算法思想：在未排序序列中找到最小元素，存放到排序序列的起始位置
時間復雜度：O(n2)
空間復雜度：O(1)
穩定性：不穩定
適用場景：小規模數據排序，交換次數少

算法步驟：

在未排序序列中找到最小元素，存放到排序序列的起始位置
再從剩余未排序元素中繼續尋找最小元素，然后放到已排序序列的末尾
重復第二步，直到所有元素均排序完畢

  /*** 選擇排序算法* * 算法思想：每次從未排序區間選擇最小的元素，放到已排序區間的末尾* 具體邏輯：* 1. 外層循環控制已排序區間的邊界，初始時已排序區間為空* 2. 內層循環在未排序區間中尋找最小元素的下標* 3. 將找到的最小元素與未排序區間的第一個元素交換，擴大已排序區間* 4. 重復上述過程，直到所有元素都進入已排序區間* * 時間復雜度：O(n2) - 需要n-1輪選擇，每輪在n-i個元素中找最小值* 空間復雜度：O(1) - 只使用常數個額外變量* 穩定性：不穩定 - 相等元素可能改變相對位置（如[3,3,1]排序后變成[1,3,3]）* * @param arr 待排序的整數數組*/public static void selectionSort(int[] arr) {// 邊界條件檢查：空數組或長度為1的數組無需排序if (arr == null || arr.length <= 1) {return;}int n = arr.length;// 外層循環：控制已排序區間的邊界，初始時已排序區間為空for (int i = 0; i < n - 1; i++) {// 假設當前位置i的元素是最小的int minIndex = i;// 內層循環：在未排序區間[i+1, n)中尋找真正的最小元素for (int j = i + 1; j < n; j++) {// 如果發現更小的元素，更新最小元素的下標if (arr[j] < arr[minIndex]) {minIndex = j;}}// 如果找到的最小元素不在位置i，則交換它們// 這樣就將最小元素放到了已排序區間的末尾if (minIndex != i) {swap(arr, i, minIndex);}}}

1.3 插入排序 (Insertion Sort)

算法思想：將第一個元素看做已排序序列，取出下一個元素，在已排序序列中從后向前掃描
時間復雜度：O(n2)
空間復雜度：O(1)
穩定性：穩定
適用場景：小規模數據排序，基本有序的數據

算法步驟：

將第一個元素看做已排序序列
取出下一個元素，在已排序序列中從后向前掃描
如果該元素大于新元素，將該元素移到下一位置
重復步驟3，直到找到已排序的元素小于或者等于新元素的位置
將新元素插入到該位置后
重復步驟2~5

  /*** 插入排序算法* * 算法思想：將數組分為已排序和未排序兩部分，逐個將未排序元素插入到已排序部分的正確位置* 具體邏輯：* 1. 初始時，第一個元素視為已排序，其余元素為未排序* 2. 從未排序區間取第一個元素，在已排序區間中尋找合適的插入位置* 3. 插入過程中，將大于該元素的已排序元素向后移動，為插入騰出空間* 4. 將元素插入到正確位置，擴大已排序區間* 5. 重復上述過程，直到所有元素都進入已排序區間* * 時間復雜度：O(n2) - 最壞情況下需要移動大量元素* 空間復雜度：O(1) - 只使用常數個額外變量* 穩定性：穩定 - 相等元素不會改變相對位置* 特點：對于接近有序的數組，插入排序效率很高，接近O(n)* * @param arr 待排序的整數數組*/public static void insertionSort(int[] arr) {// 邊界條件檢查：空數組或長度為1的數組無需排序if (arr == null || arr.length <= 1) {return;}int n = arr.length;// 從第二個元素開始，逐個將未排序元素插入到已排序部分for (int i = 1; i < n; i++) {// 保存當前要插入的元素int key = arr[i];// j指向已排序區間的最后一個元素int j = i - 1;// 在已排序區間中尋找key的插入位置// 將大于key的元素向后移動，為key騰出插入空間while (j >= 0 && arr[j] > key) {// 將大于key的元素向后移動一位arr[j + 1] = arr[j];// 繼續向前查找j--;}// 找到插入位置，將key插入到arr[j+1]位置// 此時arr[j] <= key，所以key應該放在arr[j+1]arr[j + 1] = key;}}

1.4 希爾排序 (Shell Sort)

算法思想：插入排序的改進版，通過設置不同的增量序列來提高效率
時間復雜度：O(n^1.3) 到 O(n2)
空間復雜度：O(1)
穩定性：不穩定
適用場景：中等規模數據排序

算法步驟：

選擇一個初始的增量序列（通常為n/2, n/4, n/8…）
按照增量序列對數組進行分組
對每組使用插入排序
逐步減小增量，重復步驟2-3
當增量為1時，完成排序

  /*** 希爾排序算法（改進的插入排序）* * 算法思想：通過設置不同的間隔序列，對數組進行分組插入排序，逐步減小間隔直到為1* 具體邏輯：* 1. 選擇一個初始間隔gap（通常為n/2），將數組分成gap個子序列* 2. 對每個子序列分別進行插入排序，但使用gap作為步長* 3. 減小間隔（通常為gap/2），重復上述過程* 4. 當間隔為1時，進行最后一次插入排序，此時數組已經基本有序* 5. 由于數組基本有序，最后的插入排序效率很高* * 時間復雜度：O(n^1.3) - 比插入排序快，但具體復雜度取決于間隔序列的選擇* 空間復雜度：O(1) - 只使用常數個額外變量* 穩定性：不穩定 - 相等元素可能改變相對位置* 特點：希爾排序是插入排序的改進版本，對于中等大小的數組效率較高* * @param arr 待排序的整數數組*/public static void shellSort(int[] arr) {// 邊界條件檢查：空數組或長度為1的數組無需排序if (arr == null || arr.length <= 1) {return;}int n = arr.length;// 外層循環：控制間隔序列，從n/2開始，逐步減小到1for (int gap = n / 2; gap > 0; gap /= 2) {// 對每個子序列進行插入排序// 從第gap個元素開始，因為前gap個元素分別作為各個子序列的第一個元素for (int i = gap; i < n; i++) {// 保存當前要插入的元素int key = arr[i];// j指向當前元素在子序列中的前一個位置int j = i;// 在子序列中尋找key的插入位置// 將大于key的元素向后移動gap個位置while (j >= gap && arr[j - gap] > key) {// 將大于key的元素向后移動gap個位置arr[j] = arr[j - gap];// 在子序列中向前查找j -= gap;}// 找到插入位置，將key插入到arr[j]位置arr[j] = key;}}}

2. 高級排序算法 (Advanced Sorting Algorithms)

2.1 快速排序 (Quick Sort)

算法思想：選擇一個基準元素，將小于基準的元素放在左邊，大于基準的元素放在右邊
時間復雜度：平均O(n log n)，最壞O(n2)
空間復雜度：O(log n)
穩定性：不穩定
適用場景：大規模數據排序，實際應用中最常用的排序算法

算法步驟：

選擇一個基準元素（pivot）
將小于基準的元素放在左邊，大于基準的元素放在右邊
對左右兩個子序列遞歸執行快速排序
當子序列長度為1或0時，排序完成

優化點：

選擇基準元素的方法（三數取中、隨機選擇等）
處理重復元素的優化
小數組使用插入排序

  /*** 快速排序算法* * 算法思想：使用分治策略，選擇一個基準元素（pivot），將數組分為兩部分，* 左邊部分都小于等于基準元素，右邊部分都大于基準元素，然后遞歸排序兩部分* * 具體邏輯：* 1. 選擇基準元素（這里選擇最后一個元素作為pivot）* 2. 通過partition方法將數組分為兩部分* 3. 遞歸對左半部分和右半部分進行快速排序* 4. 當子數組長度小于等于1時，遞歸結束* * 時間復雜度：平均O(n log n)，最壞O(n2)（當數組已經有序時）* 空間復雜度：O(log n) - 遞歸調用棧的深度* 穩定性：不穩定 - 相等元素可能改變相對位置* 特點：實際應用中效率很高，是很多編程語言內置排序算法的選擇* * @param arr 待排序的整數數組*/public static void quickSort(int[] arr) {// 邊界條件檢查：空數組或長度為1的數組無需排序if (arr == null || arr.length <= 1) {return;}// 調用遞歸版本的快速排序，初始范圍為整個數組quickSort(arr, 0, arr.length - 1);}/*** 快速排序的遞歸實現* * @param arr 待排序的數組* @param low 當前排序范圍的起始索引* @param high 當前排序范圍的結束索引*/private static void quickSort(int[] arr, int low, int high) {// 遞歸終止條件：當子數組長度小于等于1時if (low < high) {// 選擇基準元素并分區，返回基準元素的最終位置int pivotIndex = partition(arr, low, high);// 遞歸排序左半部分（小于基準元素的部分）quickSort(arr, low, pivotIndex - 1);// 遞歸排序右半部分（大于基準元素的部分）quickSort(arr, pivotIndex + 1, high);}}/*** 分區方法：將數組分為兩部分，左邊都小于等于pivot，右邊都大于pivot* * 具體邏輯：* 1. 選擇最后一個元素作為基準元素（pivot）* 2. 使用雙指針技術：i指向小于等于pivot的區域的最后一個位置* 3. 遍歷數組，將小于等于pivot的元素放到左邊區域* 4. 最后將pivot放到正確位置，返回pivot的索引* * @param arr 待分區的數組* @param low 分區范圍的起始索引* @param high 分區范圍的結束索引（pivot的位置）* @return 基準元素的最終位置*/private static int partition(int[] arr, int low, int high) {// 選擇最后一個元素作為基準元素int pivot = arr[high];// i指向小于等于pivot的區域的最后一個位置，初始為low-1int i = low - 1;// 遍歷數組，將小于等于pivot的元素放到左邊區域for (int j = low; j < high; j++) {// 如果當前元素小于等于pivotif (arr[j] <= pivot) {// 擴展左邊區域i++;// 將當前元素交換到左邊區域swap(arr, i, j);}}// 將pivot放到正確位置（左邊區域的后面）swap(arr, i + 1, high);// 返回pivot的最終位置return i + 1;}

2.2 歸并排序 (Merge Sort)

算法思想：將數組分成兩個相等的子數組，遞歸地對兩個子數組進行歸并排序，然后合并
時間復雜度：O(n log n)
空間復雜度：O(n)
穩定性：穩定
適用場景：大規模數據排序，需要穩定排序的場景

算法步驟：

將數組分成兩個相等的子數組
遞歸地對兩個子數組進行歸并排序
將兩個已排序的子數組合并成一個有序數組
當子數組長度為1時，開始合并

特點：

時間復雜度穩定，不受數據分布影響
需要額外的空間復雜度
適合外部排序

  /*** 歸并排序算法* * 算法思想：使用分治策略，將數組遞歸地分成兩半，分別排序后再合并* 具體邏輯：* 1. 將數組分成兩個大致相等的子數組* 2. 遞歸地對兩個子數組進行歸并排序* 3. 將兩個已排序的子數組合并成一個有序數組* 4. 當子數組長度為1時，遞歸結束* * 時間復雜度：O(n log n) - 穩定，不受數據分布影響* 空間復雜度：O(n) - 需要額外的臨時數組來存儲合并結果* 穩定性：穩定 - 相等元素不會改變相對位置* 特點：時間復雜度穩定，但需要額外空間，適合外部排序* * @param arr 待排序的整數數組*/public static void mergeSort(int[] arr) {// 邊界條件檢查：空數組或長度為1的數組無需排序if (arr == null || arr.length <= 1) {return;}int n = arr.length;// 創建臨時數組，用于存儲合并過程中的結果int[] temp = new int[n];// 調用遞歸版本的歸并排序，初始范圍為整個數組mergeSort(arr, 0, n - 1, temp);}/*** 歸并排序的遞歸實現* * @param arr 待排序的數組* @param left 當前排序范圍的左邊界* @param right 當前排序范圍的右邊界* @param temp 臨時數組，用于存儲合并結果*/private static void mergeSort(int[] arr, int left, int right, int[] temp) {// 遞歸終止條件：當子數組長度小于等于1時if (left < right) {// 計算中間位置，將數組分成兩半int mid = (left + right) / 2;// 遞歸排序左半部分mergeSort(arr, left, mid, temp);// 遞歸排序右半部分mergeSort(arr, mid + 1, right, temp);// 合并兩個已排序的子數組merge(arr, left, mid, right, temp);}}/*** 合并兩個已排序的子數組* * 具體邏輯：* 1. 使用三個指針：i指向左半部分，j指向右半部分，k指向臨時數組* 2. 比較兩個子數組的元素，將較小的放入臨時數組* 3. 當一個子數組遍歷完后，將另一個子數組的剩余元素全部放入臨時數組* 4. 最后將臨時數組的結果復制回原數組* * @param arr 原數組* @param left 左半部分的起始位置* @param mid 左半部分的結束位置* @param right 右半部分的結束位置* @param temp 臨時數組*/private static void merge(int[] arr, int left, int mid, int right, int[] temp) {// 初始化三個指針int i = left;      // 左半部分的指針int j = mid + 1;   // 右半部分的指針int k = left;      // 臨時數組的指針// 比較兩個子數組的元素，將較小的放入臨時數組while (i <= mid && j <= right) {if (arr[i] <= arr[j]) {// 左半部分元素較小或相等，優先選擇左半部分（保證穩定性）temp[k++] = arr[i++];} else {// 右半部分元素較小temp[k++] = arr[j++];}}// 將左半部分剩余的元素全部放入臨時數組while (i <= mid) {temp[k++] = arr[i++];}// 將右半部分剩余的元素全部放入臨時數組while (j <= right) {temp[k++] = arr[j++];}// 將臨時數組的結果復制回原數組for (int m = left; m <= right; m++) {arr[m] = temp[m];}}

2.3 堆排序 (Heap Sort)

算法思想：利用堆這種數據結構所設計的排序算法
時間復雜度：O(n log n)
空間復雜度：O(1)
穩定性：不穩定
適用場景：大規模數據排序，原地排序

算法步驟：

構建最大堆（或最小堆）
將堆頂元素（最大值）與末尾元素交換
調整堆結構，使其重新成為最大堆
重復步驟2-3，直到堆中只有一個元素

特點：

原地排序，不需要額外空間
時間復雜度穩定
適合找出前k個最大/最小元素

  /*** 堆排序算法* * 算法思想：利用堆這種數據結構進行排序，先將數組構建成最大堆，* 然后逐個取出堆頂元素（最大值），放到數組末尾，重復此過程直到堆為空* * 具體邏輯：* 1. 構建最大堆：從最后一個非葉子節點開始，自底向上調整每個節點* 2. 堆排序：重復執行以下操作直到堆為空*    a. 將堆頂元素（最大值）與堆的最后一個元素交換*    b. 堆的大小減1*    c. 對新的堆頂元素進行下沉操作，重新構建最大堆* 3. 最終得到升序排列的數組* * 時間復雜度：O(n log n) - 構建堆O(n)，每次調整O(log n)，共n-1次* 空間復雜度：O(1) - 原地排序，只使用常數個額外變量* 穩定性：不穩定 - 相等元素可能改變相對位置* 特點：原地排序，空間效率高，適合大數據量排序* * @param arr 待排序的整數數組*/public static void heapSort(int[] arr) {// 邊界條件檢查：空數組或長度為1的數組無需排序if (arr == null || arr.length <= 1) {return;}int n = arr.length;// 第一步：構建最大堆// 從最后一個非葉子節點開始，自底向上調整每個節點// 最后一個非葉子節點的索引是 n/2 - 1for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 第二步：逐個從堆中取出元素// 從數組末尾開始，每次將堆頂元素（最大值）放到當前位置for (int i = n - 1; i > 0; i--) {// 將堆頂元素（最大值）與堆的最后一個元素交換swap(arr, 0, i);// 對新的堆頂元素進行下沉操作，重新構建最大堆// 注意：此時堆的大小已經減1，所以傳入i而不是nheapify(arr, i, 0);}}/*** 堆化操作：將以節點i為根的子樹調整為最大堆* * 具體邏輯：* 1. 假設節點i是最大的，比較節點i與其左右子節點* 2. 如果左子節點或右子節點更大，則更新largest指針* 3. 如果largest不等于i，說明需要交換，然后遞歸調整被交換的子樹* 4. 這個過程稱為"下沉"操作，確保父節點總是大于等于其子節點* * @param arr 數組（表示堆）* @param n 堆的當前大小* @param i 要調整的節點索引*/private static void heapify(int[] arr, int n, int i) {// 假設當前節點i是最大的int largest = i;// 計算左子節點的索引int left = 2 * i + 1;// 計算右子節點的索引int right = 2 * i + 2;// 如果左子節點存在且大于當前節點，更新largest指針if (left < n && arr[left] > arr[largest]) {largest = left;}// 如果右子節點存在且大于當前最大值，更新largest指針if (right < n && arr[right] > arr[largest]) {largest = right;}// 如果largest不等于i，說明需要交換if (largest != i) {// 交換當前節點與最大子節點swap(arr, i, largest);// 遞歸調整被交換的子樹，確保整個子樹都滿足最大堆性質heapify(arr, n, largest);}}

性能對比

時間復雜度對比

算法	最好情況	平均情況	最壞情況
冒泡排序	O(n)	O(n2)	O(n2)
選擇排序	O(n2)	O(n2)	O(n2)
插入排序	O(n)	O(n2)	O(n2)
希爾排序	O(n log n)	O(n^1.3)	O(n2)
快速排序	O(n log n)	O(n log n)	O(n2)
歸并排序	O(n log n)	O(n log n)	O(n log n)
堆排序	O(n log n)	O(n log n)	O(n log n)

空間復雜度對比

算法	空間復雜度	是否原地排序
冒泡排序	O(1)	是
選擇排序	O(1)	是
插入排序	O(1)	是
希爾排序	O(1)	是
快速排序	O(log n)	是
歸并排序	O(n)	否
堆排序	O(1)	是

穩定性對比

算法	穩定性
冒泡排序	穩定
選擇排序	不穩定
插入排序	穩定
希爾排序	不穩定
快速排序	不穩定
歸并排序	穩定
堆排序	不穩定

使用方式

1. 直接調用靜態方法

int[] arr = {64, 34, 25, 12, 22, 11, 90};// 使用基礎排序算法
BasicSortingAlgorithms.bubbleSort(arr);
BasicSortingAlgorithms.selectionSort(arr);
BasicSortingAlgorithms.insertionSort(arr);
BasicSortingAlgorithms.shellSort(arr);// 使用高級排序算法
AdvancedSortingAlgorithms.quickSort(arr);
AdvancedSortingAlgorithms.mergeSort(arr);
AdvancedSortingAlgorithms.heapSort(arr);

2. 通過策略模式使用

SortContext context = new SortContext();// 設置不同的排序策略
context.setStrategy(new QuickSortStrategy());
int[] result1 = context.executeSort(testArray);context.setStrategy(new MergeSortStrategy());
int[] result2 = context.executeSort(testArray);

3. 運行示例程序

# 運行基礎排序算法演示
java org.example.interview.algorithm.sorting.BasicSortingAlgorithms# 運行高級排序算法演示
java org.example.interview.algorithm.sorting.AdvancedSortingAlgorithms# 運行策略模式演示
java org.example.interview.algorithm.sorting.StrategyPattern

算法選擇建議

小規模數據 (n < 50)

推薦：插入排序
原因：實現簡單，對于小數據效率較高

中等規模數據 (50 ≤ n < 1000)

推薦：希爾排序
原因：比插入排序效率高，實現相對簡單

大規模數據 (n ≥ 1000)

推薦：快速排序
原因：平均情況下效率最高，實際應用中最常用

特殊需求

需要穩定排序：歸并排序
原地排序：堆排序
外部排序：歸并排序

擴展建議

添加更多排序算法：
- 計數排序、基數排序、桶排序等線性時間排序算法
- 外部排序算法
- 并行排序算法
性能優化：
- 混合排序算法（如Timsort）
- 針對特定數據分布的優化
- 多線程并行排序
可視化展示：
- 排序過程的可視化
- 性能對比圖表
- 內存使用情況分析

注意事項

數據規模：選擇合適的算法需要考慮數據規模
數據特征：考慮數據的分布特征（是否基本有序、重復元素等）
穩定性要求：某些應用場景要求排序算法是穩定的
空間限制：在內存受限的環境下，優先選擇原地排序算法

公共代碼

工具方法

    /*** 交換數組中兩個元素的位置* * @param arr 目標數組* @param i 第一個元素的索引* @param j 第二個元素的索引*/private static void swap(int[] arr, int i, int j) {// 使用臨時變量保存第一個元素int temp = arr[i];// 將第二個元素放到第一個位置arr[i] = arr[j];// 將第一個元素放到第二個位置arr[j] = temp;}/*** 打印數組內容，用于調試和演示* * @param arr 要打印的數組* @param message 打印前的說明信息*/public static void printArray(int[] arr, String message) {// 輸出消息和數組開始符號System.out.print(message + ": [");// 遍歷數組的每個元素for (int i = 0; i < arr.length; i++) {// 輸出當前元素System.out.print(arr[i]);// 如果不是最后一個元素，添加分隔符if (i < arr.length - 1) {System.out.print(", ");}}// 輸出數組結束符號并換行System.out.println("]");}/*** 檢查數組是否已經排序（升序）* * @param arr 要檢查的數組* @return true表示數組已排序，false表示數組未排序*/public static boolean isSorted(int[] arr) {// 空數組或長度為1的數組認為是有序的if (arr == null || arr.length <= 1) {return true;}// 檢查每個元素是否大于等于前一個元素for (int i = 1; i < arr.length; i++) {// 如果發現逆序，返回falseif (arr[i] < arr[i - 1]) {return false;}}// 所有元素都滿足升序條件return true;}/*** 復制數組，創建數組的深拷貝* * @param arr 要復制的原數組* @return 新的數組副本，如果原數組為null則返回null*/public static int[] copyArray(int[] arr) {// 如果原數組為null，直接返回nullif (arr == null) {return null;}// 創建新數組，長度與原數組相同int[] copy = new int[arr.length];// 使用系統方法復制數組內容，效率最高System.arraycopy(arr, 0, copy, 0, arr.length);return copy;}/*** 生成指定大小的隨機數組，用于測試排序算法* * @param size 數組大小* @param max 隨機數的最大值（不包含）* @return 包含隨機整數的數組*/public static int[] generateRandomArray(int size, int max) {// 創建指定大小的數組int[] arr = new int[size];// 為每個位置生成隨機數for (int i = 0; i < size; i++) {// 生成[0, max)范圍內的隨機整數arr[i] = (int) (Math.random() * max);}return arr;}

性能測試

    /*** 測試所有排序算法的性能* * 測試流程：* 1. 分別測試基礎排序算法和高級排序算法* 2. 每個算法使用相同的測試數據，確保公平比較* 3. 記錄每個算法的執行時間* 4. 驗證排序結果的正確性* * @param arr 用于測試的原始數組*/public static void testAllAlgorithms(int[] arr) {// 輸出測試標題和基本信息System.out.println("\n=== 所有排序算法性能測試 ===");System.out.println("測試數組大小：" + arr.length);// 第一階段：測試基礎排序算法（時間復雜度O(n2)）testBasicAlgorithms(arr);// 第二階段：測試高級排序算法（時間復雜度O(n log n)）testAdvancedAlgorithms(arr);}/*** 測試基礎排序算法的性能* * 測試算法：* - 冒泡排序：O(n2)，穩定，適合小數據量* - 選擇排序：O(n2)，不穩定，交換次數少* - 插入排序：O(n2)，穩定，對接近有序的數組效率高* - 希爾排序：O(n^1.3)，不穩定，插入排序的改進版本* * @param arr 用于測試的原始數組*/private static void testBasicAlgorithms(int[] arr) {System.out.println("\n--- 基礎排序算法 ---");// 測試冒泡排序int[] arr1 = copyArray(arr);long startTime = System.currentTimeMillis();bubbleSort(arr1);long endTime = System.currentTimeMillis();System.out.println("冒泡排序：" + (endTime - startTime) + " 毫秒，結果：" + (isSorted(arr1) ? "成功" : "失敗"));// 測試選擇排序int[] arr2 = copyArray(arr);startTime = System.currentTimeMillis();selectionSort(arr2);endTime = System.currentTimeMillis();System.out.println("選擇排序：" + (endTime - startTime) + " 毫秒，結果：" + (isSorted(arr2) ? "成功" : "失敗"));// 測試插入排序int[] arr3 = copyArray(arr);startTime = System.currentTimeMillis();insertionSort(arr3);endTime = System.currentTimeMillis();System.out.println("插入排序：" + (endTime - startTime) + " 毫秒，結果：" + (isSorted(arr3) ? "成功" : "失敗"));// 測試希爾排序int[] arr4 = copyArray(arr);startTime = System.currentTimeMillis();shellSort(arr4);endTime = System.currentTimeMillis();System.out.println("希爾排序：" + (endTime - startTime) + " 毫秒，結果：" + (isSorted(arr4) ? "成功" : "失敗"));}/*** 測試高級排序算法的性能* * 測試算法：* - 快速排序：平均O(n log n)，不穩定，實際應用中效率最高* - 歸并排序：O(n log n)，穩定，時間復雜度穩定但需要額外空間* - 堆排序：O(n log n)，不穩定，原地排序空間效率高* * 預期結果：這些算法在大數據量時應該比基礎排序算法快很多* * @param arr 用于測試的原始數組*/private static void testAdvancedAlgorithms(int[] arr) {System.out.println("\n--- 高級排序算法 ---");// 測試快速排序int[] arr1 = copyArray(arr);long startTime = System.currentTimeMillis();quickSort(arr1);long endTime = System.currentTimeMillis();System.out.println("快速排序：" + (endTime - startTime) + " 毫秒，結果：" + (isSorted(arr1) ? "成功" : "失敗"));// 測試歸并排序int[] arr2 = copyArray(arr);startTime = System.currentTimeMillis();mergeSort(arr2);endTime = System.currentTimeMillis();System.out.println("歸并排序：" + (endTime - startTime) + " 毫秒，結果：" + (isSorted(arr2) ? "成功" : "失敗"));// 測試堆排序int[] arr3 = copyArray(arr);startTime = System.currentTimeMillis();heapSort(arr3);endTime = System.currentTimeMillis();System.out.println("堆排序：" + (endTime - startTime) + " 毫秒，結果：" + (isSorted(arr3) ? "成功" : "失敗"));}

主方法

    /*** 主方法：演示所有排序算法的功能和性能* * 演示內容：* 1. 小規模數據排序：展示各種算法的排序過程和結果* 2. 大規模數據性能測試：比較不同算法的執行效率* 3. 驗證排序結果的正確性* * @param args 命令行參數（未使用）*/public static void main(String[] args) {// 打印演示標題InterviewUtils.printTitle("所有排序算法演示");// 第一階段：小規模數據排序演示// 使用固定的測試數據，便于觀察排序過程int[] smallArray = {64, 34, 25, 12, 22, 11, 90, 88, 76, 54};System.out.println("小規模測試數據：");printArray(smallArray, "原始數組");// 依次測試各種排序算法，展示排序結果System.out.println("\n=== 小規模數據排序測試 ===");// 測試冒泡排序int[] arr1 = copyArray(smallArray);bubbleSort(arr1);printArray(arr1, "冒泡排序后");// 測試選擇排序int[] arr2 = copyArray(smallArray);selectionSort(arr2);printArray(arr2, "選擇排序后");// 測試插入排序int[] arr3 = copyArray(smallArray);insertionSort(arr3);printArray(arr3, "插入排序后");// 測試希爾排序int[] arr4 = copyArray(smallArray);shellSort(arr4);printArray(arr4, "希爾排序后");// 測試快速排序int[] arr5 = copyArray(smallArray);quickSort(arr5);printArray(arr5, "快速排序后");// 測試歸并排序int[] arr6 = copyArray(smallArray);mergeSort(arr6);printArray(arr6, "歸并排序后");// 測試堆排序int[] arr7 = copyArray(smallArray);heapSort(arr7);printArray(arr7, "堆排序后");// 第二階段：大規模數據性能測試// 生成5000個隨機數進行性能對比System.out.println("\n=== 大規模數據性能測試 ===");int[] largeArray = generateRandomArray(5000, 100000);testAllAlgorithms(largeArray);// 打印分隔線和完成信息InterviewUtils.printSeparator(50);System.out.println("所有排序算法演示完成！");}