您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

Rust排序算法:选择排序、冒泡排序、插入排序、归并排序

时间:2022-12-02 16:09:21  来源:  作者:麦花香里说丰年

 

选择排序

pub fn selection_sort<T:Ord>(arr:&mut [T]) {
    let len = arr.len();
    for left in 0..len {
        let mut smallest = left;
        for right in (left+1)..len {
            if arr[right] < arr[smallest] {
                smallest = right;
            }
        }
        arr.swap(smallest, left);
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn basic() {
        let mut res = vec!["f","d","e","a","c","b"];
        selection_sort(&mut res);
        assert_eq!(res, vec!["a","b","c","d","e","f"]);
    }
    #[test]
    fn empty() {
        let mut res = Vec::<u8>::new();
        selection_sort(&mut res);
        assert_eq!(res, vec![]);
    }

    #[test]
    fn one_element() {
        let mut res = vec!["a"];
        selection_sort(&mut res);
        assert_eq!(res, vec!["a"]);
    }

    #[test]
    fn pre_sorted() {
        let mut res = vec!["a","b","c","d"];
        selection_sort(&mut res);
        assert_eq!(res, vec!["a","b","c","d"]);
    }
}

冒泡排序


pub fn bubble_sort<T:Ord>(arr:&mut [T]) {
    if arr.is_empty() {
        return;
    }

    let mut sorted = false;
    let mut n = arr.len();
    while!sorted {
        sorted = true;
        for i in 0..n-1{
            if arr[i] > arr[i+1] {
                arr.swap(i,i+1);
                sorted = false;
            }
        }
        n -= 1;
    }

}

#[cfg(test)]
mod tests {
    use super::super::is_sorted;
    use super::*;

    #[test]
    fn descending() {
        let mut vec1 = vec![6,5,4,3,2,1];
        bubble_sort(&mut vec1);
        assert!(is_sorted(&vec1))
    }

    #[test]
    fn ascending() {
        let mut vec2 = vec![1,2,3,4,5];
        bubble_sort(&mut vec2);
        assert!(is_sorted(&vec2))
    }

    #[test]
    fn empty() {
        let mut vec3:Vec<usize> = vec![];
        bubble_sort(&mut vec3);
        assert!(is_sorted(&vec3))
    }
}

插入排序


pub fn insertion_sort<T>(arr:&mut [T])
where
    T: PartialOrd+Copy
{
    for i in 1..arr.len() {
        let cur = arr[i];
        let mut j = i - 1;

        while arr[j] > cur {
            arr[j+1] = arr[j];
            if j == 0 {
                break;
            }
            j -= 1;
        }

        // exit the loop from that break statement
        if j == 0 && arr[0] > cur {
            arr[0] = cur;
        }else {
            // `arr[j]>cur` is not satisfied ,exit from condition judgement
            arr[j+1] =cur;
        }
    }
}

#[cfg(test)]
mod tests {
    use super::super::is_sorted;
    use super::*;

    #[test]
    fn empty() {
        let mut arr:[u8;0] = [];
        insertion_sort(&mut arr);
        assert!(is_sorted(&arr));
    }

    #[test]
    fn one_element() {
        let mut arr:[char;1] = ['a'];
        insertion_sort(&mut arr);
        assert!(is_sorted(&arr));
    }

    #[test]
    fn already_sorted() {
        let mut arr:[&str;3] = ["a","b","c"];
        insertion_sort(&mut arr);
        assert!(is_sorted(&arr));
    }

    #[test]
    fn basic() {
        let mut arr:[&str;4] = ["d","a","c","b"];
        insertion_sort(&mut arr);
        assert!(is_sorted(&arr));
    }

    #[test]
    fn repeated_elements() {
        let mut arr: Vec<usize> = vec![542,542,542,542];
        insertion_sort(&mut arr);
        assert!(is_sorted(&arr));
    }
}

归并排序

fn merge<T:Ord+Copy>(arr:&mut [T],mid:usize) {
    // Create temporary vectors to support the merge
    let left_half = arr[..mid].to_vec();
    let right_half = arr[mid..].to_vec();

    let mut l:usize = 0;
    let mut r:usize = 0;

    for v in arr {
        if r == right_half.len() || (l < left_half.len() && left_half[l] < right_half[r]) {
            *v = left_half[l];
            l += 1;
        }else {
            *v = right_half[r];
            r += 1;
        }
    }

}

pub fn top_down_merge_sort<T: Ord+Copy>(arr:&mut [T]) {
    if arr.len() > 1 {
        let mid:usize = arr.len() / 2;
        // Sort the left half recursively
        top_down_merge_sort(&mut arr[..mid]);
        // Sort the right half recursively
        top_down_merge_sort(&mut arr[mid..]);
        // Combine the two halves
        merge(arr,mid)
    }
}

#[cfg(test)]
mod tests {

    #[cfg(test)]
    mod top_down_merge_sort {
        use super::super::*;

        #[test]
        fn basic() {
            let mut res = vec![10,3,8,2,7,6,1,4,5,9];
            top_down_merge_sort(&mut res);
            assert_eq!(res, vec![1,2,3,4,5,6,7,8,9,10])
        }

        #[test]
        fn basic_string() {
            let mut res = vec!["a","bb","d","cc"];
            top_down_merge_sort(&mut res);
            assert_eq!(res,vec!("a","bb","cc","d"))
        }

        #[test]
        fn empty() {
            let mut res = Vec::<u8>::new();
            top_down_merge_sort(&mut res);
            assert_eq!(res, vec![])
        }

        #[test]
        fn one_element() {
            let mut res = vec![1];
            top_down_merge_sort(&mut res);
            assert_eq!(res, vec![1])
        }

        #[test]
        fn pre_sorted() {
            let mut res = vec![1,2,3,4,5,6,7];
            top_down_merge_sort(&mut res);
            assert_eq!(res, vec![1,2,3,4,5,6,7])
        }
    }
}


Tags:算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
选择排序pub fn selection_sort<T:Ord>(arr:&mut [T]) { let len = arr.len(); for left in 0..len { let mut smallest = left; for right in (left+...【详细内容】
2022-12-02  Tags: 算法  点击:(0)  评论:(0)  加入收藏
本文主要内容如下: 前言最近生产环境遇到一个问题:现象:创建工单、订单等地方,全都创建数据失败。初步排查:报错信息为duplicate key,意思是保存数据的时候,报主键 id 重复,而这些...【详细内容】
2022-11-15  Tags: 算法  点击:(11)  评论:(0)  加入收藏
算法最开始是数学概念,我国古代称之为“术”,最早出现在《周髀算经》和《九章算术》中。而现代计算机中的算法的定义,则是在阿朗佐&middot;丘奇 和他的学生艾伦&middot;图灵的...【详细内容】
2022-11-09  Tags: 算法  点击:(19)  评论:(0)  加入收藏
对 TikTok 算法的工作原理感到好奇吗?什么是 TikTok 算法?TikTok 算法是一个复杂的系统,旨在为应用主页上的用户内容提供服务 - 为您提供页面 (FYP)。就像Instagram 的探索页面...【详细内容】
2022-11-03  Tags: 算法  点击:(43)  评论:(0)  加入收藏
去年写了一篇文章手写一个虚拟DOM库,彻底让你理解diff算法介绍虚拟DOM的patch过程和diff算法过程,当时使用的是双端diff算法,今年看到了Vue3使用的已经是快速diff算法,所以也想...【详细内容】
2022-10-30  Tags: 算法  点击:(17)  评论:(0)  加入收藏
前言CPU (Central Processing Unit)作为整个冯&middot;诺依曼架构的控制与运算中心,终其一生都在执行没有边界的指令,用无差别的计算支撑起智能时代“算力取之不尽用之不竭”的...【详细内容】
2022-10-28  Tags: 算法  点击:(23)  评论:(0)  加入收藏
什么是散列表散列表又被称为哈希表,包含一个键key、一个值value它们之间的对应关系是一对一,散列表就提供了键key和值value的对应关系,基本结构如下。 键值不会重复所以通过键...【详细内容】
2022-10-25  Tags: 算法  点击:(15)  评论:(0)  加入收藏
算法交易已经存在了一段时间,它不会消失。事实上,它只会越来越受欢迎。随着对快速交易的需求上升,算法交易的使用也在增长。在股票市场上使用算法,使交易者能够以更快的速度进...【详细内容】
2022-10-24  Tags: 算法  点击:(48)  评论:(0)  加入收藏
摘要深度学习在科学计算领域得到了广泛的应用,其算法被解决复杂问题的行业广泛使用。所有的深度学习算法都使用不同类型的神经网络来执行特定的任务。本文为大家带来基本的人...【详细内容】
2022-10-22  Tags: 算法  点击:(51)  评论:(0)  加入收藏
简介前面在密码学入门一文中讲解了各种常见的密码学概念、算法与运用场景,但没有介绍过代码,因此,为作补充,这一篇将会介绍使用Java语言如何实现使用这些算法,并介绍一下使用过程...【详细内容】
2022-10-22  Tags: 算法  点击:(17)  评论:(0)  加入收藏
▌简易百科推荐
选择排序pub fn selection_sort<T:Ord>(arr:&mut [T]) { let len = arr.len(); for left in 0..len { let mut smallest = left; for right in (left+...【详细内容】
2022-12-02  麦花香里说丰年    Tags:算法   点击:(0)  评论:(0)  加入收藏
B 树和 B+ 树是两种数据结构,构建了磁盘中的高速索引结构,因此不仅 MySQL 在用,MongoDB、Oracle 等也在用,基本属于数据库的标配常规操作。数据库要经常和磁盘与内存打交道,为了...【详细内容】
2022-11-25  java小悠  今日头条  Tags:B 树   点击:(14)  评论:(0)  加入收藏
本文主要内容如下: 前言最近生产环境遇到一个问题:现象:创建工单、订单等地方,全都创建数据失败。初步排查:报错信息为duplicate key,意思是保存数据的时候,报主键 id 重复,而这些...【详细内容】
2022-11-15  架构师之道  今日头条  Tags:雪花算法   点击:(11)  评论:(0)  加入收藏
算法最开始是数学概念,我国古代称之为“术”,最早出现在《周髀算经》和《九章算术》中。而现代计算机中的算法的定义,则是在阿朗佐&middot;丘奇 和他的学生艾伦&middot;图灵的...【详细内容】
2022-11-09  异步社区  今日头条  Tags:算法   点击:(19)  评论:(0)  加入收藏
去年写了一篇文章手写一个虚拟DOM库,彻底让你理解diff算法介绍虚拟DOM的patch过程和diff算法过程,当时使用的是双端diff算法,今年看到了Vue3使用的已经是快速diff算法,所以也想...【详细内容】
2022-10-30  街角小林  今日头条  Tags:算法   点击:(17)  评论:(0)  加入收藏
前言CPU (Central Processing Unit)作为整个冯&middot;诺依曼架构的控制与运算中心,终其一生都在执行没有边界的指令,用无差别的计算支撑起智能时代“算力取之不尽用之不竭”的...【详细内容】
2022-10-28  码洞  CSDN  Tags:算法   点击:(23)  评论:(0)  加入收藏
什么是散列表散列表又被称为哈希表,包含一个键key、一个值value它们之间的对应关系是一对一,散列表就提供了键key和值value的对应关系,基本结构如下。 键值不会重复所以通过键...【详细内容】
2022-10-25  Java面试365  今日头条  Tags:散列表   点击:(15)  评论:(0)  加入收藏
摘要深度学习在科学计算领域得到了广泛的应用,其算法被解决复杂问题的行业广泛使用。所有的深度学习算法都使用不同类型的神经网络来执行特定的任务。本文为大家带来基本的人...【详细内容】
2022-10-22  BigQuant  今日头条  Tags:算法   点击:(51)  评论:(0)  加入收藏
作者:小傅哥 博客:https://bugstack.cn沉淀、分享、成长,让自己和他人都能有所收获!一、前言:挂在树上!不知道你经历过HashMap的夺命连环问!为啥,面试官那么喜欢让你聊聊 HashMap?因...【详细内容】
2022-10-10  小傅哥    Tags:红黑树   点击:(33)  评论:(0)  加入收藏
前言在头条创作了一个月左右的时间,收获了50+粉丝,很是开心,我会把数据结构与算法的文章更新到底,第一次看我文章的同仁如果觉得不错的话就关注一下我哦,你的支持就是我创作的动...【详细内容】
2022-10-10  掂掂三生有幸  今日头条  Tags:数据结构   点击:(30)  评论:(0)  加入收藏
站内最新
站内热门
站内头条