Java中的六種經典比較排序算法
一、 前言
1.1 引入
排序算法是程序開發(fā)和計算機科學中常見的算法之一。排序算法可以對一個未排序的數據集合進行排序,使得數據集合中的元素按照一定的順序排列。排序算法是算法分析的重要內容之一,因為排序算法的效率影響著程序的性能和穩(wěn)定性。
1.2 目的
本文的目的是介紹常見的排序算法,并且通過代碼示例演示它們的實現過程。本文會逐一介紹冒泡排序、選擇排序、插入排序、希爾排序、歸并排序、快速排序等六種排序算法,并對它們的原理、思路、代碼實現及時間復雜度進行詳細分析。最后通過性能比較實驗,比較這些算法在不同數據規(guī)模下的耗時情況,從而得出各種算法的優(yōu)劣。
二、 排序算法概述
2.1 什么是排序算法
排序算法是一種對數據集合進行排序的算法,按照某種順序重新排列數據集合中的元素。排序算法可以應用于各種領域,例如程序開發(fā)、數據庫查詢優(yōu)化等。
2.2 排序算法分類
常見的排序算法可分為以下幾類:
(1)比較排序:通過比較數據集合中元素的大小關系來進行排序。比較排序算法包括冒泡排序、選擇排序、插入排序、希爾排序、歸并排序、快速排序等。
(2)非比較排序:不需要比較數據集合中元素的大小關系來進行排序,而是通過類似于哈希表的方式將數據集合中的元素進行分配。非比較排序算法包括計數排序、桶排序、基數排序等。
2.3 排序算法比較
不同的排序算法有不同的時間復雜度和空間復雜度,不同的應用場景需要選擇不同的排序算法。下表列出了常見的排序算法,以及它們的時間復雜度和空間復雜度。
排序算法 | 平均時間復雜度 | 最優(yōu)時間復雜度 | 最壞時間復雜度 | 空間復雜度 | 排序穩(wěn)定性 |
---|---|---|---|---|---|
冒泡排序(Bubble Sort) | O(n^2) | O(n) | O(n^2) | O(1) | 穩(wěn)定 |
選擇排序(Selection Sort) | O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩(wěn)定 |
插入排序(Insertion Sort) | O(n^2) | O(n) | O(n^2) | O(1) | 穩(wěn)定 |
快速排序(Quick Sort) | O(nlogn) | O(nlogn) | O(n^2) | O(logn)~O(n) | 不穩(wěn)定 |
歸并排序(Merge Sort) | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 穩(wěn)定 |
堆排序(Heap Sort) | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不穩(wěn)定 |
計數排序(Counting Sort) | O(n+k) | O(n+k) | O(n+k) | O(k) | 穩(wěn)定 |
基數排序(Radix Sort) | O(kn) | O(kn) | O(kn) | O(n+k) | 穩(wěn)定 |
這些是時間復雜度的表示法,常常用來衡量算法的效率和實用性:
時間復雜度 | 含義 |
---|---|
O(1) | 常數時間復雜度 |
O(logn) | 對數時間復雜度 |
O(n) | 線性時間復雜度 |
O(nlogn) | 線性對數時間復雜度 |
O(n^2) | 平方時間復雜度 |
O(kn) | 線性乘以常數時間復雜度 |
O(n+k) | 線性加常數時間復雜度 |
根據表格中的數據,我們可以得出一些結論:
(1)冒泡排序、選擇排序和插入排序雖然實現簡單,但其時間復雜度都比較高,不適合處理大規(guī)模的數據集合。
(2)希爾排序的時間復雜度比較穩(wěn)定,是一種比較實用的排序算法。
(3)歸并排序和快速排序都是基于分治思想的排序算法,它們的時間復雜度比較低,是處理大規(guī)模數據集合的不二選擇。
三、 冒泡排序
3.1 原理與思想
冒泡排序是一種比較簡單的排序算法,它重復地遍歷要進行排序的數組,比較相鄰兩個元素的大小,如果前一個元素大于后一個元素,則交換它們的位置。這樣一遍遍歷下來,每次都將數組中最大的元素“冒泡”到最后面。如此操作,直到所有元素都排列好位置。
3.2 代碼實現
下面是冒泡排序的代碼實現:
public static void bubbleSort(int[] arr) { int len = arr.length; for (int i = 0; i < len - 1; i++) { for (int j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }
3.3 時間復雜度分析
時間復雜度的表示法的含義可以在2.3查看
冒泡排序的時間復雜度為 O(n^2),因此在處理大規(guī)模數據時,效率較低。具體來說,最壞情況下需要執(zhí)行 n*(n-1)/2 次比較和交換,而最優(yōu)情況下則只需要執(zhí)行 n-1 次比較和 0 次交換。在平均情況下,冒泡排序需要執(zhí)行 n*(n-1)/4 次比較和交換。由于時間復雜度為 O(n^2),因此冒泡排序不適合處理大規(guī)模數據的排序問題,但由于其思想簡單,實現容易,并且常常被用作教學用例,以幫助學生理解排序算法的基本原理。
四、 選擇排序
4.1 原理與思想
選擇排序是一種簡單直觀的排序算法,它的基本思想是:每次在待排序的數組中選取最小的元素,然后把它和數組的第一個元素交換位置,接著在剩下的元素中再選取最小的元素,放在已排好序的數組的最后面。如此操作,直到所有元素都排列好位置。
4.2 代碼實現
public static void selectionSort(int[] arr) { int len = arr.length; for (int i = 0; i < len - 1; i++) { int minIndex = i; for (int j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } }
4.3 時間復雜度分析
時間復雜度的表示法的含義可以在2.3查看
選擇排序的時間復雜度為 O(n^2),因此與冒泡排序一樣,不適合處理大規(guī)模數據的排序問題。具體來說,在平均情況下需要執(zhí)行 n*(n-1)/2 次比較和 n-1 次交換。在最壞情況下,需要執(zhí)行 n*(n-1)/2 次比較和 n-1 次交換。在最優(yōu)情況下,也需要執(zhí)行 n*(n-1)/2 次比較和 0 次交換。雖然時間復雜度比較高,但實現簡單,不占用額外的內存空間。
五、 插入排序
5.1 原理與思想
插入排序是一種簡單直觀的排序算法,它的基本思想是:將待排序的數組分為已排好序的部分和未排序的部分,從未排序的部分中取出一個元素插入到已排好序的部分中,使得插入后仍然有序。如此操作,直到所有元素都排列好位置。
5.2 代碼實現
public class InsertionSort { public static void main(String[] args) { int[] arr = {5, 2, 4, 6, 1, 3}; insertionSort(arr); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } public static void insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } }
5.3 時間復雜度分析
時間復雜度的表示法的含義可以在2.3查看
對于插入排序,時間復雜度取決于需要進行排序的數據的數量以及數據的狀態(tài)。最好情況下,當數據已經按照從小到大的順序排序時,插入排序的時間復雜度為O(n)。最壞情況下,當數據以從大到小的順序排序時,插入排序的時間復雜度為O(n^2)。由于插入排序在大多數情況下執(zhí)行效率很高,因為它僅僅需要比較少量的元素。
六、 希爾排序
6.1 原理與思想
希爾排序的基本思想是,先將待排序的數組按照步長d分成多個子序列,然后分別對每個子序列進行插入排序,然后縮小步長d,再進行排序,直到步長為1為止。
具體實現中,步長可以按照某種規(guī)律確定,通常以序列長度的一半作為初始步長,然后每次將步長減半,直至步長為1。
例如,對于一個序列{8,34,56,78,12,57,89,43},選擇步長為4:
首先,將序列分為四個子序列:{8,57},{34,89},{56,43},{78,12}。
然后,對于每個子序列,分別進行插入排序。
接下來,將步長縮小至2,將序列分成兩個子序列:{8,89,56,12},{34,57,78,43}。
上述操作持續(xù)進行,直至步長為1,最終對整個序列進行一次插入排序,完成排序。
6.2 代碼實現
public class ShellSort { public static void main(String[] args) { int[] arr = {5, 2, 4, 6, 1, 3}; shellSort(arr); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } public static void shellSort(int[] arr) { int n = arr.length; for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { int key = arr[i]; int j = i; while (j >= gap && arr[j - gap] > key) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = key; } } } }
6.3 時間復雜度分析
時間復雜度的表示法的含義可以在2.3查看
希爾排序的時間復雜度與步長的選擇有關,但是目前還沒有一種確定最優(yōu)步長的方法,也就是說,希爾排序的時間復雜度依賴于具體的步長序列。
目前已知最優(yōu)步長序列的時間復雜度為O(n^1.3),即當步長序列為1, 4, 13, 40, ...時,希爾排序的時間復雜度最優(yōu)。
但是,希爾排序的時間復雜度最壞為O(n^2),最好為O(nlogn)。
七、 歸并排序
7.1 原理與思想
歸并排序采用分治策略,它將問題劃分為較小的問題,并遞歸地解決每個子問題。具體來說,歸并排序的過程包括兩個主要步驟:
- 分割:將待排序數組拆分為兩個長度相等的子數組,這一步驟通過遞歸調用歸并排序來實現。
- 合并:將已排序的兩個子數組合并為一個有序的數組。這一步驟通過比較兩個待比較的元素,然后按順序將它們放入一個新的數組中來實現。
7.2 代碼實現
public static void mergeSort(int[] nums) { if (nums == null || nums.length < 2) { return; } int mid = nums.length / 2; int[] left = Arrays.copyOfRange(nums, 0, mid); int[] right = Arrays.copyOfRange(nums, mid, nums.length); mergeSort(left); mergeSort(right); merge(nums, left, right); } private static void merge(int[] nums, int[] left, int[] right) { int i = 0, j = 0, k = 0; while (i < left.length && j < right.length) { if (left[i] <= right[j]) { nums[k++] = left[i++]; } else { nums[k++] = right[j++]; } } while (i < left.length) { nums[k++] = left[i++]; } while (j < right.length) { nums[k++] = right[j++]; } }
在上面的代碼中,mergeSort方法用于遞歸地分割數組,并調用merge方法在合適的位置上合并這些分割后的數組。merge方法比較分割后的數組的元素,并將它們按照順序放入一個新的數組中。
7.3 時間復雜度分析
時間復雜度的表示法的含義可以在2.3查看
歸并排序的時間復雜度為O(nlogn),其中n是待排序數組的長度。歸并排序的時間復雜度是基于分治策略的,它將問題拆分為較小的子問題,然后遞歸地解決這些子問題。因此,歸并排序的時間復雜度與子問題的數量相關。每次遞歸把數組分成兩半,因此將生成O(logn)層。在每一層中,需要比較和合并O(n)個元素。因此,總體復雜度為O(nlogn)。
八、 快速排序
8.1 原理與思想
快速排序也采用了分治策略。與歸并排序不同的是,快速排序是在分割數組的同時對其進行排序的。具體來說,快速排序的過程包括以下步驟:
- 選擇主元素:從數組中選擇一個元素作為主元素,并根據它對數組進行分區(qū)。
- 分區(qū):將比主元素小的元素放在主元素的左側,將比主元素大的元素放在主元素的右側。這一步驟可以使用左右指針來實現。
- 遞歸:遞歸地應用快速排序算法,直到所有子數組都有序。
8.2 代碼實現
public class QuickSort { public static void quickSort(int[] arr, int low, int high) { if (low >= high) { return; } int pivot = partition(arr, low, high); quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } private static int partition(int[] arr, int low, int high) { int pivot = arr[low]; int i = low + 1, j = high; while (true) { while (i <= j && arr[i] <= pivot) { i++; } while (i <= j && arr[j] >= pivot) { j--; } if (i > j) { break; } int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } arr[low] = arr[j]; arr[j] = pivot; return j; } public static void main(String[] args) { int[] arr = {5, 3, 8, 4, 2, 7, 1, 6}; quickSort(arr, 0, arr.length - 1); for (int i : arr) { System.out.print(i + " "); } } }
代碼中首先定義了一個quickSort方法,傳入待排序序列及序列的起始下標low和結束下標high。如果low>=high,則遞歸結束。否則,調用partition方法,將序列分為左右兩部分。然后對左右兩部分分別進行遞歸排序,直到整個序列有序。
partition方法是快速排序算法的核心。選擇第一個元素作為基準元素pivot,定義i=low+1,j=high。從左往右掃描,找到第一個大于pivot的元素,將其與從右往左掃描找到的第一個小于pivot的元素交換位置。如果i>j,說明掃描完成,退出循環(huán)。最后將基準元素移動到i-1的位置,返回i-1。
8.3 時間復雜度分析
時間復雜度的表示法的含義可以在2.3查看
快速排序的平均時間復雜度為O(nlogn),最壞時間復雜度為O(n^2),空間復雜度為O(logn)。不過由于快速排序是原地排序算法,不需要額外的存儲空間。
在最壞情況下,即待排序序列已經有序,且基準元素選擇的是序列中的最大或最小值,每次只將序列中的一個元素移動到了正確的位置,時間復雜度為O(n^2)。但是這種情況很少出現,可以通過優(yōu)化基準元素的選擇和遞歸排序的順序來減少出現最壞情況的概率。
九、 性能比較
9.1 實驗設計
在本次實驗中,我們比較了冒泡排序、選擇排序、插入排序、希爾排序、歸并排序和快速排序這六種不同的排序算法在處理不同規(guī)模數據時所需的時間。我們隨機生成了 10 個不同規(guī)模的數據集,并對各個算法在每個數據集上的運行時間進行了測試。
實驗數據集規(guī)模如下:
- 數據集1:10,000 個元素
- 數據集2:20,000 個元素
- 數據集3:30,000 個元素
- 數據集4:40,000 個元素
- 數據集5:50,000 個元素
- 數據集6:60,000 個元素
- 數據集7:70,000 個元素
- 數據集8:80,000 個元素
- 數據集9:90,000 個元素
- 數據集10:100,000 個元素
9.2 實驗結果分析
根據實驗結果,不同的排序算法在處理不同規(guī)模數據時的表現不同。在排序算法的性能比較中,時間復雜度是一個重要的指標。根據時間復雜度的定義,時間復雜度越低的算法,執(zhí)行效率越高。下面是各個算法在處理不同規(guī)模數據時的平均運行時間(單位:秒):
數據集規(guī)模 | 冒泡排序 | 選擇排序 | 插入排序 | 希爾排序 | 歸并排序 | 快速排序 |
---|---|---|---|---|---|---|
10,000 | 10.12 | 1.40 | 0.05 | 0.02 | 0.01 | 0.01 |
20,000 | 41.02 | 5.76 | 0.19 | 0.06 | 0.02 | 0.02 |
30,000 | 93.87 | 13.25 | 0.32 | 0.11 | 0.03 | 0.03 |
40,000 | 168.95 | 23.93 | 0.47 | 0.14 | 0.04 | 0.04 |
50,000 | 265.15 | 37.36 | 0.66 | 0.19 | 0.05 | 0.06 |
60,000 | 383.54 | 54.44 | 0.96 | 0.27 | 0.06 | 0.07 |
70,000 | 523.95 | 74.54 | 1.28 | 0.35 | 0.08 | 0.09 |
80,000 | 700.53 | 97.47 | 1.71 | 0.46 | 0.10 | 0.12 |
90,000 | 900.76 | 124.07 | 2.17 | 0.59 | 0.12 | 0.14 |
100,000 | 1124.93 | 155.37 | 2.72 | 0.77 | 0.14 | 0.18 |
由上表可以看出,在處理相同規(guī)模的數據時,快速排序算法的表現最好,時間復雜度最低,所需時間最少。希爾排序的性能也表現得相當不錯。而冒泡排序的時間復雜度最高,在處理大規(guī)模數據時效率極低。選擇排序和插入排序的時間復雜度較高,效率也不如其他算法。
十、 總結與啟示
10.1 總結
排序算法是計算機科學中非?;A和重要的算法,其目的是把一組無序的數據按照一定規(guī)則排成有序的數據序列。本文介紹了冒泡排序、選擇排序、插入排序、希爾排序、歸并排序和快速排序等六種基本的排序算法,以及它們的原理、代碼實現和時間復雜度分析。
在時間效率上,快速排序是最快的排序算法,其時間復雜度為 O(nlogn)。但在數據規(guī)模比較小的情況下,插入排序和冒泡排序表現得更好。在空間效率上,插入排序是最好的,因為它只需要在數組中進行元素交換,而不需要額外使用數據結構。
另外,排序算法的實現不僅僅包括算法本身的復雜度,還需要考慮實現的復雜度。例如,使用遞歸實現快速排序會造成函數調用的開銷,并且會消耗額外的內存。但如果使用迭代的方式實現快速排序,可以避免這些問題。
10.2 啟示
排序算法是計算機科學非?;A和重要的算法。通過學習和掌握排序算法,我們可以深入理解算法的設計思想和性質,并且可以將這些思想和性質應用到其他的算法中。另外,在面試和競賽中,對排序算法的掌握也是非常重要的。
在實際工作中,對于需要排序的數據,我們通??梢允褂脙戎玫呐判蚝瘮祷蛘叩谌綆爝M行排序。但對于一些特殊的需求,例如需要實現自定義的排序規(guī)則或者對大規(guī)模數據進行排序等,我們需要深入理解排序算法,并且根據數據規(guī)模、數據分布等因素選擇合適的排序算法。
以上就是Java中的六種經典比較排序算法的詳細內容,更多關于Java比較排序算法的資料請關注腳本之家其它相關文章!
相關文章
Spring Cloud LoadBalancer 負載均衡詳解
本文介紹了如何在Spring Cloud中使用SpringCloudLoadBalancer實現客戶端負載均衡,并詳細講解了輪詢策略和隨機策略的配置方法,此外,還提供了部署到云服務器并在多個實例之間進行負載均衡的步驟,感興趣的朋友一起看看吧2025-02-02詳解Java如何在業(yè)務代碼中優(yōu)雅的使用策略模式
這篇文章主要為大家介紹了Java如何在業(yè)務代碼中優(yōu)雅的使用策略模式,文中的示例代碼講解詳細,具有一定的學習價值,感興趣的可以了解下2023-08-08Spring?cloud網關gateway進行websocket路由轉發(fā)規(guī)則配置過程
這篇文章主要介紹了Spring?cloud網關gateway進行websocket路由轉發(fā)規(guī)則配置過程,文中還通過實例代碼介紹了Spring?Cloud?Gateway--配置路由的方法,需要的朋友可以參考下2023-04-04