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

本文涉及算法的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 ^ b：a = 甲 ^ 乙, b = 乙
• b = a ^ b：a = 甲, b = 甲 ^ 乙 ^ 乙 = 甲 ^ 0 = 甲
• a = a ^ b：a = 甲 ^ 乙 ^ 甲 = 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++
  • 思路
    • 两个指针
      • edge表示它左侧的数是 <= num 的，它是第1个> num的数
      • p表示要检查的数
      • 当 a[p] <= num时，它应该和a[edge]交换

  • 具体实现

    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;
        }
    }
    
    fn split2part(arr: &[i32], num: i32) -> (usize, Vec<i32>) {
        let mut v: Vec<i32> = arr.into();
    
        let mut i: usize = 0;
        let mut nle: usize = 0; // <= 的next下一个
    
        while i < arr.len() {
            if arr[i] <= num {
                v.swap(i, nle);
                nle += 1;
            }
            i += 1;
        }
    
        (nle, v)
    }
    

• 给定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 split3part(arr: &[i32], num: i32) -> (usize, Vec<i32>) {
          let mut v: Vec<i32> = arr.into();
    
          let mut i: usize = 0;
          let mut nlt: usize = 0;
          let mut gt: usize = arr.len(); // 当前数大于num
    
          while i < gt {
              match v[i].cmp(&num) {
                  Ordering::Less => {
                      v.swap(i, nlt);
                      nlt += 1;
                      i += 1;
                  }
                  Ordering::Greater => {
                      gt -= 1;
                      v.swap(i, gt);
                  }
                  _ => i += 1,
              }
          }
    
          (gt, 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 quick_sort1(arr: &[i32]) -> Vec<i32> {
        if arr.len() <= 1 {
            return arr.into();
        }
        let privot = arr.len() - 1;
  
        let n = arr[privot];
        let (nidx, mut v) = split2part(&arr[..privot], n);
        v.push(n);
        v.swap(privot, nidx);
        let lv = quick_sort1(&v[0..nidx]);
        let rv = quick_sort1(&v[nidx + 1..]);
  
        [lv, rv].join(&n)
    }
  

  • 算法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[..])
    }
    
    fn split3part(arr: &[i32], num: i32) -> (usize, Vec<i32>) {
        let mut v: Vec<i32> = arr.into();
    
        let mut i: usize = 0;
        let mut nlt: usize = 0;
        let mut gt: usize = arr.len();
    
        while i < gt {
            match v[i].cmp(&num) {
                Ordering::Less => {
                    v.swap(i, nlt);
                    nlt += 1;
                    i += 1;
                }
                Ordering::Greater => {
                    gt -= 1;
                    v.swap(i, gt);
                }
                _ => i += 1,
            }
        }
    
        (gt, v)
    }
    
    fn quick_sort2(arr: &[i32]) -> Vec<i32> {
        if arr.len() <= 1 {
            return arr.into();
        }
        let privot = arr.len() - 1;
    
        let n = arr[privot];
        let (nidx, mut v) = split3part(&arr[..privot], n);
        v.push(n);
        v.swap(privot, nidx);
        let lv = quick_sort2(&v[0..nidx]);
        let rv = quick_sort2(&v[nidx + 1..]);
    
        [lv, rv].join(&n)
    }
    

  • 算法3.0

    • 随机选择一个数作为privot

      extern crate rand;
      use rand::prelude::*;
      
      fn random_num(range: std::ops::Range<i32>) -> i32 {
          let mut rng = thread_rng();
          rng.gen_range(range)
      }
      
      fn quick_sort3(arr: &[i32]) -> Vec<i32> {
          let mut v: Vec<i32> = arr.into();
          if arr.len() <= 1 {
              return v;
          }
      
          let lidx = arr.len() - 1;
          let privot = random_num(0..arr.len() as i32) as usize;
          let n = arr[privot];
          v.swap(privot, lidx);
      
          let (nidx, mut v) = split3part(&v[..lidx], n);
          v.push(n);
          v.swap(lidx, nidx);
          let lv = quick_sort2(&v[0..nidx]);
          let rv = quick_sort2(&v[nidx + 1..]);
      
          [lv, rv].join(&n)
      }
      

堆排序

堆

• 堆是用数组实现的完全二叉树结构
  • 最大堆（大根堆）
    • 每棵子树的最大值在顶端
  • 最小堆（小根堆）
    • 每棵子树的最小值在顶端
  • 完全二叉树
    • 满二叉树
      • 每层都满的二叉树
    • 从左到右依次变满的二叉树
• 用数组表示
  • [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]
  • 思想
    • 将新num放到堆数组最后一位
    • 从最后一位和它的父节点比较，大于父节点就交换
    • 直到不大于或到root

  • 代码实现

      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;
          }
      }
    
      #[derive(Debug)]
      struct Heap {
          heap: Vec<i32>,
      }
    
      impl Heap {
          fn new() -> Self {
              Self { heap: Vec::new() }
          }
          fn insert(&mut self, num: i32) {
              self.heap.push(num);
              let mut nidx = self.heap.len() - 1;
              while nidx > 0 {
                  let parent = (nidx - 1) / 2;
                  if self.heap[parent] < self.heap[nidx] {
                      self.heap.swap(parent, nidx);
                      nidx = parent;
                  }
              }
          }
      }
    

• 堆化 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 越界
  • 思想
    • 读取root
    • 让h[0] = heap的最后一位
    • 不断的把子节点中大的那个顶上来

  • 代码实现

      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;
          }
      }
    
      fn pop(&mut self) -> Option<i32> {
          if self.heap.len() <= 1 {
              return self.heap.pop();
          }
    
          let root = self.heap.swap_remove(0);
          let last = self.heap.len() - 1;
    
          let mut parent: usize = 0;
          let mut lchd: usize = 2 * parent + 1;
    
          while lchd < last {
              let rchd: usize = lchd + 1;
              let max_idx = if rchd < last && self.heap[lchd] > self.heap[rchd] {
                  lchd
              } else {
                  rchd
              };
    
              if self.heap[parent] >= self.heap[max_idx] {
                  break;
              }
    
              self.heap.swap(parent, max_idx);
              parent = max_idx;
              lchd = 2 * parent + 1;
          }
    
          Some(root)
      }
    

堆排序

• 算法
  • 把数组通过heap_insert变成最大堆
  • 把a[0]和最后一个数交换，同时减少heapsize
    • swap(arr, 0, - -heapsize);
  • 直到所有元素都排好序
• 思想
  • heap[0..end]
    • 1
      • heap.swap(0, end)
      • heap = heap[0..end-1]
      • heapify(heap)
    • 2
      • heap.swap(0, end-1)
      • heapify(heap)
      • heap = heap[0..end-2]
  • 把最大堆的第一个数放到最后
  • 把最后这个最大数从最大堆中除名
  • 堆长度-1

• 代码实现

    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
    }
  
    fn sort(&mut self, arr: &[i32]) -> Vec<i32> {
        for num in arr {
            self.insert(*num);
        }
        let mut v: Vec<i32> = vec![];
        while let Some(num) = self.pop() {
            v.push(num);
        }
  
        v.into_iter().rev().collect()
    }
  

题目

• 已知一个几乎有序的数组(数组要排好序，每个元素移动的距离 < 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]
  • 说明
    • 根据基数排序
      • 百位最后排序，它优先级最高，所以百位可以到数组最右边
    • 越晚排
    • 越靠近想要的结果
      • 先排年龄
      • 再排班级
      • 最后就是按班级排序
      • 相同班级按年龄排序
  • 思想
    • 基数相当于某些特征t1,t2,t3
    • 将数据放到t1特征取值的桶里，再依次从桶里取出放到arr中，相当于arr中的数据对t1特征进行了排序
    • 再将arr的数据放到t2的各种桶里，相当于arr中的数据在保留了t1顺序的情况下，以t2特征值的顺序进行了排序；这时arr中的数据严格拥有t2的特征值顺序，在相同的特征值桶里，数据有着t1特征值顺序

  • 基数桶排序代码实现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
    }
    ```
    

排序算法的总结

稳定性

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

性能

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

问题

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树