计算机基础精校教程
排序、递归与动态规划
从复杂度出发比较经典排序，再把递归、记忆化与动态规划串成一条解题主线。
什么是算法？ algorithm
🏢 提示
解决问题的具体特定方法
- 有限指令集，每条指令的描述不依赖于语言
- 接受一些输入（有些不需要）
- 产生输出
- 一定在有限步骤后终止
排序算法
冒泡排序
🚅 提示
本质上是对比两个相邻的元素，然后交换位置，重复这个过程，直到把元素移动到最后的位置 一次循环只排序一个元素
function bubbleSort(arr:number[]){
// 1. 开启循环
for (let i = 0; i < arr.length; i++) {
// 内层循环是互换顺序，每次需要交换剩余的长度-1次，
let swapped = false
for (let j = 0; j < arr.length-i-1; j++) {
if(arr[j]>arr[j+1]){
const temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
swapped = true
}
}
if(!swapped) break
}
}
选择排序
🚅 提示
分两个区间，排序区间(默认为空)和未排序区间([0,size-1])，遍历未排序区间，选择一个最值，与未排序区间第一个元素交换，即完成一次排序，未排序区间减一
function selectionSort(arr:number[]){
//应该使用双指针实现，一个指针指向未排序的区间开头第一个元素，
// 另一个指针往后寻找最小的元素索引，直到数组尾部
for (let j = 0; j < arr.length; j++) {
let minVal = arr[j],minIndex = j
for (let i = j; i < arr.length; i++) {
if(arr[i]<minVal){
minIndex = i
minVal = arr[i]
}
}
const temp = arr[j]
arr[j] = arr[minIndex]
arr[minIndex] = temp
}
}
插入排序
🚅 提示
分排序区间（默认第一个元素[0,]）和未排序区间([1,size-1])，从未排序区间选取一个值，插入到已排序区间的适合位置，遍历完成后即完成排序
function insertionSort(arr:number[]){
// 从第2个元素开始（默认第一个已经排序），也是
for (let i = 1; i < arr.length ; i++) {
let j = i
while(arr[j]<arr[j-1] && j-1>=0 ){
const temp = arr[j]
arr[j] = arr[j-1]
arr[j-1] = temp
j--
}
}
}
归并排序
🚅 提示
Merge sort 大数组分解成小数组，递归对小数组来排序 递： 按照索引中间的值来划分子数组，不断递归，直到数组长度为1 归： 把返回的左右子数组，使用双指针来逐个元素进行比较，把比较的结果按顺序放到新数组中 分治思想，NlogN
function mergeSort(arr:number[]): number[]{
if(arr.length<=1) return arr
// 1. 分
// 1.1 分子数组
const mid = Math.floor(arr.length/2)
const leftArr = arr.slice(0,mid) // 划分左子数组
const rightArr = arr.slice(mid) // 划分右子数组
//1.2 递归子数组
const newLeftArr = mergeSort(leftArr)
const newRightArr = mergeSort(rightArr)
// 2. 并
let newArr:number[] = []
let j = 0
let i = 0
while(i < newLeftArr.length && j< newRightArr.length){
// 左子数组的元素较小
if(newLeftArr[i]<=newRightArr[j]){
newArr.push(newLeftArr[i])
i++
}else {
// 右左数组的元素较小
newArr.push(newRightArr[j])
j++
}
}
//退出递归后，左子数组还有剩余的情况
if(i<newLeftArr.length){
newArr.push(...newLeftArr.slice(i))
}
//退出递归后，右子数组还有剩余的情况
if(j<newRightArr.length){
newArr.push(...newRightArr.slice(j))
}
return newArr
}
快速排序
🚅 提示
是一种原地排序算法，选取一个基准元素，把大于基准的数放到右边，小于基准的数放到左边，并递归左右子数组 优化：基准元素的选取方法 最坏情况：N平方 平均情况 NlogN
kimi版
function quickSort<T extends number | string>(arr: T[], left: number = 0, right: number = arr.length - 1): T[] {
// 基本情况：如果数组只有一个元素或没有元素，则不需要排序
if (left < right) {
const pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1); // 递归排序左侧子数组
quickSort(arr, pivotIndex + 1, right); // 递归排序右侧子数组
}
return arr;
}
// 辅助函数：对数组进行分区操作
function partition<T extends number | string>(arr: T[], left: number, right: number): number {
const pivot = arr[right]; // 选择最右侧的元素作为基准
let i = left; // `i`用于记录比基准小的元素的索引
for (let j = left; j < right; j++) {
// 如果当前元素小于或等于基准
if (compare(arr[j], pivot)) {
// 交换元素，将较小的元素移到数组的前面
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
// 交换基准元素到它最终的位置
[arr[i], arr[right]] = [arr[right], arr[i]];
return i; // 返回基准的索引
}
// 比较函数，用于比较两个元素，可以根据需要修改以支持不同类型
function compare<T extends number | string>(a: T, b: T): boolean {
// 对于数字，使用数值比较
if (typeof a === 'number' && typeof b === 'number') {
return a <= b;
}
// 对于字符串，使用字典序比较
if (typeof a === 'string' && typeof b === 'string') {
return a.localeCompare(b) <= 0;
}
throw new Error('Unsupported type for comparison');
}
自己实现版
/* 元素交换 */
function swap(nums: number[], i: number, j: number): void {
let tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
/* 快速排序 */
function quickSort(nums: number[] ){
function sort(left:number,right:number){
if(left>=right) return
let i = left, j = right
while (i<j){
// 要让右边先移动，以便到达交界的地方，索引i对应数组中的值，始终时小于基准值的，
// 否则i先移动则会在i ==j的退出条件时，i已经指向了j的值
while(i<j && nums[j]>=nums[left] ){
j--
}
while(i<j&& nums[i]<=nums[left] ){
i++
}
swap(nums,j,i)
}
swap(nums,left,i)
sort(left,i-1)
sort(i+1,right)
}
sort(0,nums.length-1)
}
堆排序
🚅 提示
利用最大堆的特性，每次取出堆顶元素
- 对数组原地建堆
- 取出堆顶元素，与最后一个叶子节点交换
- 堆长度减一，继续进行堆化操作 最关键的就是实现下滤函数
/**
* 堆的下滤操作
* @param arr
* @param i
*/
function hepify_donw(arr:number[],i:number,size:number){
if(i>size) return //越界了
let left = 2*i+1 //左子节点
let right = 2*i+2 //右子节点
let swapIndex = i // 假定有交换的索引
if(left <= size && arr[left]>arr[swapIndex]) swapIndex = left
// 左子节点在数组范围内，且左子节点的值大于要交换节点的值
if(right <= size && arr[right]>arr[swapIndex]) swapIndex = right
// 右子节点在数组范围内，且右子节点的值大于要交换的节点的值
if(swapIndex!==i){ // 如果要交换的节点不是当前节点
// swap(arr,swapIndex,i) // 交换
[arr[i],arr[swapIndex]] = [arr[swapIndex],arr[i]]
hepify_donw(arr,swapIndex,size) // 交换后的节点，再次下滤
}
}
/**
* 堆排序
* @param arr
* @returns
*/
function heapSort(arr:number[]):number[]{
// 1. 原地建堆,原地排序
const size = arr.length - 1
for(let i=Math.floor((size-1)/2);i>=0;i--){
// 从第一个非叶子节点开始堆化，直到堆顶
hepify_donw(arr,i,size)
}
// 2. 出堆，排序，堆的长度减一，再次堆化，下滤
for (let j = size; j >0 ; j--) {
// swap(arr,j,0)
[arr[0],arr[j]] = [arr[j],arr[0]]
hepify_donw(arr,0,j-1)
}
return arr
}
希尔排序
🚅 提示
动态规划
🚅 提示
解题步骤：
- 定义状态
🍰 提示
将问题划分为若干个子问题，定义状态表示子问题的解，通常使用一个数组或矩阵来表示 存储子问题的状态
- 状态转移方程
🎹 提示
在计算子问题的基础上逐步构建原问题的解 这个过程通常用【状态转移方程】来描述，表示从一个状态转移到另一个状态的转移规则 这是动态规划最重要的步骤，怎么寻找前后之间的关系 也就是说，当前状态是如何从前一个(或多个)状态中计算得到的
- 初始化状态
🎼 提示
设置最开始子问题的状态
- 求解最优
🍞 提示
通过计算状态之间的的转移，最终计算出问题的解
通常使用递归或迭代的方式计算
斐波那契求解
递归&记忆化搜索
function fib(num:number,memory:number[]=[]):number{
if(num<=1) return num
if(memory[num]) return memory[num]
const res = fib(num-1,memory) + fib(num-2,memory)
memory[num] = res
return res
}
📌 提示
这里的求解过程是自顶向下的方式
动态规划方式
function fib(n:number):number{
// 1. 定义状态
const dp:number[] = []
// 初始化状态
dp[0]=0
dp[1]=1
for (let i = 2; i <= n; i++) {
// 2. 初始化状态 优化成上面的方式，减少2次循环
// if(i<=1) {
// dp[i] = i
// }
// 3. 状态转移方程
dp[i] = dp[i-1] +dp[i-2]
}
// 4. 获取最终结果
return dp[n]
}
🥖 提示
自底向上的方式求解，可以使用迭代来完成 先求解子问题
状态压缩
💡 提示
在这里的情况下，实际上只需要知道前面2次的状态，而不需要保留以前的状态，所以，可以不使用数组保存，降低空间复杂度，从O(n) 到O(1) 并不是所有的动态规划都可以压缩状态
function fib(n:number):number{
if(n<=1) return n
// 1. 定义状态 & 初始化状态,状态压缩到只保留前2项
let pre = 0,cur =1
for (let i = 2; i <= n; i++) {
// 3. 状态转移方程
const newVal = pre + cur
pre = cur
cur =newVal
}
// 4. 获取最终结果
return cur
}