為什么要排序？排序算法的性能提升之道
本文轉載自公眾號“讀芯術”(ID：AI_Discovery)。
排序有什么用?想象一下，如果字典不是按照字母順序排列，查找一個單詞，你得查到什么時候?這就是為什么人們引入了分類的概念，因為其極大地幫助我們快速搜索物品。
那么，如何實現排序呢?這些排序算法，你應該了解。
冒泡排序
這是最簡單的排序算法。只需比較每對相鄰的元素，并檢查元素是否有序，否則交換兩個元素，直到所有元素都被排序為止。
- 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²)。
- 最佳情況：O(n²)——即使數組已經排序了，算法也會檢查每個相鄰對，因此最佳情況下的時間復雜度將與最壞情況相同。
空間復雜度：O(1)。
由于只輸入了數組并未使用任何額外的數據結構，因此空間復雜度將為O(1)。
(2) 改進版冒泡排序：
如果看一下代碼，就會發現在上述排序算法中即使數組已經排序，時間復雜度也將相同，即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;
- }
- }
- }
(3) 性能分析：
時間復雜度：
- 最壞情況：O(n²)——與上述算法相同。
- 最佳情況：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;
- }
性能分析：
時間復雜度：
- 最壞情況：O(n²)——由于對于數組中的每個元素，遍歷其余數組以找到最小值，因此時間復雜度將變為O(n²)。
- 最佳情況：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--;
- }
- }
性能分析：
時間復雜度：
- 最壞情況：O(n²)——在最壞情況下，數組按降序排序。因此，必須遍歷每個元素并向左交換。
- 最佳情況：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;
- return left;
- }
性能分析：
時間復雜度：
- 最佳情況：O(nlogn)——首先將數組遞歸分為兩個子數組，時間復雜度為O(logn)。每次函數調用都將調用時間復雜度為O(n)的分區函數，因此，總時間復雜度為O(nlogn)。
- 最壞情況：O(n²)——當數組以降序排序或數組中的所有元素都相同時，由于子數組高度不平衡，因此時間復雜度躍升至O(n²)。
空間復雜度：O(n)。
由于遞歸調用quicksort函數，因此使用內部堆棧來存儲這些函數調用。堆棧中最多有n個調用，因此空間復雜度為O(n)。
合并排序
合并排序和快速排序一樣，都使用分而治之概念。在合并排序主要工作是合并子數組，而在快速排序中，主要工作是對數組進行分區/劃分，因此快速排序也稱為分區排序。
下面的函數會一直將數組遞歸地分成兩個子數組直到每個子數組只有一個元素。
- publicvoid merge(int arr[], int l, int m, int r) {
- int n1 = m-l+1;
- int n2 = r-m;
- int[] L =new int[n1];
- int[] R =new int[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++];
- }
將這些子數組存儲在兩個新數組中后，就根據它們的順序進行合并，并將它們存儲到輸入數組中。所有這些子數組合并后，輸入數組就排序完成了。
- publicvoid merge(int arr[], int l, int m, int r) {
- int n1 = m-l+1;
- int n2 = r-m;
- int[] L =new int[n1];
- int[] R =new int[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++];
- }
- }
性能分析：
時間復雜度：
- 最佳情況：O(nlogn)——首先將數組遞歸分為兩個子數組，時間復雜度為O(logn)。每次函數調用都將調用時間復雜度為O(n)的分區函數，因此，總時間復雜度為O(nlogn)。
- 最壞情況：O(nlogn)——最壞情況下的時間復雜度與最佳情況相同。
空間復雜度：O(n)
由于遞歸調用MergeSort函數，因此使用內部堆棧來存儲這些函數調用。堆棧中最多有n個調用，因此空間復雜度為O(n)。
圖源：unsplash
上面提到的算法是基于比較的排序算法，因為在對元素進行相互比較之后再對其進行排序。但是，還有其他基于非比較的排序算法，例如計數排序、基數排序、桶排序等，由于時間復雜度為O(n)，因此也稱為線性排序算法。
每種算法各自都有優缺點，采用哪種算法取決于優先級。如果效率上沒有問題，可以使用易實現的冒泡排序。或者在數組幾乎排好序時使用插入排序，因為此時插入排序的時間復雜度是線性的。
