冒泡排序|插入排序

• 2020 年 5 月 16 日
• 筆記
• 數據結構和算法

冒泡排序|插入排序

標籤（空格分隔）： 數據結構和算法

冒泡排序

冒泡排序只會操作相鄰的兩個數據。每次冒泡操作都會對相鄰的兩個元素進行比較，看是否滿足大小關係要求。如果不滿足就讓它倆互換。一次冒泡會讓至少一個元素移動到它應該在的位置，重複 n 次，就完成了 n 個數據的排序工作

$array = [1, 2, 10, 11, 90, 8, 4, 88, 100];
$count = count($array);
for ($i = 0; $i < $count; $i++) {
    // 提前退出冒泡循環的標誌位
    $flag = false;
    for ($j = $i; $j < $count; $j++) {
        if ($array[$j] > $array[$i]) {
            $tmp = $array[$i];
            $array[$i] = $array[$j];
            $array[$j] = $tmp;
            $flag = true;
        }
    }
    if (!$flag) break;
}

插入排序

首先，我們將數組中的數據分為兩個區間，**已排序區間**和**未排序區間**。初始已排序區間只有一個元素，就是數組的第一個元素。*插入算法的核心思想是取未排序區間中的元素，在已排序區間中找到合適的插入位置將其插入，並保證已排序區間數據一直有序*。重複這個過程，直到未排序區間中元素為空，算法結束

$array = [1, 2, 10, 11, 90, 8, 4, 88, 100];
$count = count($array);
for ($i = 1; $i < $count; $i++) {
    $tmp = $array[$i];
    for ($j = $i - 1; $j>-1; $j--) {
        if ($array[$j] > $tmp) {
            $array[$j+1] = $array[$j];
        } else {
            $array[$j+1] = $tmp;
            break;
        }
    }
}

對比