当前位置:   article > 正文

Rust数据结构——排序算法(一)_rust 排序

rust 排序

Rust数据结构——排序算法(一)

0x01 常见的排序算法

排序算法是数据结构中很常见的算法。如果你了解过数据结构,那么对“常见的排序算法有哪些?”这个问题的回答都懒得答了。那么我还是来列举下吧。

  • 选择排序
  • 插入排序
  • 希尔排序
  • 冒泡排序
  • 快速排序
  • 基数排序
  • 堆排序
  • 归并排序等

排序算法实在是太多了,今天我们用Rust来实现几种比较简单的排序算法。

0x02 选择排序

选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。重复第二步,直到所有元素均排序完毕。

算法实现
fn select_sort(vec: &mut Vec<i32>) {
    for i in 0..vec.len() - 1 {
        let mut mix_index = i;
        for j in i + 1..vec.len() {
            if vec[mix_index] > vec[j] {
                mix_index = j;
            }
        }

        // 如果找到了比当前小的值
        // 交换
        if mix_index != i {
            let temp = vec[i];
            vec[i] = vec[mix_index];
            vec[mix_index] = temp;
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
0x03 插入排序

插入排序的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增 1 的有序表。插入排序的平均时间复杂度也是 O(n^2),空间复杂度为常数阶 O(1),具体时间复杂度和数组的有序性也是有关联的。

算法步骤

在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动。

算法实现
fn insert_sort(vec: &mut Vec<i32>) {
    for i in 0..vec.len() {
        let mut j = i;
        while j > 0 {
            if vec[j] < vec[j - 1] {
                // 交换值
                let temp = vec[j];
                vec[j] = vec[j - 1];
                vec[j - 1] = temp;
            }
            j -= 1;
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
0x04 希尔排序

希尔排序(Shell Sort)是插入排序的一种,它是针对直接插入排序算法的改进。希尔排序又称缩小增量排序,因 DL.Shell 于 1959 年提出而得名。它通过比较相距一定间隔的元素来进行,各趟比较所用的距离随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。希尔排序时间复杂度是 O(n^(1.3-2)),空间复杂度为常数阶 O(1)

算法步骤

希尔排序目的为了加快速度改进了插入排序,交换不相邻的元素对数组的局部进行排序,并最终用插入排序将局部有序的数组排序。在此我们选择增量 gap=length/2,缩小增量以 gap = gap/2 的方式,用序列 {n/2,(n/2)/2…1} 来表示。再实现代码的过程中,建议先写一遍插入排序,然后再为其划分gap

算法实现
pub fn shell_sort(vec: &mut Vec<i32>) {
    let mut gap = vec.len() / 2;
    while gap > 0 {
        // 插入排序
        for i in gap..vec.len() {
            let mut j = i;
            while j > 0 && j >= gap {
                // 交换
                if vec[j - gap] > vec[j] {
                    vec[j - gap] = vec[j - gap] ^ vec[j];
                    vec[j] = vec[j - gap] ^ vec[j];
                    vec[j - gap] = vec[j - gap] ^ vec[j];
                }
                j -= gap;
            }
        }
        gap /= 2;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
0x05 冒泡排序

冒泡排序也是一种简单直观的排序算法。它的时间复杂度:O(n^2) 空间复杂度:O(1)

算法步骤

它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

算法实现
fn bubble_sort(vec: &mut Vec<i32>) {
    for i in 0..vec.len() {
        for j in 0..vec.len() - 1 - i {
            // 交换
            if vec[j] > vec[j + 1] {
                vec[j] = vec[j] ^ vec[j + 1];
                vec[j + 1] = vec[j] ^ vec[j + 1];
                vec[j] = vec[j] ^ vec[j + 1];
            }
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
小结

这节课讲解了下一些简单的排序算法使用Rust来实现。其实跟其它语言也大同小异了。等有时间的时候,再把后面的算法也写一下~~

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/正经夜光杯/article/detail/750120
推荐阅读
相关标签
  

闽ICP备14008679号