一、算法图示
二、算法思想
- 图示以
7 1 5 4 1 8 11
为例进行; - 开始设定第一个数
7
为有序数,因此从第二个数1
开始进行; - 第一轮开始:
1
向前找比它大的数,发现了7
,进行交换; - 第一轮结束后,前两个数已经是排序好的数;
- 第二轮开始:第3个数
5
向前找比它大的数,发现了7
,进行交换; - 第三轮开始:第四个数
4
向前找比它大的数,发现了7
,进行交换;继续向前找,与5
对比,还是比它大,继续交换;再向前之后就比它小了,结束; - 其它的以此类型,由于前面标红的部分是已经排序好的
有序数列
,因此一旦发现不满足大小关系就可以提前结束当前循环;
三、代码实现
pub fn insert_sort<T: PartialOrd>(src: &mut Vec<T>){
let length = src.len();
for i in 1..length {
for j in (1..=i).rev(){
if src[j] < src[j-1] {
src.swap(j, j-1);
}
else {
break;
}
}
}
}
#[cfg(test)]
mod tests{
……
#[test]
fn insert_sort_test(){
let mut num = vec![ 7, 1, 5, 4, 1, 8, 11];
select_sort(&mut num);
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » 【算法】插入排序
发表评论 取消回复