Rust·算法·排序

 

排序算法 选择、冒泡、插入、归并、快速、堆

  • 排序算法
    • 选择、冒泡、插入、归并、快速、堆

本文涉及算法的rust源码

对数器

  • 对于想测试的算法a
  • 找到暴力解法b
  • 随机样本生成器c
  • 对比a,b生成的结果
  • 随机数

    use rand::distributions::Uniform;
    use rand::prelude::*;
    
    fn rand_nums(num: usize) -> Vec<i32> {
        let mut rng = thread_rng();
    
        let distri = Uniform::new_inclusive(0, 10);
        (&mut rng).sample_iter(distri).take(num).collect()
    }
    
    // 单个数
    let mut rng = thread_rng();
    let num = rng.sample(Uniform::new(0, 8));
    
    • cargo.toml

      [dependencies]
      rand = "0.8.5"
      

选择排序

  • 算法流程
    • 在[0, n-1]找到最小值a[i]
    • swap(a, 0, i)
    • 在[1, n-1]找最小值a[i]
    • swap(a, 1, i)
  • 总结
    • idx: [0, len-1]
      • a[idx] 和 (a[idx+1..len])min
    • 让idx上的数是[idx,n)上最小的数
  • 代码实现

      fn choice_sort(arr: &mut Vec<i32>) {
        for idx in 0..arr.len() - 1 {
            let mut min = idx;
            for compare in idx + 1..arr.len() {
                min = if arr[min] > arr[compare] { compare } else { min };
            }
            swap(arr, idx, min);
        }
      }
    

冒泡排序

  • 算法
    • [0, N-1]
      • 比较a[i], a[i+1],谁大谁往右移
      • 一轮之后a[N-1]是最大值
    • [0, N-2]
      • 得到a[N-2]是最大值
  • 思想
    • 每一轮的刷新,都让大数后移
    • 每一轮[0, dix)的两两比较,都让大的数后移
  • 代码实现

      fn bubble_sort(arr: &mut Vec<i32>) -> &mut Vec<i32> {
          if arr.len() < 2 {return arr;}
          for sorted_idx in (0..arr.len()).rev() {
              for i in 0..sorted_idx {
                  if arr[i] > arr[i + 1] {
                      swap(arr, i, i + 1);
                  }
              }
          }
          arr
      }
    

异或的性质

  1. 交换律、结合律
    • a^b = b^a
  2. 无进位相加
    • 1 + 1 = 0
    • 1 + 0 = 1
  3. 0 ^ x = 0, x^x = 0
  4. a ^ b = b ^ a, a ^ b ^ c = a ^ (b ^ c)
  5. (...A...) ^ B = (...a1...) ^ B ^ (...a2...)

两个数的交换

a = a ^ b; b = a ^ b; a = a ^ b

a = 甲,b = 乙

  • a = a ^ ba = 甲 ^ 乙, b = 乙
  • b = a ^ ba = 甲, b = 甲 ^ 乙 ^ 乙 = 甲 ^ 0 = 甲
  • a = a ^ ba = 甲 ^ 乙 ^ 甲 = 0 ^ 乙 = 乙 = b

a, b必须是不同的2块内存,否则 a ^ b = 0

为什么异同满足交换律

  • 假设 a = 0b0100, b = 0b1001, c = 0b1111
    • 其中某位是否为1,与这1位出现1的奇偶次数有关,与1出现的前后无关
    • 所以某位是否为1 = 0 + 1 + 1 = 0

题目

  1. 在数组中,只有一种数出现奇数次,其他数出现偶数次,如何找到此数
     let mut eor: i32 = 0;
     for cur in arr.iter() {
         eor ^= cur;
     }
     eor
    
  2. 在数组中,只有两种数出现奇数次,其他数出现偶数次,如何找到此数
  • 算法
    • a[0]^a[1]^...^a[n] = x ^ y
    • 假设 x^y = 0b010101,则第1位为1的数不是x就是y
    • eor = x^y, 且 x != y,则eor上某一位必不为0
    • 设eor的bit[8]=1,说明x,y在bit[8]上一定有一个为1,一个为0
    • 那么bit[8]=1可以把arr中的数分成两个部分,一个部分只包含x,一个部分只包含y
    • 那么eor' = a_xory[0] ^ a_xory[1] ^ ... ^ a_xory[i] = xory
    • eor ^ eor' = x(或者y)
  • 代码实现

    pub fn find2num(arr: &Vec<i32>) -> (i32, i32) {
        let mut eor = 0; // eor = a ^ b
        let mut eor2 = 0; // eor2 = a or b
        for cur in arr.iter() {
            eor ^= cur;
        }
    
        let right_one = eor & (!eor + 1); // 取出最右位的1
        for cur in arr.iter() {
            if cur & right_one != 0 {
                eor2 ^= cur;
            }
        }
    
        let a = eor ^ eor2;
        let b = eor ^ a;
        (a, b)
    }
    

插入排序

arr = [3, 2, 5, 4, 2, 3, 3]

  • 算法
    • 先实现[0, 0]范围内有序 (ok)
    • 实现[0, 1]范围有序, i = 1
      • 向左看
        • 如果i比左边小,就交换

          arr = [2, 3, ...]

      • 再向左看,越界,退出
      • 此时[0, 1]有序 (ok)
    • 实现[0, 2]有序, i = 2
      • 向左看,此时a[2] > a[1],有序,退出

        arr = [2, 3, 5, ...]

    • 实现[0, 3]有序, i = 3
      • 向左看
        • a[3] < a[2],swap(a, 2, 3), i = 2
      • 向左看
        • a[2] > a[1], 有序(ok)
  • 思想
    • 每轮通过两两交换,把a[idx]插入到a[0:idx-1]中它最大的位置
  • 代码实现

      fn insert_sort(arr: &mut Vec<i32>) -> &mut Vec<i32> {
          if arr.len() < 2 { return arr; }
          for i in 0..arr.len() {
              for j in (1..=i).rev() {
                  if arr[j] < arr[j - 1] {
                      swap(arr, j, j - 1);
                  }
              }
          }
          arr
      }
    

二分法

  • 2分法是建立一个排他的规则,每次删除一半,答案在另一半
  • 一个问题优化的方向
    • 优化数据状况:无序变有序
    • 问题标准:可应用2分法
  • 比如:
    • arr无序,相邻数不相等,求局部最小值
      • 局部最小
        • 最左侧:a[0] < a[1]:a[0]是局部最小
        • 最右侧:a[N-1] > a[N]:a[N]局部最小
        • 中间:a[i-1] > a[i] < a[i+1],a[i]局部最小
  • 二分法找arr中的最大值代码实现

      fn bin_searchmax(arr: &Vec<i32>, l: usize, r: usize) -> i32 {
          if l == r { return arr[l]; };
    
          let mid = l + ((r - l) >> 1);
          let left_max = bin_searchmax(arr, l, mid);
          let right_max = bin_searchmax(arr, mid + 1, r);
          return cmp::max(left_max, right_max);
      }
    
  • 划分过程
    • arr = [3, 2, 5, 6, 7, 4]

递归的master公式

$T(N) = a \times T(\dfrac{N}{b}) + O(N^d)$

  1. $log_b{a} > d$: 复杂度为 $O(N^{log_b{a}})$
  2. $log_b{a} = d$:复杂度为$O(N^d \times log_2{N})$
  3. $log_b{a} < d$:复杂度为$O(N^d)$

归并排序

  • 算法流程
    • 找到中心
    • 左边排序
    • 右边排序
    • 合并
  • 算法实现

      fn merge_arr(left_arr: Vec<i32>, right_arr: Vec<i32>) -> Vec<i32> {
          let mut i = 0usize;
          let mut j = 0usize;
          let capacity = left_arr.len() + right_arr.len();
          let mut res: Vec<i32> = Vec::with_capacity(capacity);
          while i < left_arr.len() && j < right_arr.len() {
              if left_arr[i] <= right_arr[j] {
                  res.push(left_arr[i]);
                  i += 1;
              } else {
                  res.push(right_arr[j]);
                  j += 1;
              }
          }
          res.extend_from_slice(&left_arr[i..]);
          res.extend_from_slice(&right_arr[j..]);
          res
      }
    
      fn merge_sort(arr: Vec<i32>) -> Vec<i32> {
          if arr.len() < 2 {
              return arr;
          }
          let mid_plus = (arr.len() + 1) / 2;
          let mut left_arr = arr;
          let right_arr = left_arr.split_off(mid_plus);
          let left_arr = merge_sort(left_arr);
          let right_arr = merge_sort(right_arr);
          return merge_arr(left_arr, right_arr);
      }
    
  • 为什么归并排序可以缩短时间 O(N^2) -> O(N·logN)
    • 因为O(N^2)浪费了大量比较行为才搞定一个数
      • 选择排序比较了N次,得到一个最小值放到a[0]
      • 对于a[1]又要比较N-1次
    • 归并排序没有浪费比较行为
      • 合并过程是左侧与右侧比较
      • 比较信息都留下了,变成一个整体有序的部分
      • 所以有序信息是向下传递的
        • 每部分都保留了有序信息
        • 合成整体时就缩短了时间

小和问题

小和:每个数左边比当前数小的数之和

  • arr = [1, 3, 4, 2, 5]
    • 1: 左无
    • 3: 左有 1
    • 4:左有 1+3 = 4
    • 2:左有 1
    • 5:左有 1+3+4+2 = 10
    • 小和为 16
  • 求左边比它小,等价于右边有多少个数比它大,它就要被加多少次(产生出多少个小和)
    • 1:右边4个数大于它,产生4个1
    • 3:右边2个数,生产2个3
    • 4:右边1个数,生产1个4
    • 2:右边1个数,生产1个2
    • 5:右边无

  • 代码实现

      fn smallsum_merge(left_arr: Vec<i32>, right_arr: Vec<i32>) -> (i32, Vec<i32>) {
          let mut ss = 0;
          let mut i = 0;
          let mut j = 0;
          let mut merge: Vec<i32> = Vec::new();
          while i < left_arr.len() && j < right_arr.len() {
              if left_arr[i] < right_arr[j] {
                  ss += left_arr[i] * (right_arr.len() - j) as i32;
                  merge.push(left_arr[i]);
                  i += 1;
              } else {
                  merge.push(right_arr[j]);
                  j += 1;
              }
          }
          merge.extend_from_slice(&left_arr[i..]);
          merge.extend_from_slice(&right_arr[j..]);
          (ss, merge)
      }
    
      fn smallsum_process(arr: Vec<i32>) -> (i32, Vec<i32>) {
          if arr.len() == 1 {
              return (0, arr);
          }
          let mid_plus: usize = (arr.len() + 1) / 2;
          let mut left_arr = arr;
          let right_arr = left_arr.split_off(mid_plus);
          let (ss_left, left_arr) = smallsum_process(left_arr);
          let (ss_right, right_arr) = smallsum_process(right_arr);
          let (ss_merge, merge) = smallsum_merge(left_arr, right_arr);
          return (ss_left + ss_right + ss_merge, merge);
      }
    
  • 归并的本质

    • 递归
    • 合并
      • 一个有序数组中的元素与另一个有序数组中的元素一一比较
      • 但当A组中的元素小于B组中某位置的元素时
      • 不再需要与B组中后面的元素再比较了
      • 因为B是有序的数组
      • 最终也等效于A、B两个数组中的所有元素都一一做了比较
    • 所以当要对一个数组中的元素进行一一比较时,就可以用归并排序的思路
      • 先递归(调度)
        • 是以数组的中间位置为调度分层
      • 再合并(比较)

荷兰国旗

  • 给定一个数组arr和一个数num,把<=num的书放到左边,>num的数放右边
    • 算法
      • 给定两个变量,把数组划分成三个部分
        • edge变量,是 <= 区域的边界
        • i变量,是待判定的元素
        • [edge, i)是 > 区域
      • if arr[i] <= num: swap(arr, edge++, i++);
      • else: i++
    • 具体实现

      fn split2part(arr: &mut Vec<i32>, num: i32) {
          let mut edge: usize = 0;
          let mut i = 0usize;
          while i < arr.len() {
              if arr[i] <= num {
                  arr.swap(i, edge);
                  edge += 1;
              }
              i += 1;
          }
      }
      
  • 给定arr和num,把数据分成<, =, >三个部分
    • 算法
      • 给定三个变量,把数组分成四个部分
        • small:small-(small的左边,不包括small) 部分是 <num 的区域
        • big: big部分是 >num 的区域
        • i: i+是待定区域
        • [small, big-1]是==区域
      • if arr[i] < num, swap(arr, i++, small++);
      • if arr[i] > num, swap(arr, i, –big)
      • if arr[i] == num, i++
    • 思想
      • 用三个指针把arr分成了<, =, 待定, >四个区域
        • [.., lt), [lt, i), [i, gt], (gt, ..)
      • 对于待定值 arr[i] 情况有三种
        • <: arr.swap(i, lt); lt++
          • a.swap(i, lt)相当于把a[i]这个小的数放到原来<区域的旁边1格
          • lt++:这个区域向右扩大1位,包住交换过来的a[i]
          • a.swap(i, lt)还把a[lt]这个=区域的数放到刚刚判定a[i]的位置,相当于=区域向右平移了一格
          • <区域是向右扩充的一格,=区域是向右平移了一格(是长度,区域中数据的顺序是变了的,a[lt]这个头变成了尾)
        • >: a.swp(i, gt); gt--
          • a.swap(i, gt)把考察的数a[i]放到>区域的左边一格
          • gt--把这个a[i]包进>区域
          • a.swap(i, gt)交换过来[i]位置的a[gt]没有被考察过,所以要在考察<, =, >的情况
        • =: i++:因为a[lt, i)=区域,所以直接向右扩充=区域
      • i从左向右,推着<,=,>区域运动,当i==gt时,说明待考察a[i]已经落在>区域中,不用再考察了
    • 具体实现

        fn split3part(arr: &mut Vec<i32>, num: i32) {
            let mut small = 0usize;   // small-1才是<num的区域
            let mut big = arr.len(); // big 是>num的区域
            let mut i = 0usize;
            while i < big {
                if arr[i] < num {
                    arr.swap(i, small);
                    small += 1;
                    i += 1;
                } else if arr[i] > num {
                    big -= 1;
                    arr.swap(i, big);
                } else {
                    i += 1;
                }
            }
        }
      
        fn 荷兰国旗(v: &[i32], num: i32) -> Vec<i32> {
            let mut v: Vec<i32> = v.into();
            let mut gt: usize = v.len() - 1;
            let mut lt: usize = 0;
            let mut i: usize = 0;
      
            while i < gt {
                match v[i].cmp(&num) {
                    Ordering::Equal => i += 1,
                    Ordering::Less => {
                        v.swap(i, lt);
                        lt += 1;
                        i += 1;
                    }
                    Ordering::Greater => {
                        v.swap(i, gt);
                        gt -= 1;
                    }
                }
            }
      
            v
        }
      

快速排序

  • 快排算法是荷兰国旗问题的推广
    • 算法v1.0
      • 确定最后一个数所在的位置
        • 用最后一个数做num
        • 把数组划分成:[…<= num…], [..>num..], [num] 三个区域
        • 把num和[>num]区域的第1个数交换,得到[…<=num…],[num], […>num..]区域
        • 同时,这个交换的num所在的位置就是它在排好序数组中应该在的位置
      • 把这个数左右两边递归快排
    • 算法v2.0
      • 确定最后一个数及其相等的数所在的位置
        • 用最后一个数做num
        • 把数组划分成:[…< num…], [..=num..], [..>num..], [num] 四个区域
        • 把num和[>num]区域的第1个数交换,得到[.<num..], [..=num..], [..>num..]三个区域
        • 同时,这个交换的num所在的位置就是它在排好序数组中应该在的位置
      • 在左右两边递归
    • 算法v3.0
      • 确定随机指定的数及等数所在的位置
        • 随机待定一个数和最后一个数交换
        • 划分数组:[..<num..], [..=num..], [..>num..], [num]
          • 其中small, big所在的位置是[=num]的两侧
          • [..<num..], [small..=num..big], [..>num..]
          • a[small] == num, a[small-1] < num
          • a[big] == num, a[big+1] > num
        • 交换num和[>num]的第1个数
      • 递归
  • 算法v1.0

      fn quick_sort1(mut arr: Vec<i32>) -> Vec<i32> {
          if arr.len() <= 1 {
              return arr;
          }
          let last_idx = arr.len() - 1;
          let num = arr[last_idx];
          let mut small = 0usize;
          let mut i = 0usize;
          while i < last_idx {
              if arr[i] <= num {
                  swap(&mut arr, i, small);
                  small += 1;
              }
              i += 1;
          }
          swap(&mut arr, small, last_idx);
      
          let right_arr = arr.drain(small + 1..).collect();
          let left_arr = arr.drain(0..small).collect();
          let left_sorted = quick_sort1(left_arr);
          let right_sorted = quick_sort1(right_arr);
          [left_sorted, right_sorted].join(&num)
      }
    
      fn 快排1(nums: &[i32]) -> Vec<i32> {
          if nums.len() <= 1 {
              return nums.into();
          }
    
          let last = nums.len() - 1;
          let num = nums[last];
          let mut nums: Vec<i32> = nums.into();
          let mut le: usize = 0;
          let mut i: usize = 0;
    
          while i < last {
              if nums[i] <= num {
                  nums.swap(i, le);
                  le += 1;
              }
              i += 1;
          }
          nums.swap(le, last);
    
          [快排1(&nums[..le]), 快排1(&nums[le + 1..])].join(&num)
      }
    
    • 算法v2.0

      fn quick_sort2(mut arr: Vec<i32>) -> Vec<i32> {
          if arr.len() <= 1 {
              return arr;
          }
          let mut outline = false;
          let mut i = 0usize;
          let last = arr.len() - 1;
          let mut small = 0usize; // [0, small-1]是<num的区域
          let mut big = last - 1; // [big+1, end]是>num的区域
          let num = arr[last];
          while i <= big {
              if arr[i] < num {
                  arr.swap(i, small);
                  small += 1;
                  i += 1;
              } else if arr[i] > num {
                  arr.swap(i, big);
                  //rust的usize>= 0
                  if big == 0 {
                      outline = true;
                      break;
                  } else {
                      big -= 1;
                  }
              } else {
                  i += 1;
              }
          }
          if outline {
              // >num区的第1个数在0位置时,要单独处理
              arr.swap(i, last);
              big = 0;
          } else {
              // 把最后一个数和>num区的第1个数交换
              arr.swap(big + 1, last);
              // >num边界同时向右移
              big += 1; // 保证big_plus是>num的区域 [big+1, end]
          }
      
          // arr => [small_arr, equal_arr, big_arr]
          let big_arr = arr.drain(big + 1..).collect();
          let small_arr = arr.drain(0..small).collect();
          let big_sorted = quick_sort2(big_arr);
          let small_sorted = quick_sort2(small_arr);
          [small_sorted, big_sorted].join(&arr[..])
      }
      

堆排序

  • 堆是用数组实现的完全二叉树结构
    • 最大堆(大根堆)
      • 每棵子树的最大值在顶端
    • 最小堆(小根堆)
      • 每棵子树的最小值在顶端
    • 完全二叉树
      • 满二叉树
        • 每层都满的二叉树
      • 从左到右依次变满的二叉树
  • 用数组表示
    • [i]的左子: [2*i + 1]
    • [i]的右子: [2*i + 2]
    • [i]的父: [(i-1)/2]

heap insert 过程

  • 最大堆的建构过程
    • 算法
      • heapsz = 0
      • heap_insert(5)
        • a[heapsz++] = 5
        • heapsz = 1
        • a = [5]
      • heap_insert(3)
        • a[heap_size++] = 3
        • heapsz = 2
        • a = [5, 3]
      • heap_insert(6)
        • a[heapsz++] = 6
        • a = [5, 3, 6]
        • a[2] = 6 > a[(2-1)/2]=a[0]=5
        • swap(a, 2, 0)
          • a = [6, 3, 5]
        • heapsz = 3
      • heap_insert(7)
        • a[heapsz++] = 7
        • a = [6, 3, 5, 7]
        • a[3] = 7 > a[1] = 5
        • swap(a, 3, 1)
          • a = [6, 7, 5, 3]
        • a[1] = 7 > a[0] = 6
        • swap(a, 1, 0)
          • a = [7, 6, 5, 3]
        • heapsz = 4
      • heap_insert(7)
        • a[heapsz++] = 7
        • a = [7, 6, 5, 3, 7]
        • a[4] = 7 > a[1] = 6
        • swap(a, 4, 1)
          • a = [7, 7, 5, 3, 6]
    • 代码实现

        fn heap_insert(arr: &mut Vec<i32>, num: i32) {
            arr.push(num);
            let mut i = arr.len() - 1;
            if i == 0 {
                return;
            }
            while i > 0 && arr[i] > arr[(i - 1) / 2] {
                arr.swap(i, (i - 1) / 2);
                i = (i - 1) / 2;
            }
        }
      
  • 堆化 heapify
    • 从堆中取出最大值后,堆仍保持最大堆
    • 算法
      • 取出a[0]
      • 令a[0] = a[–heapsz]
      • i = 0
      • 取 max_id = max(a[2i+1], a[2i+2])
      • if a[0] < a[max_id]:
        • swap(a, 0, max_idx)
        • i = max_idx
      • 直到 i 越界
    • 代码实现

        fn heapify(arr: &mut Vec<i32>, idx: usize, heapsize: usize) {
            let mut i = idx;
            let mut left = 2 * i + 1;
      
            while left < heapsize {
                let right = left + 1;
                let max_idx = if right < heapsize && arr[left] < arr[right] {
                    right
                } else {
                    left
                };
      
                let max_idx = if arr[i] < arr[max_idx] { max_idx } else { i };
                if max_idx == i {
                    break;
                }
                arr.swap(i, max_idx);
                i = max_idx;
                left = 2 * i + 1;
            }
        }
      

堆排序

  • 算法
    • 把数组通过heap_insert变成最大堆
    • 把a[0]和最后一个数交换,同时减少heapsize
      • swap(arr, 0, –heapsize);
    • 直到所有元素都排好序
  • 代码实现

      fn heap_sort(arr: Vec<i32>) -> Vec<i32> {
          let mut res: Vec<i32> = Vec::new();
          for num in arr {
              heap_insert(&mut res, num);
          }
    
          let mut heapsize = res.len();
          while heapsize > 0 {
              res.swap(0, heapsize - 1);
              heapsize -= 1;
              heapify(&mut res, 0, heapsize);
          }
    
          res
      }
    

题目

  • 已知一个几乎有序的数组(数组要排好序,每个元素移动的距离 < k, k较小)。选择合适的算法排序
    • 算法
      • 先把k个数字放到最小堆中
      • 堆顶一定是k个数字中最小的元素(数组几乎有序)
      • 把a[0]弹出
      • 再a[7]放到a[0],进行堆化,得到a[1:7]的最小值
      • 把a[1]弹出,重复进行,直到最后
    • 代码实现

        use std::cmp::Reverse;
        use std::collections::BinaryHeap;
      
        fn sortarr_distancek(arr: &mut Vec<i32>, k: usize) -> Vec<i32> {
            let mut min_heap = BinaryHeap::new();
            let mut res: Vec<i32> = vec![];
      
            for i in 0..k {
                min_heap.push(Reverse(arr[i]));
            }
      
            for i in k..arr.len() {
                if let Some(Reverse(min_val)) = min_heap.pop() {
                    res.push(min_val);
                }
                min_heap.push(Reverse(arr[i]));
            }
            while let Some(Reverse(min_val)) = min_heap.pop() {
                res.push(min_val);
            }
      
            res
        }
      

比较器的作用

  • 比较器返回负数时
    • 第1个参数在前面
    • 升序排列
  • 比较器返回正数时
    • 第2个参数在前面
    • 逆序排列

桶排序

  • 不基于比较的排序,一定是根据数据的特定状况定制的方法
  • 记数排序
    • 员工年龄
      • 申请age_freq[200]
      • 遍历所有年龄,统计年龄词频
        • age_freq[age[i]]++
        • 得到age_freq = [7, 3, 4, ….]
      • 恢复成
        • age = [7个0, 3个1, 4个2, ….]
      • 缺点
        • 数据跨度大[-10^20, 10^20]
        • 要申请大容量的数组
  • 基数排序
    • 排序[17, 13, 25, 100, 72]
    • 算法
      • 补成相同位数 [017, 013, 025, 100, 072]
      • 准备10个桶b[0], b[1], … b[9]
      • 按个位数依次进桶
        • b[0] = [100]
        • b[2] = [072]
        • b[3] = [013]
      • 从左到右依次出桶
        • a = [100, 072, 013, …]
      • 按十位数进桶、再出桶
      • 按百位数进桶、再出桶
        • a = [013, 017, 025, 072, 100]
    • 说明
      • 根据基数排序
        • 百位最后排序,它优先级最高,所以百位可以到数组最右边
      • 越晚排
      • 越靠近想要的结果
        • 先排年龄
        • 再排班级
        • 最后就是按班级排序
        • 相同班级按年龄排序
    • 基数桶排序代码实现1

      ```rust
      fn radix_sort(arr: Vec<i32>, ndigit: usize) -> Vec<i32> {
          let mut arr = arr;
          let mut buckets: Vec<Vec<i32>> = vec![vec![]; 10];
      
          for d in 0..ndigit {
              for i in 0..arr.len() {
                  let dnum = get_digit(arr[i], d);
                  buckets[dnum].push(arr[i]);
              }
      
              let mut i = 0usize;
              for bucket in buckets.iter_mut() {
                  for &num in bucket.iter() {
                      arr[i] = num;
                      i += 1;
                  }
                  bucket.clear();
              }
          }
          arr
      }
      ``` - 用前缀和实现基数桶排序实现2
      
      ```rust
      fn radix_sort2(arr: Vec<i32>, ndigit: usize) -> Vec<i32> {
          let mut arr = arr;
          let mut help = vec![0; arr.len()];
          for digit in 0..ndigit {
              // 词频
              let mut count: Vec<usize> = vec![0; 10];
              for &num in arr.iter() {
                  count[get_digit(num, digit)] += 1;
              }
              // 前缀和
              for i in 1..count.len() {
                  count[i] += count[i - 1];
              }
              // 排序
              for i in (0..arr.len()).rev() {
                  let idx = get_digit(arr[i], digit);
                  help[count[idx] - 1] = arr[i];
                  count[idx] -= 1;
              }
              for i in 0..help.len() {
                  arr[i] = help[i];
              }
          }
      
          arr
      }
      ```
      

排序算法的总结

稳定性

  • 定义
    • 排序过程不会改变相同数据的先后顺序
  • 稳定
    • 冒泡排序
    • 插入排序
    • 归并排序
  • 不稳定
    • 选择排序
    • 快速排序
    • 堆排序

性能

排序 时间复杂度 空间复杂度 稳定性
选择排序 $O(N^2)$ $O(1)$ ×
冒泡排序 $O(N^2)$ $O(1)$
插入排序 $O(N^2)$ $O(1)$
归并排序 $O(N \times log_2{N})$ $O(N)$
快速排序 $O(N \times log_2{N})$ $O(log_2{N})$ ×
堆排序 $O(N \times log_2{N})$ $O(1)$ ×

在大量的实践中,快速排序表现好于归并排序

问题

  1. 把奇数在左、偶数在右,
    • 算法:快速排序中的partition
       fn split_oddeven_quick(arr: &mut Vec<i32>) {
           let mut odd = 0usize;
           let mut i = 0usize;
           while i < arr.len() {
               if arr[i] % 2 == 0 {
                   arr.swap(i, odd);
                   odd += 1;
               }
               i += 1;
           }
       }
    
  2. 要求相对原始次序不变
    • 算法:归并排序
       fn merge_oddeven_arr( left: Vec<i32>, edgel: usize, 
                             right: Vec<i32>, edger: usize,
       ) -> (usize, Vec<i32>) {
           let mut res = vec![];
    
           res.extend_from_slice(&left[..edgel]);
           res.extend_from_slice(&right[..edger]);
           res.extend_from_slice(&left[edgel..]);
           res.extend_from_slice(&right[edger..]);
    
           (edgel + edger, res)
       }
    
       fn merge_oddeven(arr: Vec<i32>) -> (usize, Vec<i32>) {
           if arr.len() == 1 {
               let edge = if arr[0] % 2 != 0 { 0 } else { 1 };
               return (edge, arr);
           }
           let mid_plus = (arr.len() + 1) / 2;
           let mut left = arr;
           let right = left.split_off(mid_plus);
           let (edge_l, left) = merge_oddeven(left);
           let (edge_r, right) = merge_oddeven(right);
           merge_oddeven_arr(left, edge_l, right, edge_r)
       }
    

哈希表和有序表

  • 哈希表
    • 只有key的是HashSet
    • 有key:val的是HashMap
    • HashMap的增、删、改、查是O(1),只是常数时间大
  • 有序表 TreeSet和TreeMap
    • 时间复杂度:O(logN)级别
    • 红黑树、AVL树、SB树