学习一下一些经典数据结构和排序算法

1.快速排序

1.基本思想

快速排序是一种高效的分治算法，其核心思想是：

选择一个基准元素（pivot）：通常是数组中的某个元素。
分区（Partition）：将数组分为两部分，使得左边元素均 ≤ 基准，右边元素均 ≥ 基准。
递归排序：对左右子数组递归执行上述操作，直到子数组长度为1或0（已有序）。

2.分区（Partition）过程详解

分区是快速排序的核心步骤，目的是将数组划分为两个子数组。以双指针法为例：

基准选择：通常选第一个元素 arr[left] 作为基准（也可随机选择优化性能）。
双指针移动：
- 左指针（i）：从左向右找第一个 > 基准的元素。
- 右指针（j）：从右向左找第一个 < 基准的元素。
交换元素：当找到后，交换这两个元素，继续移动指针。
放置基准：最终将基准元素交换到正确的位置，返回其下标。

3.Java 代码实现

class Solution {

    private static final Random RANDOM=new Random();

    public int[] sortArray(int[] nums) {
        if(nums==null||nums.length==0) return nums;
        quickselect(nums,0,nums.length-1);
        return nums;
    }

    public void quickselect(int[] nums,int left,int right){
        if(left < right){
            int pivotIndex=partition(nums,left,right);
        	quickselect(nums,left,pivotIndex-1);
        	quickselect(nums,pivotIndex+1,right);
        }
    }

    public int partition(int[] nums,int left,int right){	//最关键核心的部分
        int randomIndex=RANDOM.nextInt(right-left+1)+left;	//随机选择基准
        swap(nums,left,randomIndex);
        int i=left+1,j=right;
        int pivot=nums[left];
        while(true){
            while(i<=j && nums[i]<pivot) i++;
            while(i<=j && nums[j]>pivot) j--;
            if(i>=j) break;
            swap(nums,i,j);
            i++;
            j--;
        }
        swap(nums,left,j);
        return j;
    }

    public void swap(int[] nums,int i,int j){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
}

4.时间复杂度分析

平均情况：O(n log n)
每次分区将数组大致分为两半。
最坏情况：O(n²)
当数组已有序且总选第一个元素为基准时，退化为冒泡排序。
优化策略：
- 随机选择基准：减少最坏情况概率。
- 三数取中法：选左、中、右三个数的中位数作为基准。

2.动态规划之0-1背包问题为什么要压缩数组？

1.0-1背包问题简介

0-1背包问题是一个经典的动态规划问题。假设我们有 n 个物品，每个物品有重量 w[i] 和价值 v[i]，以及一个容量为W的背包。每个物品只能选择拿或不拿（0或1），目标是选择一些物品放入背包，使得总重量不超过 W，同时总价值最大。

2.二维DP的思路

我们先从传统的二维DP数组讲起，因为它是一维DP的基础。

定义DP数组

定义 dp[i][j] 表示：前 i 个物品（从 0 到 i-1），背包容量为 j 时，能获得的最大价值。
其中：
- i 表示考虑前 i 个物品。
- j 表示背包的当前容量。

状态转移方程

对于第 i 个物品（编号从 1 开始），我们有两种选择：

不拿第 i 个物品：
- dp[i][j] = dp[i-1][j]，即不放入当前物品，价值等于前 i-1 个物品在容量 j 下的最大价值。
拿第 i 个物品（前提是背包容量足够，即 j >= w[i]）：
- dp[i][j] = dp[i-1][j - w[i]] + v[i]，即放入当前物品，用掉 w[i]的容量，价值增加 v[i]。
综合选择：
- dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])（如果 j >= w[i]）。
- 如果 j < w[i]，则只能不拿，dp[i][j] = dp[i-1][j]。

初始化

当没有物品时（i = 0），价值为 0，即 dp[0][j] = 0 对于所有 j。

目标

最终答案是 dp[n][W]，表示前 n 个物品在容量 W 下的最大价值。

空间复杂度

二维DP需要一个 n × W 的数组，空间复杂度是 O(nW)。

3.优化到一维DP

观察二维DP的状态转移方程，我们发现dp[i][j]只依赖于上一行（i-1）的数据，即dp[i-1][j]和 dp[i-1][j - w[i]]。这意味着我们不需要存储整个二维数组，只需要用一个一维数组保存“上一行”的结果，并在计算当前物品时更新它。

定义一维DP数组

定义 dp[j] 表示：背包容量为 j 时，能获得的最大价值。
这个数组会随着物品的遍历不断更新，最终反映所有物品考虑后的结果。

状态转移方程

对于每个物品 i，更新 dp[j]：
- 如果 j >= w[i]，则 dp[j] = max(dp[j], dp[j - w[i]] + v[i])。
- 如果 j < w[i]，则 dp[j] 不变（因为装不下当前物品）。

关键问题：遍历顺序

在一维DP中，dp[j] 会被反复更新。如果我们正向遍历（从 j = 0 到 W），会导致问题；而倒着遍历（从 j = W 到 0）则能正确解决问题。接下来我会详细解释为什么。

为什么需要倒着遍历？

在一维DP中，dp[j] 的更新依赖于 dp[j - w[i]]。如果遍历顺序不当，会导致当前物品被重复使用，而0-1背包要求每个物品只能用一次。我们通过一个例子来说明。

例子

假设：

背包容量 W = 5。
只有一个物品，重量 w[1] = 2，价值 v[1] = 3。
初始dp[j] = 0对于所有 j。

正向遍历（从 0 到 W）

j = 2：dp[2] = max(dp[2], dp[2-2] + 3) = max(0, dp[0] + 3) = max(0, 0 + 3) = 3。
j = 3：dp[3] = max(dp[3], dp[3-2] + 3) = max(0, dp[1] + 3) = max(0, 0 + 3) = 3。
j = 4：dp[4] = max(dp[4], dp[4-2] + 3) = max(0, dp[2] + 3) = max(0, 3 + 3) = 6。
问题：dp[4] = 6 表示价值达到 6，相当于拿了两次物品（2 × 3 = 6），但0-1背包不允许重复拿取！

原因：正向遍历时，dp[2] 被更新为 3 后，dp[4] 用到了更新后的 dp[2]，相当于当前物品被多次使用。

倒着遍历（从 W 到 0）

j = 5：dp[5] = max(dp[5], dp[5-2] + 3) = max(0, dp[3] + 3) = max(0, 0 + 3) = 3。
j = 4：dp[4] = max(dp[4], dp[4-2] + 3) = max(0, dp[2] + 3) = max(0, 0 + 3) = 3。
j = 3：dp[3] = max(dp[3], dp[3-2] + 3) = max(0, dp[1] + 3) = max(0, 0 + 3) = 3。
j = 2：dp[2] = max(dp[2], dp[2-2] + 3) = max(0, dp[0] + 3) = max(0, 0 + 3) = 3。
结果：dp[5] = 3，表示最多放入一个物品，符合0-1背包的规则。

原因：倒着遍历时，dp[j] 更新时用到的dp[j - w[i]]是还未被当前物品更新的值，相当于二维DP中的 dp[i-1][j - w[i]]。

一维DP的详细流程

初始化：
- dp[j] = 0 对于所有 j 从 0 到 W。
遍历物品
- 对于每个物品 i（从 1 到 n）：
  - 倒着遍历容量 j（从 W 到 w[i]）：
    - 如果 j >= w[i]，则 dp[j] = max(dp[j], dp[j - w[i]] + v[i])。
    - 如果 j < w[i]，跳过（实际上不需要显式处理，因为循环从 w[i] 开始）。
结果
- dp[W] 即为最终答案。

3.算法对比

算法	时间复杂度	稳定性
冒泡	O(n²)	稳定
插入	O(n²)	稳定
归并	O(nlogn); 需要 O(n) 额外空间	稳定
选择	O(n²)	不稳定
希尔	O(nlogn)	不稳定
堆排序	O(nlogn)	不稳定
快排	O(nlogn) ， O(n²) 最坏情况;	不稳定

常用算法系列