接下兩天會繼續講常見的排序演算法
選擇排序法是枚舉法的應用。原理是在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,再從剩餘未排序元素中繼續尋找最小(大)元素,放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。
優點在資料移動有關。當某個元素位於正確的最終位置上,他就不會移動。
演算流程:
第一次找到此樹列中最小值後與第一個元素交換。
第二次從第二個值找起,找到此數列最小值,但不包含第一個,再和第二個值交換。
第三次從第三個值找起,找到此數列最小值,但不包含第一二個,再和第三個值交換。
第四次從第四個值找起,找到此數列最小值,但不包含第一二三個,再和第四個值交換M
就完成此排序。
範例:
用選擇排序法將下面數列做排序:
fn main() {
let mut arr = [5, 4, 8, 7, 1];
let n = arr.len();
for i in 0..n {
let mut min = i;
for j in i + 1..n {
if arr[j] < arr[min] {
min = j;
}
}
if min != i{
let temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
println!("每次置換的數列: {:?}", arr);
}
println!("排序後的數列: {:?}", arr);
}
插入排序法是將陣列中的元素,逐一與排序好的資料做比較,前兩個元素先排好,再將第三個元素插入適當位置。當這三個元素排序好,接著再將第四個元素加入,重複此步驟,直到排序完成。
這邊就走一次演算流程:
步驟一4先跟第一個元素比較,放到5前面,步驟二8跟前面兩個元素比較因為比較大所以不動,步驟三7跟前面三個元素比較,因為比8小所以移動但比前面兩個大所以就沒再往前移動,最後步驟四1跟前面的元素比較,所以移到最前面即完成排序。
範例:
用插入排序法將下面數列做排序:
[5,4,8,7,1]
fn main() {
let mut arr = [5, 4, 8, 7, 1];
let n = arr.len();
for i in 1..n {
let mut j = i;
while j > 0 && arr[i] < arr[j -1] {
let temp = arr[i];
arr[j] = arr [j - 1];
arr[j - 1] = temp;
j -= 1;
}
println!("每次置換的數列:{:?}", arr);
}
println!("排序後的數列: {:?}", arr);
}
希爾排序法可以減少插入排序法中資料搬移的次數,插入排序法效率偏低,因為每次只能將數據移動一位。原理是將資料區分成特定間隔的幾個小區塊,以插入排序法排完區塊內的資料在減少間隔距離。
演算流程:
1.我們用gap sequence來排序,首先算出第一個gap為(8/2)=4
先排序(5,4),接下來(3,9)所以不動,再來排序(8,6),接著(7,2)
2.算出第二個gap為8/(2 * 2)=2
先排序(4,6)所以不動,接著(3,2),接著(6,5),再來是(3,9),(6,8)所以不動,接著(9,7)
3.算出第三次。gap為8/(2 * 2 * 2)=1,但前一次結果已經很接近排序完成,這邊就可以完成。
範例:
用希爾排序法將下面數列做排序:
[5, 3, 8, 7, 4, 9, 6, 2]
fn main() {
let mut arr = [5, 3, 8, 7, 4, 9, 6, 2];
let n = arr.len();
let mut gap = n / 2;
while gap > 0 {
for i in gap..n {
let mut j = i;
let current = arr[i];
while j >= gap && arr[j - gap] > current {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = current;
}
gap /= 2;
println!("每次置換的數列:{:?}", arr);
}
println!("最後排序的數列:{:?}", arr);
}
今天講解了三種排序法,圖片有點多,但多看幾次大概會懂,主要是希爾演算法比較複雜一點,先分區塊比較後再排序,對於資料處理各有各的處理。
目前應該不會太難吧🦣🦣!!
要是哪裡理解上還是邏輯上有錯請各位大大指正,感謝 🧙🧙🧙。