排序演算法是很常見的演算法,將一串不規則的數值資料依照遞增或遞減的方式重新編排。
排序簡單來說就是將一群資料按照某一個特定規則重新安排,使其具有遞增或遞減的次序關係。用以排序的依據,稱為鍵(key),它所含的就稱為「鍵值」。鍵值資料型態有數值型態、中文字串型態及非中文字串型態。
如果鍵值為數值型態,在比較時,則直接以數值大小做為鍵值大小比較依據,但如果鍵值為中文字串,依該中文字串由左到右逐字比較,並以中文內碼的編碼順序作為鍵值大小比較依據。假設鍵值為非中文字串,則和中文字串型態的比較方式類似,以該字串由左到右逐字比較,但卻以該字串ASCII碼的編碼順序作為鍵值大小比較依據。
在排序過程,資料的移動方式可分「直接移動」和「邏輯移動」。直接移動是直接交換儲存資料的位置,邏輯移動並不會移動資料儲存位置,僅改變指向這些資料的輔助指標的值。
兩者優劣在:直接移動會浪費許多時間進行資料的更動,而邏輯移動只要改變輔助指標指向的位置就能排序。就像是邏輯移動,而不是真正移動改變檔案中的位置。
氣泡排序也稱交換排序法,是最簡單的排序法之一,由於排序時每個元素會像泡泡般,一個一個浮出序列頂部,而得名。原理是由第一個元素開始,比較相鄰元素大小,如果大小順序有誤,則對調後再進行下一個元素的比較,如此掃過一次後就可確保最後一個元素是位於正確的順序。接著在第二次掃,直到完成所有元素的排序關係為止。
這邊就走一次演算流程:
🧀 由大到小排序
第一次疊代會先拿第一個元素5和第二個元素4比較,如果第二個小於第一個元素就會交換。接著拿5和8做比較,到第四次比較完後即可確定最大值在陣列最後面。
第二次疊代也是從頭開始,因為最後的元素已經是最大值,所以只要做三次就可以把剩下的元素最大值到剩餘陣列的最後面。
第三次疊代,完成三個值的排序。
第四次疊代,即可完成所有排序。
氣泡排序法需執行n-1次,每疊代要n-1-i次。
範例:
用氣泡排序法將下面數列做排序:
5,4,8,7,1
fn main() {
let mut arr = [5, 4, 8, 7, 1];
let n = arr.len();
for i in 0..n - 1 {
for j in 0..n - 1 - i {
if arr[j] > arr[j + 1] {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
println!("每次置換的數列:{:?}", arr);
}
}
}
println!("最後排序的數列:{:?}", arr);
}
結果是:
每次置換的數列:[4, 5, 8, 7, 1]
每次置換的數列:[4, 5, 7, 8, 1]
每次置換的數列:[4, 5, 7, 1, 8]
每次置換的數列:[4, 5, 1, 7, 8]
每次置換的數列:[4, 1, 5, 7, 8]
每次置換的數列:[1, 4, 5, 7, 8]
最後排序的數列:[1, 4, 5, 7, 8]
第一個就先用bubble開個場,接下來還會來用更多的排序法,也都是面試常見題目,除了觀念之外,也會了解是否知道處理資料的方法,多學多益啊。
目前應該不會太難吧🐑🐑!!
要是哪裡理解上還是邏輯上有錯請各位大大指正,感謝 🧙🧙🧙。