Rust实现八种排序算法

3,956 阅读8分钟

排序是非常基础的算法问题之一,本文将使用Rust编程语言实现八种排序算法,通过实现排序算法来学习Rust。在本文中,我们限定对n个数字进行从小到大的排序。

冒泡排序

冒泡排序每次从头到尾比较每个相邻的数字,如果前面的数字小于后面数字,那么交换它们的位置。第i次遍历后,第i大的元素必然被交换到了正确的位置上,因此总共需要n-1次遍历,算法复杂度为O(n^2)

算法实现如下

fn bubble_sort(nums: &mut Vec<usize>) {
    for _i in 1..nums.len() {
        for i in 1..nums.len() {
            if nums[i-1] > nums[i] {
                nums.swap(i-1, i);
            }
        }
    }
}

插入排序

插入排序将数组视为两部分,已经排好序的前部和未排序的后部,每次取出后部第一个数字,找到在前部合适的插入位置,然后将插入位置后的数字全部后移。算法需要将n-1个元素插入到以及排好序的前部(从只有一个元素开始),最坏情况下需要移动前部全部的数字,因此最坏时间复杂度依然是O(n^2)

算法实现如下

fn insert_sort(nums: &mut Vec<usize>) {
    for i in 1..nums.len() {
        let (mut p, v) = (i, nums[i]);
        while p > 0 && nums[p-1] > v {
            nums[p] = nums[p-1];
            p -= 1;
        }
        nums[p] = v;
    }
}

希尔排序

希尔排序[2]每一轮使用插入排序对每个步长为g的子序列进行排序。

假设有t轮排序,显然最后一轮的g必须为1,也就是g_t=1,步长的最佳取值为g_{t-1}=3g_t+1,这种取值的算法复杂为O(n^{3/2})

算法实现如下

fn shell_sort(nums: &mut Vec<usize>) {

    fn _insert_sort(nums: &mut Vec<usize>, g: usize) {
        for i in g..nums.len() {
            let (mut p, v) = (i, nums[i]);
            while p >= g && nums[p-g] > v {
                nums[p] = nums[p-g];
                p -= g;
            }
            nums[p] = v;
        }
    }

    let mut a: VecDeque<usize> = VecDeque::new();
    a.push_front(1);
    while *a.front().unwrap() <= nums.len() {
        a.push_front(3*a.front().unwrap()+1);
    }
    for &g in a.iter() {
        _insert_sort(nums, g);
    }
}

选择排序

选择排序同样将数组视为两部分,排好序的前部和未排序的后部,和插入排序不一样的地方在于,每次将后部的最小元素加入到前部的末尾。算法需要找出n-1次最小数字,每次寻找最小数字的时候需要遍历后部元素,因此最坏时间内复杂度依然是O(n^2)

算法实现如下

fn selection_sort(nums: &mut Vec<usize>) {
    for i in 0..nums.len()-1 {
        let mut p = i;
        for j in i+1..nums.len() {
            if nums[j] < nums[p] {
                p = j;
            }
        }
        nums.swap(i, p);
    }
}

计数排序

计数排序[1]是本文中唯一的非比较排序,因此可以突破比较排序的算法复杂度理论下界(也就是O(nlog(n)))。对于计数排序,我们要求所有数字的取值是有限的,例如是来组[0,k)的整数。算法可以分为三个步骤

  • 计数:首先将各个取值的数量记录到计数数组C中。

  • 计算区间:通过累加小于等于取值的数字数量,可以计算出每个取值在排好序的数组中的分布范围,将结果保存回数组C。例如,取值i在排好序的数组中的分布应该是[C_{i-1},C_i),0所在范围为[0,C_0)

  • 填入结果:最后遍历数组,通过数组C可以直接得到数字所在区间的最后一个位置,如果数字为i,那么摆放位置应该是C_i-1,然后将C_i减去一,以便下次使用。

算法需要遍历原数组以及计数数组,因此算法复杂度为O(n+k)。算法实现如下

fn count_sort(nums: &mut Vec<usize>) {
    let n = nums.iter().max().unwrap();
    let origin_nums = nums.clone();
    let mut count: Vec<usize> = Vec::new();
    for _i in 0..n+1 {
        count.push(0)
    }
    for &v in nums.iter() {
        count[v] += 1;
    }
    for i in 1..count.len() {
        count[i] += count[i-1];
    }
    for &v in origin_nums.iter() {
        nums[count[v]-1] = v;
        count[v] -= 1;
    }
}

快速排序

快速排序每次选个一个数字,然后将数组分割成两部分,一部分都是小于该数字的数字,另一部分都是大于该数字的数字。然后,再次在划分好的数组片段上继续做划分。在最好情况下,每次数组被均匀地分割成大小相同的两个片段,此时的算法复杂度为O(nlog(n))

算法实现如下

fn quick_sort(nums: &mut Vec<usize>) {

    fn _partition(nums: &mut Vec<usize>, begin: usize, end: usize) -> usize {
        let (mut i, v) = (begin, nums[end-1]);
        for j in begin..end-1 {
            if nums[j] <= v {
                nums.swap(i, j);
                i += 1;
            }
        }
        nums.swap(i, end-1);
        i
    }

    fn _quick_sort(nums: &mut Vec<usize>, begin: usize, end: usize) {
        if begin+1 < end {
            let mid = _partition(nums, begin, end);
            _quick_sort(nums, begin, mid);
            _quick_sort(nums, mid+1, end);
        }
    }

    _quick_sort(nums, 0, nums.len())
}

归并排序

归并排序通过不断归并排好序的数组片断得到完整的排序数组。只有一个数字的数组显然算是排好序的,归并排序自底向上将数组片断两两归并得到最终的排序数组。这是一个二分然后递归的过程,因此算法复杂度为O(nlog(n))

算法实现如下

fn merge_sort(nums: &mut Vec<usize>) {

    fn _merge(nums: &mut Vec<usize>, left: usize, mid: usize, right: usize) {
        let left_part: Vec<usize> = nums[left..mid].iter().cloned().collect();
        let right_part: Vec<usize> = nums[mid..right].iter().cloned().collect();
        let (mut left_offset, mut right_offset) = (0usize, 0usize);
        while left_offset < left_part.len() || right_offset < right_part.len() {
            if right_offset == right_part.len() 
            || (left_offset < left_part.len() && left_part[left_offset] <= right_part[right_offset]) {
                nums[left + left_offset + right_offset] = left_part[left_offset];
                left_offset += 1;
            } else {
                nums[left + left_offset + right_offset] = right_part[right_offset];
                right_offset += 1;
            }
        }
    }

    fn _merge_sort(nums: &mut Vec<usize>, left: usize, right: usize) {
        if left+1 < right {
            let mid = (left + right) / 2;
            _merge_sort(nums, left, mid);
            _merge_sort(nums, mid, right);
            _merge(nums, left, mid, right);
        }
    }

    _merge_sort(nums, 0, nums.len())
}

堆排序

堆排序使用最大(或最小)堆上的操作进行排序。堆是一棵完全二叉树,因此可以直接保存在一个数组里,通过计算可以得到某个节点的父节点、左子节点、右子节点的下标,如下图所示(图中下标从1开始,实现中从0开始)。

这个完全二叉树需要满足一个性质:父节点包含的数字必须大于等于它的子节点,对于其中的节点有两种操作:

  • 上升:当节点元素变大后需要进行上升操作。当元素大于父节点元素时,将当前节点元素和父节点元素进行交换,然后尝试继续上升父节点元素,直到当前节点元素小于父节点元素或者到达树根。
  • 下沉:当节点元素变小后需要进行下沉操作。如果当前节点的元素小于子节点元素,那么将当前节点元素和子节点元素进行交换,然后尝试继续下沉子节点,当达到叶节点或者没有元素更小的子节点为止。

在这两个操作的基础上,我们可以定义堆的接口

  • 弹出最大元素:按照最大堆的性质,最大元素位于树根,因此将树根元素和末尾元素交换,弹出末尾元素,然后对树根进行下沉操作;
  • 加入新的元素:将新元素加到末尾,然后继续上升操作;
  • 从向量创建堆:自底向上对每个非叶节点进行下沉操作。
struct Heap<T: Ord> {
    elems: Vec<T>   // 保存完全二叉树
}

impl<T: Ord> Heap<T> {

    fn new() -> Heap<T> {
        Heap { elems: Vec::new() }
    }

    // 从向量创建一个最大堆
    fn from(elems: Vec<T>) -> Heap<T> {
        let mut heap = Heap { elems: elems };
        // 自底向上遍历非叶节点
        for i in (0..heap.len()/2).rev() {
            // 下沉节点i
            heap.max_heapify(i)
        }
        heap
    }

    // 计算父节点下标
    fn parent(i: usize) -> usize {
        if i > 0 { (i-1)/2 } else { 0 }
    }

    // 计算左子节点下标
    fn left(i: usize) -> usize {
        i*2+1
    }

    // 计算右子节点下标
    fn right(i: usize) -> usize {
        i*2+2
    }

    // 对节点i进行下沉操作
    fn max_heapify(&mut self, i: usize) {
        let (left, right, mut largest) = (Heap::<T>::left(i), Heap::<T>::right(i), i);
        if left < self.len() && self.elems[left] > self.elems[largest] {
            largest = left;
        }
        if right < self.len() && self.elems[right] > self.elems[largest] {
            largest = right;
        }
        if largest != i {
            self.elems.swap(largest, i);
            self.max_heapify(largest);
        }
    }

    // 插入一个元素
    fn push(&mut self, v: T) {
        self.elems.push(v);
        // 上升元素
        let mut i = self.elems.len()-1;
        while i > 0 && self.elems[Heap::<T>::parent(i)] < self.elems[i] {
            self.elems.swap(i, Heap::<T>::parent(i));
            i = Heap::<T>::parent(i);
        }
    }

    // 弹出最大元素
    fn pop(&mut self) -> Option<T> {
        if self.is_empty() {
            None
        } else {
            let b = self.elems.len()-1;
            self.elems.swap(0, b);
            let v = Some(self.elems.pop().unwrap());
            if !self.is_empty() {
                // 下沉根节点
                self.max_heapify(0);
            }
            v
        }
    }

    fn is_empty(&self) -> bool {
        self.elems.is_empty()
    }

    fn len(&self) -> usize {
        self.elems.len()
    }
}

编写好了最大堆后,可以采用建立堆,然后不断取出最大元素的方式完成排序。其中,建立堆的方法既可以采用一次性建立,也可以采用不断插入方法建立。由于最差情况下,每个数组都要涉及到一次从树根到底部的操作,因此时间复杂度为O(nlog(n))

fn heap_sort(nums: &mut Vec<usize>) {
    let mut heap: Heap<usize> = Heap::from(nums.clone());
    for i in (0..nums.len()).rev() {
        nums[i] = heap.pop().unwrap();
    }
}

性能对比

为了直观地对比各个排序算法的时间复杂度,本文使用八种排序算法对一个包含10000个范围在0到9999之间的随机整数的数组进行从小到大排序,程序源代码可见此处,各个算法的用时如下

算法 时间 时间复杂度
冒泡排序 13.758615666s O(n^2)
选择排序 6.177197908s O(n^2)
插入排序 2.359652393s O(n^2)
希尔排序 35.799763ms O(n^{3/2})
归并排序 47.860586ms O(nlog(n))
堆排序 26.415899ms O(nlog(n))
快速排序 25.931741ms O(nlog(n))
计数排序 9.198881ms O(n+k)

从结果上可以看出,O(n^2)算法、O(nlog(n))算法和O(n+k)算法之间均存在数量级的差距,归并排序用时大于希尔排序,这和归并排序需要不断拷贝数组有关。

参考文献

  1. javascript-algorithms/src/algorithms/sorting/counting-sort at master · trekhleb/javascript-algorithms
  2. 排序2:希尔排序