堆排序
基本介绍
堆排序是利用 堆 这种 数据结构 而设计的一种排序算法，它是一种选择排序，最坏 、最好、平均时间复杂度均为 O(nlogn)，它是不稳定排序。
堆是具有以下性质的完全二叉树：
-
大顶堆：每个节点的值都 大于或等于 其左右孩子节点的值
注：没有要求左右值的大小关系
-
小顶堆：每个节点的值都 小于或等于 其左右孩子节点的值
举例说明：
大顶堆举例
对堆中的节点按层进行编号，映射到数组中如下图
大顶堆特点：arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2]，i 对应第几个节点，i 从 0 开始编号
小顶堆举例
小顶堆特点：arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2]，i 对应第几个节点，i 从 0 开始
- 升序：一般采用大顶堆
- 降序：一般采用小顶堆
基本思想
-
将待排序序列构造成一个大顶堆
注意：这里使用的是数组，而不是一颗二叉树
-
此时：整个序列的 最大值就是堆顶的根节点
-
将其 与末尾元素进行交换，此时末尾就是最大值
-
然后将剩余
n-1个元素重新构造成一个堆，这样 就会得到 n 个元素的次小值。如此反复，便能的得到一个有序序列。
堆排序步骤图解
- 给定无序序列结构 如下：注意这里的操作用数组，树结构只是参考理解
将给定无序序列构造成一个大顶堆。
-
此时从最后一个非叶子节点开始调整，从左到右，从上到下进行调整。
叶节点不用调整，第一个非叶子节点
arr.length/2-1 = 5/2-1 = 1，也就是 元素为 6 的节点。 -
找到第二个非叶子节点 4，由于
[4,9,8]中，9 元素最大，则 4 和 9 进行交换 -
此时，交换导致了子根
[4,5,6]结构混乱，将其继续调整。[4,5,6]中 6 最大，将 4 与 6 进行调整。
此时，就将一个无序序列构造成了一个大顶堆。
5. 将堆顶元素与末尾元素进行交换，**使其末尾元素最大**。然后继续调整，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
1. 将堆顶元素 9 和末尾元素 4 进行交换
-
将堆顶元素 9 和末尾元素 4 进行交换
-
再将堆顶元素 8 与末尾元素 5 进行交换，得到第二大元素 8
-
再将堆顶元素 8 与末尾元素 5 进行交换，得到第二大元素 8
代码实现
//堆排序
public static void heapSort(int[] arr){
int temp;
//将无序列表构建成一个大顶推
for(int i = arr.length/2-1;i >= 0; i--){
adjustHeap(arr,i,arr.length);
}
for(int k = arr.length-1; k > 0; k--){
//交换
temp = arr[0];
arr[0] = arr[k];
arr[k] = temp;
adjustHeap(arr,0,k);
}
}
/**
* 将以i为节点的数调整成一个大顶堆
* @param arr 待调整的数组
* @param i 要调整的非叶子节点
* @param length 数组长度
*/
public static void adjustHeap(int[] arr,int i,int length){
int temp = arr[i];
for(int k = 2*i+1; k < length; k = 2*k+1){
if(k+1 < length && arr[k+1] > arr[k]){
//右子节点比左子节点大
k++;
}
//比较是否调整位置
if(arr[k] > temp){
arr[i] = arr[k];//交换位置
i = k;//重置i的位置
}else{
break;
}
}
arr[i] = temp;
}
性能测试
排序800万数据，平均时间在2秒左右
常用的十种算法
二分查找(非递归)
二分查找法只适用于从 有序 的数列中查找（比如数字和字母等），将数列 **排序后 **再进行查找。
二分查找法的运行时间为对数时间 O(log2n) ，即查找到目标位置最多只需要 log2n 步，假设从 0~99 的队列（100 个数，即 n = 100），中旬到目标数 30，则需要查找的步数为 log2100，即最多需要查找 7 次（26 < 100 < 27，100 介于 2 的 6、7 次方之间，次方则是寻找的步数）
代码实现
/**
* 二分查找非递归
* @param arr 有序数组
* @param target 查找的目标
* @return 返回找到到的索引，没有找到返回-1
*/
public static int binarySearch(int[] arr,int target){
int left = 0;
int right = arr.length-1;
while(left <= right){
int mid = (right + left) / 2;
if(arr[mid] == target){
return mid;
}else if(arr[mid] > target){
right = mid-1;
}else{
left = mid+1;
}
}
return -1;
}
分治算法
分治法 是一种很重要的算法。字面上的解释是 分而治之，把一个复杂的问题 分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题.... 直到最后子问题可以简单的直接求解，原问题的解即 子问题的解的合并。
这个技巧是很多高效算法的基础，比如 排序算法：快速排序、归并排序，傅里叶变换、快速傅里叶变换
分治算法可以 求解的一些经典问题 如：
- 二分搜索
- 大整数乘法
- 棋盘覆盖
- 快速排序
- 归并排序
- 线性时间选择
- 最接近点对问题
- 循环赛日程表
- 汉诺塔
刚刚看了下之前学过的快速排序和归并排序，他们不同也是难点在于如何把一个大问题 分解 成一个小问题进行 解决，然后再 合并 小问题的结果。
基本步骤
分治法在每一层递归上都有三个步骤：
- 分解：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题
- 解决：若子问题规模较小而容易被解决则直接解决，否则递归的解各个子问题
- 合并：将各个子问题的解合并为原问题的解
分治算法的设计模式
if |P| ≤ n0
then return (ADHOC(P))
// 将 P 分解为较小的子问题 P1,P2...Pk
for i ← to k
do yi ← Divide-and-Conquer(Pi) // 递归解决 pi
T ← MERGE(y1,y2,..yk) // 合并子问题
return(T)
-
|P|：表示问题 P 的规模 -
n0：为阀值，表示当问题 P 的规模不超过 n0 时，问题已容易直接解出，不必再继续分解 -
ADHOC(P)：该分治法中的基本子算法，用于直接解小规模的问题 P因此，当 P 的规模不超过 n0 时，直接用
ADHOC(P)求解。 -
MERGE(y1,y2,..yk)：该分治法中的合并子算法，用于将 P 的子问题 P1、P2...Pk 的相应的解 y1、y2...yk 合并为 P 的解
实践-汉诺塔
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
假如每秒钟一次，共需多长时间呢？移完这些金片需要 5845.54 亿年以上，太阳系的预期寿命据说也就是数百亿年。真的过了 5845.54 亿年，地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。
/**
* 分治算法解决汉诺塔
* @param num 要移动的盘子个数
* @param a A柱
* @param b B柱
* @param c C柱
*/
public static void dac(int num,char a,char b,char c){
if(num == 1){
System.out.println("将第1个盘从" + a + "移动到" + c);
}else{
//将除最后一个以外的上面所有的盘移动到B柱，借助C盘
dac(num-1,a,c,b);
//将最后一个从A柱移动到C柱
System.out.println("将第" + num + "个盘从" + a + "移动到" + c);
//将除最后一个以外的上面所有的盘移动到C柱借助A柱
dac(num-1,b,a,c);
}
}
验证结果正确性：https://zhangxiaoleiwk.gitee.io/h.html
动态规划算法
应用场景：背包问题
有一个背包，容量为 4 磅，现有物品如下：
| 物品 | 重量 | 价格 |
|---|---|---|
| 吉他(G) | 1 | 1500 |
| 音响(S) | 4 | 3000 |
| 电脑(L) | 3 | 2000 |
要求：
- 达到的目标为装入的背包的总价值最大，并且重量不超出
- 装入的物品不能重复
介绍
动态规划（Dynamic Programming） 算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
动态规划算法 与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即 下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
动态规划可以通过 填表的方式 来逐步推进，得到最优解.
思路和图解
背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。其中又分：
-
01 背包：放入物品不能重复
-
无限背包：放入物品可重复
无限背包可以转化成 01 背包。
想要解决一个问题，你首先得有思想，然后转化成公式或规律，最后转化成你的程序。
算法的主要思想：利用动态规划来解决。每次遍历到的第 i 个物品，根据 w[i] 和 v[i] 来确定是否需要将该物品放入背包中。即设：
-
n ： 给定了 n 个物品
-
w[i]：第 i 个商品的重量 -
val[i]：第 i 个商品的价值 -
c：为背包的容量 -
v[i][j]：表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值假设当前已经放了 i 个物品在背包中，那么当前背包的容量为 j，能够放进去的容量用
v[i][j]表示
则有下面的结果：
v[i][0] = v[0][j]=0- 当
w[i] > j时：v[i][j] = v[i - 1][j] - 当
j ≥ w[i]时：v[i][j] = max{v[i - 1][j] , v[i - 1][j - w[i]] + val[i]}
以上思路和公式，现在肯定看不懂，下面使用填表法来逐步推导出这个规律和公式。
给定的商品如下：
| 物品 | 重量 | 价格 |
|---|---|---|
| 吉他(G) | 1 | 1500 |
| 音响(S) | 4 | 3000 |
| 电脑(L) | 3 | 2000 |
初始表格为：
| 物品 | 0 磅 | 1 磅 | 2 磅 | 3 磅 | 4 磅 |
|---|---|---|---|---|---|
| 没有物品 | 0 | 0 | 0 | 0 | 0 |
| 吉他(G) | 0 | ||||
| 音响(S) | 0 | ||||
| 电脑(L) | 0 |
- 第 1 行：是没有任何物品：那么它在任何背包容量下，都是 0 磅
- 第 1 列：是当背包容量为 0 时，那么它是无法装入任何物品的，所以都是 0
- 现在假如只有吉他可以放：
| 物品 | 0 磅 | 1 磅 | 2 磅 | 3 磅 | 4 磅 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | |
| 吉他(G) | 0 | 1500（G） | 1500（G） | 1500（G） | 1500（G） |
| 音响(S) | 0 | ||||
| 电脑(L) | 0 |
现在只有一把吉他可以放，所以不管背包的容量有多大，它都只能放一把吉他进去（01 背包），所以 4 个容量都为 1500(G)
- 上面已经放了一把吉他，现在开始尝试放音响：
| 物品 | 0 磅 | 1 磅 | 2 磅 | 3 磅 | 4 磅 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | |
| 吉他(G) | 0 | 1500（G） | 1500（G） | 1500（G） | 1500（G） |
| 音响(S) | 0 | 1500（G） | 1500（G） | 1500（G） | 3000（S） |
| 电脑(L) | 0 |
-
当背包容量只有 1 磅时：音响重 4 磅，放不进去
那么从上一个单元格复制物品下来，也就是
1500(G)吉他 -
类似的：当背包只有 2、3 磅时，也是放不下音响的
那么从上一个单元格复制物品下来，也就是
1500(G)吉他 -
当背包容量有 4 磅时：可以放下音响了
需要考虑当前音响放进去的价值，是否大于上一个单元格（子问题的解依赖于上一个子问题的解）
这里是 3000 > 1500，那么此时 4 磅的格子中就放入了
3000(S)音响
- 现在开始尝试放电脑：
| 物品 | 0 磅 | 1 磅 | 2 磅 | 3 磅 | 4 磅 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | |
| 吉他(G) | 0 | 1500（G） | 1500（G） | 1500（G） | 1500（G） |
| 音响(S) | 0 | 1500（G） | 1500（G） | 1500（G） | 3000（S） |
| 电脑(L) | 0 | 1500（G） | 1500（G） | 2000（L） | 2000（L）+ 1500（G） |
-
当背包容量只有 1、2 磅时：电脑重量 3 磅，放不进去
那么从上一个单元格复制物品下来，也就是
1500(G)吉他 -
当背包容量只有 3 磅时：可以放下电脑了
需要考虑当前电脑放进去的价值，是否大于上一个单元格。
2000 > 1500，那么就放入
2000(L)电脑。 -
当背包容量只有 4 磅时：此时如果不考虑程序实现，人为填表的话
可以放
2000（L）+ 1500（G）的电脑和吉他
代码实现
//动态规划解决背包问题
public class KnapsackProblem {
public static void main(String[] args) {
int[] w = {1,4,3};//用于表示对应的商品重量，比如，第一个商品重量为1，第二个为4
int[] val = {1500,3000,2000};//用于表示对应商品的价值，比如第一个商品价值为1500
int M = 4;//表示背包的容量
int n = w.length;//商品的个数
int[][] v = new int[n+1][M+1];//用于v[i][j]表示在有i个商品种类的时候，背包容量为j时候最大的背包价值
int[][] path = new int[n+1][M+1];//记录放入商品的顺序
//当商品种类为0的时候，不管背包容量为多少，背包价值的都是0
for(int i = 0; i < v[0].length;i++){
v[0][i] = 0;
}
//当背包容量为0的时候，不管有几种商品，背包最大的价值都是0
for(int i = 0; i < v.length; i++){
v[i][0] = 0;
}
//开始动态规划
for(int i = 1; i <= n; i++){//i表示商品的种类，i=1,表示第一个商品
for(int j = 0; j < v[i].length; j++){//j表示背包的容量，j=0表示背包容量为0
if(w[i-1] > j){//当当前商品的重量大于当前背包的容量的时候，就参考上一次该容量的时候背包的价值
v[i][j] = v[i-1][j];
}else{
//当背包容量大于或者等于当前要添加商品容量的时候，将上一次该容量的最大价值和
//将当前商品放入后的价值和剩余空间还能放的最大价值之和比较，取两个值的最大值
if(v[i-1][j] < val[i-1] + v[i-1][j-w[i-1]]){
v[i][j] = val[i-1] + v[i-1][j-w[i-1]];
path[i][j] = 1;
}else{
v[i][j] = v[i-1][j];
}
}
}
}
System.out.println("动态规划计算出的各容量的背包的最大价值:");
//输出动态规划之和背包的价值表
for(int i = 0; i < v.length; i++){
for(int j = 0; j < v[i].length; j++){
System.out.printf("%4d\t",v[i][j]);
}
System.out.println();
}
//从最后一个商品最大容量开始逆向输出
int i = path.length-1;
int j = path[0].length-1;
while(i > 0 && j > 0){
if(path[i][j] == 1){
System.out.printf("第%d个商品放入背包\n",i);
j -= w[i-1];//放入当前商品后，剩余容量
}
i--;//下一个可以放入的商品
}
}
}