【算法】冒泡排序
- 一、算法图示
- 二、算法思想
- 三、代码实现
一、算法图示
二、算法思想
- 算法总体是从头至尾挨个对比，每个排序完成一个目标；
- 以序列
7 1 5 4 1 8 11为例说明； - 第一轮冒泡中，前两个数字对比，7比1大，因此互换；
- 接着7和5对比，7比5大，互换；
- 7接着和4对比，7比4大，互换；
- 7接着和1对比，7比1大，互换；
- 7接着和8对比，7比8小，不互换；
- 8和11对比，8比11小，不互换
- 第一轮完成后，11就排到了最后面；
- 第二轮冒泡中，5和4对比，5比4大，互换；
- 5又比1大，互换；
- 继续对比之后得到最后两个排序完成的序列；
- 其它的以此类推；
注意，如果一轮对比后没有发生交换，说明此时数列已经有序；
三、代码实现
pub fn bubble_sort<T: PartialOrd>(src:&mut Vec<T>){let length = src.len() - 1;for i in 0..length{let mut is_exchange = false;for j in 0..length-i{if src[j] > src[j + 1]{src.swap(j, j+1);is_exchange = true;}}if !is_exchange{break;}}
}#[cfg(test)]
mod tests{use super::*;#[test]fn bubble_sort_test(){let mut num = vec![ 7, 1, 5, 4, 1, 8, 11];bubble_sort(&mut num);assert_eq!(num, [1, 1, 4, 5, 7, 8, 11]);}
}
- 由于是当前项和后一项对比，因此序列长度取为
总长度 - 1； - 由于第
i次循环后最后的i个数字已经有序，因此内层循环的长度为总长度 - 1 - i； - 如果一次循环过后没有发生值改变，说明序列已经有序，直接调用
break退出；
测试结果
