全文共4076字，預計學習時長11分鐘
排序有什麼用？想像一下，如果字典不是按照字母順序排列，查找一個單詞，你得查到什麼時候？這就是為什麼人們引入了分類的概念，因為其極大地幫助我們快速搜索物品。
那麼，如何實現排序呢？這些排序算法，你應該了解。
冒泡排序
這是最簡單的排序算法。只需比較每對相鄰的元素，並檢查元素是否有序，否則交換兩個元素，直到所有元素都被排序為止。
for(int i =0;i < n; i++){
for(int j=0;j < n -1; j++){
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
性能分析：
· 時間複雜度：
1.最壞情況：O（n）——由於循環n次元素n次，n為數組的長度，因此冒泡排序排序的時間複雜度變為O（n）。
2.最佳情況：O（n）——即使數組已經排序了，算法也會檢查每個相鄰對，因此最佳情況下的時間複雜度將與最壞情況相同。
· 空間複雜度：O（1）。
由於只輸入了數組並未使用任何額外的數據結構，因此空間複雜度將為O（1）。
改進版冒泡排序：
如果看一下代碼，就會發現在上述排序算法中即使數組已經排序，時間複雜度也將相同，即O（n）。
為了克服這個問題，提出了一種改進算法。創建一個標誌來確定數組是否已排序，該標誌會檢查所有相鄰對之間是否發生了交換。如果遍歷整個數組時沒有交換，則該數組已完全排序，因此可以跳出循環。這大大降低了算法的時間複雜度。
for(int i =0;i < n; i++){
boolean isSwapped =false;
for(int j=0;j < n -1; j++){
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
isSwapped =true;
}
if(!isSwapped){
break;
}
}
}
性能分析：
· 時間複雜度：
1.最壞情況：O（n）——與上述算法相同。
2.最佳情況：O（n）——由於在此算法中，如果數組已經排序，就會中斷循環，因此最佳情況下的時間複雜度將變為O（n）。
· 空間複雜度：O（1）。
選擇排序
假設排序算法中第一個元素是最小元素，然後檢查數組的其餘部分中是否存在小於假定最小值的元素。若存在，就交換假定的最小值和實際的最小值，否則轉移到下一個元素。
for(int i=0;i<arr.length; i++) {
int minIndex = i;
for(int j=i+1;j<arr.length; j++) {
if(arr[j]<arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
性能分析：
· 時間複雜度：
1.最壞情況：O（n）——由於對於數組中的每個元素，遍歷其餘數組以找到最小值，因此時間複雜度將變為O（n）。
2.最佳情況：O（n）——即使已對數組進行排序，我們的算法也會在其餘數組中尋找最小值，因此最佳情況下的時間複雜度與最壞情況相同。
· 空間複雜度：O（1）。
就像之前的算法一樣，除了輸入數組之外沒有利用任何額外的數據結構，因此空間複雜度將為O（1）。
插入排序：
在這種排序算法中，對於每個元素，都要檢查其順序是否正確，直到當前元素為止。由於第一個元素是有序的，所以我們從第二個元素開始檢查順序是否正確否則交換元素。因此，在任何給定元素上，檢查當前元素是否大於上一個元素。如果不是，繼續交換元素，直到當前元素大於上一個元素為止。
for(int i =1;i < n; i++) {
int j = i;
while(j >0&& arr[j] < arr[j-1]) {
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
j--;
}
}
性能分析：
· 時間複雜度：
1.最壞情況：O（n）——在最壞情況下，數組按降序排序。因此，必須遍歷每個元素並向左交換。
2.最佳情況：O（n）——在最佳情況下，數組已經排序。因此，對於每個元素，僅將當前元素與左側的元素進行比較。由於順序正確，不會交換並繼續進行下一個元素。因此，時間複雜度將為O（n）。
· 空間複雜度：O（1）。
由於除了輸入數組之外，沒有使用任何額外的數據結構，因此空間複雜度將為O（1）。
快速排序
快速排序也被稱為分區排序。該排序算法因其分而治之的概念相較於之前的算法效率更高
首先確定一個主元，然後找到該主元位置的正確索引，將該數組分為兩個子數組。一個子數組包含小於主元的元素，另一個子數組包含大於主元的元素。然後，遞歸調用這兩個子數組，直到無法進一步劃分數組為止。
publicstaticvoid quicksort(int[] arr, int low, int high) {
if(low >= high) return;
int pivotPosition = partition(arr, low, high);
quicksort(arr,low, pivotPosition-1);
quicksort(arr, pivotPosition+1, high);
}
但是如何劃分子數組呢？
假設數組的最後一個元素是主元，則用兩個指針遍歷整個數組。左指針指向的元素應小於主元，右指針指向的元素應大於主元。如果不是，則在左右指針處交換元素以對應數組中的特定位置，左邊的元素較小，而右邊的元素較大。然後，將主元插入此位置。
publicstaticint partition(int[] arr, int low, int high) {
int pivot = arr[high];
int left = low, right = high-1;
while(left < right) {
while(arr[left]<pivot) {
left++;
}
while(arr[right]>pivot) {
right--;
}
if(left >= right) {
break;
}
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
int temp = arr[left];
arr[left] = arr[high];
arr[high] = temp;
returnleft;
}
性能分析：
· 時間複雜度：
1.最佳情況：O（nlogn）——首先將數組遞歸分為兩個子數組，時間複雜度為O（logn）。每次函數調用都將調用時間複雜度為O（n）的分區函數，因此，總時間複雜度為O（nlogn）。
2.最壞情況：O（n）——當數組以降序排序或數組中的所有元素都相同時，由於子數組高度不平衡，因此時間複雜度躍升至O（n）。
· 空間複雜度：O（n）。
由於遞歸調用quicksort函數，因此使用內部堆棧來存儲這些函數調用。堆棧中最多有n個調用，因此空間複雜度為O（n）。
合併排序
合併排序和快速排序一樣，都使用分而治之概念。在合併排序主要工作是合併子數組，而在快速排序中，主要工作是對數組進行分區/劃分，因此快速排序也稱為分區排序。
下面的函數會一直將數組遞歸地分成兩個子數組直到每個子數組只有一個元素。
publicvoid mergeSort(int arr[], int l, int r) {
if (l < r) {
intm = l + (r-l)/2;
sort(arr, l, m);
sort(arr , m+1, r);
merge(arr, l, m, r);
}
}
將這些子數組存儲在兩個新數組中後，就根據它們的順序進行合併，並將它們存儲到輸入數組中。所有這些子數組合併後，輸入數組就排序完成了。
publicvoid merge(int arr[], int l, int m, int r) {
int n1 = m-l+1;
int n2 = r-m;
int[] L =newint[n1];
int[] R =newint[n2];
for(int i =0;i < n1; i++) {
L[i] = arr[l+i];
}
for(int i =0;i < n2; i++) {
R[i] = arr[m+1+i];
}
int i =0, j =0, k =l;
while(i < n1 && j < n2) {
if(L[i] <=R[j]) {
arr[k++] =L[i++];
}
else {
arr[k++] =R[j++];
}
}
while(i < n1) {
arr[k++] =L[i++];
}
while(j < n2) {
arr[k++] =R[j++];
}
}
性能分析：
· 時間複雜度
1.最佳情況：O（nlogn）——首先將數組遞歸分為兩個子數組，時間複雜度為O（logn）。每次函數調用都將調用時間複雜度為O（n）的分區函數，因此，總時間複雜度為O（nlogn）。
2.最壞情況：O（nlogn）——最壞情況下的時間複雜度與最佳情況相同。
· 空間複雜度：O（n）
由於遞歸調用MergeSort函數，因此使用內部堆棧來存儲這些函數調用。堆棧中最多有n個調用，因此空間複雜度為O（n）。
上面提到的算法是基於比較的排序算法，因為在對元素進行相互比較之後再對其進行排序。但是，還有其他基於非比較的排序算法，例如計數排序、基數排序、桶排序等，由於時間複雜度為O（n），因此也稱為線性排序算法。
每種算法各自都有優缺點，採用哪種算法取決於優先級。如果效率上沒有問題，可以使用易實現的冒泡排序。或者在數組幾乎排好序時使用插入排序，因為此時插入排序的時間複雜度是線性的。
留言點讚關注
我們一起分享AI學習與發展的乾貨
如轉載，請後臺留言，遵守轉載規範