rust 归并排序迭代

以你之姓@ 2022-10-05 09:45 197阅读 0赞

# Rust 归并排序 迭代 #

参考大佬们的写法写了一个rust版。

这个迭代（非递归）妙就妙在它创建啦一个栈来保存左右两个边界，类似模拟了递归的操作。实际上开销肯定是低于递归写法的。

fn merge(v: &mut Vec<i32>,left: usize,middle: usize,right: usize){ 
        let mut tmp = Vec::new();
        let mut l = left;
        let mut r = middle;
        while l<middle && r<right { 
            if v[l]<=v[r]{ 
                tmp.push(v[l]);
                l+=1;
            }else{ 
                tmp.push(v[r]);
                r+=1;
            }
        }
        while l<middle { 
            tmp.push(v[l]);
            l+=1;
        }
        while r<right { 
            tmp.push(v[r]);
            r+=1;
        }
        let mut index = 0;
        for i in left..right{ 
            v[i]=tmp[index];
            index+=1;
        }
    }
    
    fn merge_sort(v: &mut Vec<i32>){ 
        let length = v.len();
        let mut step = 2;
        let mut index;
        while step<=length { 
            index = 0;
            while index+step<=length { 
                merge(v,index,index+step/2,index+step);
                index+=step;
            }
            merge(v, index,index+step/2, length);//清理最后剩余的
            step*=2;
        }
        merge(v, 0, step/2, length);
    }
    
    fn main() { 
        let mut v = vec![3,42,6,1,42,653,23,3,3,3,3,3,3,5,2];
        merge_sort(&mut v);
        println!("{:?}",v);
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，197人围观）

还没有评论，来说两句吧...

相关阅读

相关归并排序的思想与实现（递归与迭代）

归并排序的思想核心思想：归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案”

怼烎@/ 2022年12月06日 15:55/ 0 赞/ 192 阅读

相关【大话数据结构C语言】69 归并排序（递归和迭代实现）

堆排序之所以效率比较高是利用了完全二叉树，但是堆排序的设计本身是比较复杂的那就引出一个问题，有没有更简单的使用完全二叉树来排序的算法呢？这就引出了归并排序算法

浅浅的花香味﹌/ 2022年10月15日 04:45/ 0 赞/ 226 阅读

相关 rust 归并排序迭代

Rust 归并排序迭代参考大佬们的写法写了一个rust版。这个迭代（非递归）妙就妙在它创建啦一个栈来保存左右两个边界，类似模拟了递归的操作。实际上开销肯定是低于递

以你之姓@/ 2022年10月05日 09:45/ 0 赞/ 198 阅读

相关插入排序和迭代归并排序以及复杂度分析

引言：算法是计算机科学中的基础，程序=算法+数据结构，算法描述了我们将如何来处理数据的过程。本文将介绍两种算法的实现以及其中一种算法的复杂度分析过程。 1. 算法介绍

港控/mmm°/ 2022年09月26日 02:43/ 0 赞/ 201 阅读

相关数据结构--迭代归并

归并最初的使用在与两个有序表的合并，从而引出对待排序数列的排序。两个有序表的合并在于合并之后，合并的表仍然有序。比如：有序表(1)：1 3 4 4 6 有序表(2)：

怼烎@/ 2022年07月30日 14:30/ 0 赞/ 224 阅读

相关 STL 源码分析——list 归并排序迭代版本

最近在看侯捷的 STL源码分析，发现了以下的这个list 排序算法，乍眼看去，实在难以看出它是归并排序。平常大家写归并排序，通常写的是递归版本。。为了效率的考虑，STL

野性酷女/ 2022年07月19日 01:28/ 0 赞/ 158 阅读

相关 C语言-数据结构-归并排序(merge sort)-递归迭代-源代码及分析

1. 归并排序归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有

布满荆棘的人生/ 2022年07月11日 12:24/ 0 赞/ 204 阅读

相关归并排序代码实现【递归实现+迭代实现】

1、归并排序--递归实现 2、归并排序--迭代实现 1、归并排序--递归实现 package aa; import java

野性酷女/ 2022年05月26日 12:58/ 0 赞/ 249 阅读

相关二路归并排序（迭代）——ANSI C实现

typedef int ElementType; / 将两个数组有序归并到一个数组中输入参数1：第一个

我就是我/ 2022年05月18日 03:13/ 0 赞/ 249 阅读

相关【数据结构】排序：归并排序（2路归并排序算法）详解，递归实现与迭代实现（C++）

\笔记整理内部排序分类目录： - [插入排序][Link 1] \- [交换排序][Link 2] \- [选择排序][Link 3] -[\->归并排序]

野性酷女/ 2021年12月05日 03:49/ 0 赞/ 413 阅读