Rust数据结构——排序算法(一)-卡咪卡咪哈-一个博客

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

0x01 常见的排序算法

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

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

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

0x02 选择排序

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

算法步骤

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

算法实现

fn select_sort(vec: &mutVec<i32>){foriin0..vec.len()–1{letmutmix_index=i;forjini+1..vec.len(){ifvec[mix_index]>vec[j]{mix_index=j;}}// 如果找到了比当前小的值 // 交换 ifmix_index!=i{lettemp=vec[i];vec[i]=vec[mix_index];vec[mix_index]=temp;}}}

0x03 插入排序

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

算法步骤

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

算法实现

fn insert_sort(vec: &mutVec<i32>){foriin0..vec.len(){letmutj=i;whilej>0{ifvec[j]<vec[j–1]{// 交换值 lettemp=vec[j];vec[j]=vec[j–1];vec[j–1]=temp;}j-=1;}}}

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。

算法实现

pubfn shell_sort(vec: &mutVec<i32>){letmutgap=vec.len()/2;whilegap>0{// 插入排序 foriingap..vec.len(){letmutj=i;whilej>0&&j>=gap{// 交换 ifvec[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;}}

0x05 冒泡排序

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

算法步骤

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

算法实现

fn bubble_sort(vec: &mutVec<i32>){foriin0..vec.len(){forjin0..vec.len()–1–i{// 交换 ifvec[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];}}}}