為什么要排序？排序算法的性能提升之道
本文轉(zhuǎn)載自公眾號“讀芯術(shù)”(ID：AI_Discovery)。
排序有什么用?想象一下，如果字典不是按照字母順序排列，查找一個單詞，你得查到什么時候?這就是為什么人們引入了分類的概念，因為其極大地幫助我們快速搜索物品。
那么，如何實現(xiàn)排序呢?這些排序算法，你應該了解。
冒泡排序
這是最簡單的排序算法。只需比較每對相鄰的元素，并檢查元素是否有序，否則交換兩個元素，直到所有元素都被排序為止。
- 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²)——由于循環(huán)n次元素n次，n為數(shù)組的長度，因此冒泡排序排序的時間復雜度變?yōu)镺(n²)。
- 最佳情況：O(n²)——即使數(shù)組已經(jīng)排序了，算法也會檢查每個相鄰對，因此最佳情況下的時間復雜度將與最壞情況相同。
空間復雜度：O(1)。
由于只輸入了數(shù)組并未使用任何額外的數(shù)據(jù)結(jié)構(gòu)，因此空間復雜度將為O(1)。
(2) 改進版冒泡排序：
如果看一下代碼，就會發(fā)現(xiàn)在上述排序算法中即使數(shù)組已經(jīng)排序，時間復雜度也將相同，即O(n²)。
為了克服這個問題，提出了一種改進算法。創(chuàng)建一個標志來確定數(shù)組是否已排序，該標志會檢查所有相鄰對之間是否發(fā)生了交換。如果遍歷整個數(shù)組時沒有交換，則該數(shù)組已完全排序，因此可以跳出循環(huá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)——由于在此算法中，如果數(shù)組已經(jīng)排序，就會中斷循環(huán)，因此最佳情況下的時間復雜度將變?yōu)镺(n)。
空間復雜度：O(1)。
選擇排序
假設排序算法中第一個元素是最小元素，然后檢查數(shù)組的其余部分中是否存在小于假定最小值的元素。若存在，就交換假定的最小值和實際的最小值，否則轉(zhuǎn)移到下一個元素。
- 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²)——由于對于數(shù)組中的每個元素，遍歷其余數(shù)組以找到最小值，因此時間復雜度將變?yōu)镺(n²)。
- 最佳情況：O(n²)——即使已對數(shù)組進行排序，我們的算法也會在其余數(shù)組中尋找最小值，因此最佳情況下的時間復雜度與最壞情況相同。
空間復雜度：O(1)。
就像之前的算法一樣，除了輸入數(shù)組之外沒有利用任何額外的數(shù)據(jù)結(jié)構(gòu)，因此空間復雜度將為O(1)。
插入排序
在這種排序算法中，對于每個元素，都要檢查其順序是否正確，直到當前元素為止。由于第一個元素是有序的，所以我們從第二個元素開始檢查順序是否正確否則交換元素。因此，在任何給定元素上，檢查當前元素是否大于上一個元素。如果不是，繼續(xù)交換元素，直到當前元素大于上一個元素為止。
- 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²)——在最壞情況下，數(shù)組按降序排序。因此，必須遍歷每個元素并向左交換。
- 最佳情況：O(n)——在最佳情況下，數(shù)組已經(jīng)排序。因此，對于每個元素，僅將當前元素與左側(cè)的元素進行比較。由于順序正確，不會交換并繼續(xù)進行下一個元素。因此，時間復雜度將為O(n)。
空間復雜度：O(1)。
由于除了輸入數(shù)組之外，沒有使用任何額外的數(shù)據(jù)結(jié)構(gòu)，因此空間復雜度將為O(1)。
快速排序
快速排序也被稱為分區(qū)排序。該排序算法因其分而治之的概念相較于之前的算法效率更高
首先確定一個主元，然后找到該主元位置的正確索引，將該數(shù)組分為兩個子數(shù)組。一個子數(shù)組包含小于主元的元素，另一個子數(shù)組包含大于主元的元素。然后，遞歸調(diào)用這兩個子數(shù)組，直到無法進一步劃分數(shù)組為止。
- 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);
- }
但是如何劃分子數(shù)組呢?
假設數(shù)組的最后一個元素是主元，則用兩個指針遍歷整個數(shù)組。左指針指向的元素應小于主元，右指針指向的元素應大于主元。如果不是，則在左右指針處交換元素以對應數(shù)組中的特定位置，左邊的元素較小，而右邊的元素較大。然后，將主元插入此位置。
- 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)——首先將數(shù)組遞歸分為兩個子數(shù)組，時間復雜度為O(logn)。每次函數(shù)調(diào)用都將調(diào)用時間復雜度為O(n)的分區(qū)函數(shù)，因此，總時間復雜度為O(nlogn)。
- 最壞情況：O(n²)——當數(shù)組以降序排序或數(shù)組中的所有元素都相同時，由于子數(shù)組高度不平衡，因此時間復雜度躍升至O(n²)。
空間復雜度：O(n)。
由于遞歸調(diào)用quicksort函數(shù)，因此使用內(nèi)部堆棧來存儲這些函數(shù)調(diào)用。堆棧中最多有n個調(diào)用，因此空間復雜度為O(n)。
合并排序
合并排序和快速排序一樣，都使用分而治之概念。在合并排序主要工作是合并子數(shù)組，而在快速排序中，主要工作是對數(shù)組進行分區(qū)/劃分，因此快速排序也稱為分區(qū)排序。
下面的函數(shù)會一直將數(shù)組遞歸地分成兩個子數(shù)組直到每個子數(shù)組只有一個元素。
- 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++];
- }
將這些子數(shù)組存儲在兩個新數(shù)組中后，就根據(jù)它們的順序進行合并，并將它們存儲到輸入數(shù)組中。所有這些子數(shù)組合并后，輸入數(shù)組就排序完成了。
- 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)——首先將數(shù)組遞歸分為兩個子數(shù)組，時間復雜度為O(logn)。每次函數(shù)調(diào)用都將調(diào)用時間復雜度為O(n)的分區(qū)函數(shù)，因此，總時間復雜度為O(nlogn)。
- 最壞情況：O(nlogn)——最壞情況下的時間復雜度與最佳情況相同。
空間復雜度：O(n)
由于遞歸調(diào)用MergeSort函數(shù)，因此使用內(nèi)部堆棧來存儲這些函數(shù)調(diào)用。堆棧中最多有n個調(diào)用，因此空間復雜度為O(n)。
圖源：unsplash
上面提到的算法是基于比較的排序算法，因為在對元素進行相互比較之后再對其進行排序。但是，還有其他基于非比較的排序算法，例如計數(shù)排序、基數(shù)排序、桶排序等，由于時間復雜度為O(n)，因此也稱為線性排序算法。
每種算法各自都有優(yōu)缺點，采用哪種算法取決于優(yōu)先級。如果效率上沒有問題，可以使用易實現(xiàn)的冒泡排序。或者在數(shù)組幾乎排好序時使用插入排序，因為此時插入排序的時間復雜度是線性的。
