陣列輸入怎樣跳出

全文共4076字，預計學習時長11分鐘

圖源：unsplash

排序有什麼用？想象一下，如果字典不是按照字母順序排列，查詢一個單詞，你得查到什麼時候？這就是為什麼人們引入了分類的概念，因為其極大地幫助我們快速搜尋物品。

那麼，如何實現排序呢？這些排序演算法，你應該瞭解。

氣泡排序

這是最簡單的排序演算法。只需比較每對相鄰的元素，並檢查元素是否有序，否則交換兩個元素，直到所有元素都被排序為止。

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

int minIndex = i；

for（int j=i+1；j

if（arr［j］

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］

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）。

圖源：unsplash

上面提到的演算法是基於比較的排序演算法，因為在對元素進行相互比較之後再對其進行排序。但是，還有其他基於非比較的排序演算法，例如計數排序、基數排序、桶排序等，由於時間複雜度為O（n），因此也稱為線性排序演算法。

每種演算法各自都有優缺點，採用哪種演算法取決於優先順序。如果效率上沒有問題，可以使用易實現的氣泡排序。或者在陣列幾乎排好序時使用插入排序，因為此時插入排序的時間複雜度是線性的。

留言點贊關注

我們一起分享AI學習與發展的乾貨

如轉載，請後臺留言，遵守轉載規範