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