插入排序——Insertion Sort——O(n^2)
插入排序的核心就是把带排序元素逻辑分割成一个有序表和无序表，再逐一将无序表中的元素按规则一个个加入到有序表中的过程。
[图片上传失败...(image-f106c5-1636600948024)]
image.png
[图片上传失败...(image-b13c7-1636600948025)]
public class InsertSort {
public static void main(String[] args) {
int[] arr = {101, 34, 119, 1, -1, 89};
// 创建要给80000个的随机的数组
// int[] arr = new int[80000];
// for (int i = 0; i < 80000; i++) {
// arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
// }
System.out.println("插入排序前");
System.out.println(Arrays.toString(arr));
//
// Date data1 = new Date();
// SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
// String date1Str = simpleDateFormat.format(data1);
// System.out.println("排序前的时间是=" + date1Str);
insertSort(arr); //调用插入排序算法
// Date data2 = new Date();
// String date2Str = simpleDateFormat.format(data2);
// System.out.println("排序前的时间是=" + date2Str);
System.out.println(Arrays.toString(arr));
}
//插入排序
public static void insertSort(int[] arr) {
int insertVal = 0;
int insertIndex = 0;
//使用for循环来把代码简化
for(int i = 1; i < arr.length; i++) {
//定义待插入的数
insertVal = arr[i];
//假设待插入的位置是有序表的最后一位
insertIndex = i - 1; // 即arr[1]的前面这个数的下标
// 给insertVal 找到插入的位置
// 说明
// 1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界
// 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
// 3. 就需要将 arr[insertIndex] 后移
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
//把较大的值往后移到一位
arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
//继续比较
insertIndex--;
}
// 当退出while循环时，说明插入的位置找到, insertIndex + 1
//这里我们判断是否需要赋值
if(insertIndex + 1 != i) {
arr[insertIndex + 1] = insertVal;
}
}
}
/**
* 插入排序前
* [101, 34, 119, 1, -1, 89]
* 插入排序后
* [-1, 1, 34, 89, 101, 119]
*/
}
希尔排序——Shell Sort——缩小增量排序——O(n log n)
希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。（希尔排序是把记录按下标的一定增量分组，缩小的是分组的增量，数组增量最后缩小为一组，排序完成）
前提——简单插入排序存在的问题
当待排序数组中较小的值比较集中靠后时比较次数增多影响效率。
我们看简单的插入排序可能存在的问题.
数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
在我们进行简单的插入排序可能存在的问题是待排序的数组中，较小的元素集中在后面，这时候，当我们进行升序排序时，需要插入的数是较小的数时，后移的次数明显增多，对效率有影响。
基本思想
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
思路分析
希尔.png
希尔2.png
代码示例
希尔排序时， 对有序序列在插入时可以采用交换法或者移动法，正常使用移动法，速度才能上来，也才符合希尔排序的思想是插入排序的一种缩小增量排序的优化。
/**
* 排序前:
* [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
* 排序后:
* [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
* 十万条数据排序耗时18
*/
public class ShellSort {
public static void main(String[] args) {
int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0,0,0,0};
System.out.println("排序前:");
System.out.println(Arrays.toString(array));
shellSort(array);
System.out.println("排序后:");
System.out.println(Arrays.toString(array));
int[] arrayTest = new int[10_0000];
for (int i = 0; i < 10_0000; i++) {
arrayTest[i] = (int) (Math.random() * 10_00000);
}
long start = System.currentTimeMillis();
shellSort(arrayTest);
// shellSortBySwap(arrayTest);//十万条数据排序耗时13043
long end = System.currentTimeMillis();
System.out.println("十万条数据排序耗时"+(end-start));
}
/**
* 希尔排序——移动法
* @param array
*/
public static void shellSort(int[] array) {
//gap表示分为几组，5->2->1
for (int gap = array.length / 2; gap > 0; gap /= 2) {
//int i = gap = 10/2=5,就是从5开始，是因为我们做插入排序时，会将数组分为有序表和无序表，5组则有5组有序和无序表，插入排序时从被比较的字段开始
//5个组则待排序从5开始
//遍历各组中所有的元素，一共gap组，每组2^n个元素，n>=1,步长是gap
for (int i = gap; i < array.length; i++) {
//待插入位置下标
int index = i;
//temp记录待插入值
int temp = array[i];
//如果当前元素小于加上步长后的元素，说明需要进行前移
//注意这里要拿temp与array[index - gap]比较，再进行插入排序前移，如果拿array[index]，会因为赋值而导致变化，无法满足比较
while (index - gap >= 0 && temp < array[index - gap]) {
//index - gap的值后移，也就是往后移动gap位置
array[index] = array[index - gap];
//往前移动gap，继续比较，最后gap=1，也就是往前一个个比较，如果temp比之前的数小，就让
index -= gap;
}
//这里不会像插入排序那样导致越界的原因
array[index] = temp;
// }
}
}
}
/**
* 希尔排序——交换法
* @param array
*/
public static void shellSortBySwap(int[] array) {
int temp = 0;
for (int gap = array.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < array.length; i++) {
for (int j = i - gap; j >= 0; j -= gap) {
if (array[j] > array[j + gap]) {
temp = array[j];
array[j] = array[j + gap];
array[j + gap] = temp;
}
}
}
}
}
}
快速排序——Quick Sort——冒泡排序的改进——O(n log n)
快速排序（Quicksort）是对冒泡排序的一种改进。
快排是每次通过一个基准值讲数据分割成左小右大的两部分，然后再按此方法递归对这两部分数据分别进行快速排序。
基本思想
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
思路分析
快速2.png
代码示例
/**
* 排序前:
* [-9, 78, 0, 23, -567, 70]
* 排序后:
* [-567, -9, 0, 23, 70, 78]
* 十万条数据排序耗时21
*/
public class QuickSort {
public static void main(String[] args) {
int[] array = {-9, 78, 0, 23, -567, 70};
System.out.println("排序前:");
System.out.println(Arrays.toString(array));
quickSort(array,0,array.length-1);
System.out.println("排序后:");
System.out.println(Arrays.toString(array));
int[] arrayTest = new int[10_0000];
for (int i = 0; i < 10_0000; i++) {
arrayTest[i] = (int) (Math.random() * 10_00000);
}
long start = System.currentTimeMillis();
quickSort(arrayTest,0,arrayTest.length-1);
// shellSortBySwap(arrayTest);//十万条数据排序耗时13043
long end = System.currentTimeMillis();
System.out.println("十万条数据排序耗时"+(end-start));
}
public static void quickSort(int[] array, int left, int right) {
//左下标
int l = left;
//右下标
int r = right;
//中轴值
int pivot = array[(left + right) / 2];
//临时变量swap用
int temp = 0;
//让比中轴值小的在左边
while (l < r) {
//在pivot左边一直找，直到找到大于等于pivot值后退出，得到要交互的左边值位置
while (array[l] < pivot) {
l++;
}
//在pivot右边一直找，直到找到小于等于pivot值后退出，得到要交互的右边值位置
while (pivot < array[r]) {
r--;
}
//l>=r 左右两边值已按pivot左小右大区分
if (l >= r) {
break;
}
//把找到的左右值进行交互
temp = array[l];
array[l] = array[r];
array[r] = temp;
//交换完成后，发现array[l] == pivot值， r--,前移
if (array[l] == pivot) {
r--;
}
//交互完成后，发现array[r] == pivot值， l++,前移
if (array[r] == pivot) {
l++;
}
}
//l==r则表示已经遍历完了，避免栈溢出
if (l == r) {
l++;
r--;
}
//向左递归 r--一直往左边移动，直到r<=left,表示超出最左边的范围
if (left<r){
quickSort(array,left,r);
}
//向右递归 l++一直往右边移动
if (right>l){
quickSort(array,l,right);
}
}
}
快排是分治思想么？
归并排序——Merge Sort——分治策略——O(n log n)
合并操作次数= 数组长度-1次，即8个元素需要合并7次。合并操作是线性增长而不是像冒泡那样是O(n^2)这样是平方阶增长。
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治策略（divide-and-conquer）（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
分的过程中仅仅是把数据分开到每个栈中而已，并没有实际的处理，治的过程才是真正在做排序。
归并思想
说明:可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程。
归并.png
合并思路分析
归并2.png
归并3.png
代码示例
/**
* 排序前:
* [8, 4, 5, 7, 1, 3, 6, 2]
* 排序后:
* [1, 2, 3, 4, 5, 6, 7, 8]
* 十万条数据排序耗时18
*/
public class MergeSort {
public static void main(String[] args) {
int[] array = {8, 4, 5, 7, 1, 3, 6, 2};
int[] temp = new int[array.length];
System.out.println("排序前:");
System.out.println(Arrays.toString(array));
mergeSort(array, temp, 0, array.length - 1);
System.out.println("排序后:");
System.out.println(Arrays.toString(array));
int[] arrayTest = new int[10_0000];
int[] tempTest = new int[arrayTest.length];
for (int i = 0; i < 10_0000; i++) {
arrayTest[i] = (int) (Math.random() * 10_0000);
}
long start = System.currentTimeMillis();
//注意传入的数组的左右两端值 arrayTest.length - 1
mergeSort(arrayTest, tempTest, 0, arrayTest.length - 1);
long end = System.currentTimeMillis();
System.out.println("十万条数据排序耗时"+(end-start));
}
public static void mergeSort(int[] array, int[] temp, int left, int right) {
if (left < right) {
//中间索引
int mid = (left + right) / 2;
//向左递归分解
mergeSort(array, temp, left, mid);
//向右递归分解
mergeSort(array, temp, mid + 1, right);
//递归分解后对最后分解的最先合并起来
merge(array, temp, left, mid, right);
}
}
/**
* 合并
* @param array 原始数组
* @param temp 临时存放中转数据的数组
* @param left 分解后的左索引
* @param mid 中间索引
* @param right 分解后的右索引
*/
private static void merge(int[] array, int[] temp, int left, int mid, int right) {
//i,j,t是为了比较两个有序序列里元素的值而定义的数组下标
//i是左边有序序列的初始下标索引
int i = left;
//j是右边有序序列的初始下标索引
int j = mid + 1;
//temp数组的当前下标索引
int t = 0;
//1、将左右两边的有序序列的数据依次通过下标进行比较，把较小的填充到temp数组中，直到有一边有序序列已经处理完毕
while (i <= mid && j <= right) {
if (array[i] < array[j]) {
temp[t] = array[i];
t++;
i++;
} else {
temp[t] = array[j];
t++;
j++;
}
}
//2、这时候我们判断是哪边的有序序列还有剩余元素，把剩余的元素依次填充到temp数组中，因为他们已经是有序的了
while (i <= mid) {
temp[t] = array[i];
t++;
i++;
}
while (j <= right) {
temp[t] = array[j];
t++;
j++;
}
//3、把temp数组的元素拷贝到原始数组array中，只需要拷贝left->right长度的数据即可，不需要全部拷贝
//之所以要新建左端点的局部变量是因为我们要对其遍历++，所以要创建个新的值tempLeft处理好点
int tempLeft = left;
//从0开始获取temp数组元素
t = 0;
while (tempLeft <= right) {
array[tempLeft] = temp[t];
t++;
tempLeft++;
}
}
}
基数排序——Radix Sort——桶排序——包含负数元素不适应O(logR^B)
获取待排序数组中最大的元素，拿到其长度，有几位就遍历几次比较。定义一个0到9的二位数组数组作为
桶arr[10][array.length],遍历数组时根据比较其所在位数的大小放到不同的桶中，结束后从0到9遍历这个二维数组中的元素，重新赋值给原来的数组继续排序，直到最大位排序完成，这时候获得到的数组就是排序后的数组。
排序数组里有负数不适合处理。对负数要支持的话就是再安排10个桶专门用来存放负数。拿到负数时要对负数求绝对值，再放到对应负数的桶里，等取数的时候再取反处理。
- 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
- 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法。
- 基数排序(Radix Sort)是桶排序的扩展。
- 基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。
基数排序的说明
- 基数排序是对传统桶排序的扩展，速度很快.
- 基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError 。
- 基数排序时稳定的。[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的]
- 有负数的数组，我们不用基数排序来进行排序, 如果要支持负数，参考
基本思想
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
思路分析
基数.png
基数2.png
基数3.png
代码示例
/**
* 排序前:
* [833, 42, 5, 71, 1, 3, 6332, 28]
* 排序后:
* [1, 3, 5, 28, 42, 71, 833, 6332]
* 十万条数据排序耗时75(注意并不是开辟空间导致的耗时，而是桶排序的耗时比较大)
*/
public class RadixSort {
public static void main(String[] args) {
int[] array = {833, 42, 5, 71, 1, 3, 6332, 28};
System.out.println("排序前:");
System.out.println(Arrays.toString(array));
radixSort(array);
System.out.println("排序后:");
System.out.println(Arrays.toString(array));
int[] arrayTest = new int[10_0000];
for (int i = 0; i < 10_0000; i++) {
arrayTest[i] = (int) (Math.random() * 10_00000);
}
long start = System.currentTimeMillis();
radixSort(arrayTest);
// shellSortBySwap(arrayTest);//十万条数据排序耗时13043
long end = System.currentTimeMillis();
System.out.println("十万条数据排序耗时"+(end-start));
}
public static void radixSort(int[] array) {
//定义一个二维数组，表示10个桶，每个桶就是一个一维数组，每个一维数组大小为array.length，避免最坏情况数组溢出
//基数排序就是典型的空间换时间的算法
int[][] bucket = new int[10][array.length];
//记录每个桶中，实际存放了多少个数据，定义的一维数组下标对应每一个桶，值为数据个数
int[] bucketElementSize = new int[10];
//获取数组中最大的数
int maxNumber = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > maxNumber) {
maxNumber = array[i];
}
}
//最大数字是几位数
int maxSize = String.valueOf(maxNumber).length();
int number = 0;
//针对每个元素对应的个十百千万位分别进行处理
for (int i = 0; i < maxSize; i++) {
for (int j = 0; j < array.length; j++) {
number = array[j] / (int) Math.pow(10, i) % 10;
bucket[number][bucketElementSize[number]] = array[j];
bucketElementSize[number] += 1;
}
//定义数组目前存放位置下标，从0到array.length
int index = 0;
//遍历每个桶，取出桶中的数据到原数组中
for (int m = 0; m < bucket.length; m++) {
//判断桶中有数据才进去遍历桶
if (bucketElementSize[m] > 0) {
for (int n = 0; n < bucketElementSize[m]; n++) {
//依次取出桶中元素到原数组，原数组下标index++后移一位
array[index++] = bucket[m][n];
}
//每轮遍历桶后都要对size置0，避免下一轮加入桶时size不等于0出错
bucketElementSize[m] =0;
}
}
}
}
}
扩展：关于排序的稳定性
稳定性和不稳定性的定义
通俗地讲就是能保证排序前两个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。
稳定排序： 冒泡排序、插入排序、归并排序、基数排序
不稳定的排序: 选择排序、快速排序、希尔排序、堆排序
稳定排序可以利用上一次的排序结果（上一次考试B同学比C同学分数高）来服务于这次的排序。这就是它的应用场景。
常用排序算法总结和对比
冒泡、选择、插入时间复杂度一般是O(n^2)；
而希尔、归并、快速、堆排序的插入时间复杂度一般是O(n log n):线性对数阶；
而基数排序是O(n* k)，因为k是桶的个数，因此，当排序数据较小时可以用基本的冒泡、选择、插入，而数据量上来后最后便是使用希尔、归并、快速、堆排序，但是当log n > k也就是桶的个数时，这时候应该选择基数排序，也就是说当数据量更加海量时选择基数排序。
排序对比.png
查找算法
常用查找算法
- 顺序(线性)查找
- 二分查找/折半查找
- 插值查找
- 斐波那契查找
线性查找
前提：数组不需要有序
对数组进行从头到尾完全遍历一遍查找。
代码示例
public class SequenceSearch {
public static void main(String[] args) {
int[] array = {833, 42, 5, 71, 1, 3, 6332, 28};
int index = sequenceSearch(array, 3);
if (index != -1) {
System.out.println("找到了对应的数组下标为："+index);
} else {
System.out.println("数组中找不到对应的元素");
}
//找到了对应的数组下标为：5
}
/**
* 顺序查找，返回第一个找到值的数组下标
* 如果要把所有下标都找出来则继续比对，并把找到的下标存放在集合中即可
* @param arr 数组
* @param value 查找值
* @return
*/
public static int sequenceSearch(int[] arr, int value) {
for (int i = 0; i < arr.length; i++) {
if (arr[i]== value) {
return i;
}
}
return -1;
}
}
二分查找
前提：数组有序
思路分析
二分查找.png
代码示例——包含二分查找找出所有符合条件的下标集合
//使用二分查找的前提是该数组是有序的，如果无序则要先进行排序处理
/**
* 找到了对应的数组下标为：12
* [11,10,9,12,13,14,15,16]
*/
public class BinarySearch {
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5, 6, 7,8, 9, 10, 10, 10, 10, 10 ,10, 10, 10,};
//注意右索引为array.length - 1
int index = binarySearch(array, 0, array.length - 1, 10);
if (index != -1) {
System.out.println("找到了对应的数组下标为：" + index);
} else {
System.out.println("数组中找不到对应的元素");
}
//查找所有符合条件的下标
List<Integer> list = binarySearchList(array, 0, array.length - 1, 10);
System.out.println(JSON.toJSONString(list));
}
/**
* 二分法查找，找到返回数组下标，找不到返回-1
*
* @param arr 数组
* @param left 左索引
* @param right 右索引
* @param value 要查找的值
* @return
*/
public static int binarySearch(int[] arr, int left, int right, int value) {
if (left > right) {
return -1;
}
// if (left < right) {
int mid = (left + right) / 2;
//要找的值比中间值大，向右递归
if (value > arr[mid]) {
//注意向右查找时mid下标对应的值不需要比对了，之间在mid + 1到right范围内查找，如果不加1则可能会导致栈溢出，
// 因为我们的判断条件是left < right,而此时因为找不到对应的值，得到的mid值会一直等于左索引或者右索引的一边，而mid一直没有变化，就会发生死归
return binarySearch(arr, mid + 1, right, value);
//要找的值比中间值小，向左递归
} else if (value < arr[mid]) {
return binarySearch(arr, left, mid - 1, value);
} else {
return mid;
}
// } else {
// return -1;
// }
}
/**
* 二分法查找
* 当一个有序数组中，有多个相同的数值时，如何将所有的数值都查找到，比如这里的 10.
* 思路：因为数组是有序的，当找到了要找的值时，以该值下标向左向右寻找是否还有相同的值即可
*
* @param arr 数组
* @param left 左索引
* @param right 右索引
* @param value 要查找的值
* @return
*/
public static List<Integer> binarySearchList(int[] arr, int left, int right, int value) {
if (left > right) {
return new ArrayList<>();
}
int mid = (left + right) / 2;
//要找的值比中间值大，向右递归
if (value > arr[mid]) {
//注意向右查找时mid下标对应的值不需要比对了，之间在mid + 1到right范围内查找，如果不加1则可能会导致栈溢出，
// 因为我们的判断条件是left < right,而此时因为找不到对应的值，得到的mid值会一直等于左索引或者右索引的一边，而mid一直没有变化，就会发生死归
return binarySearchList(arr, mid + 1, right, value);
//要找的值比中间值小，向左递归
} else if (value < arr[mid]) {
return binarySearchList(arr, left, mid - 1, value);
} else {
List<Integer> list = new ArrayList<>();
//注意 :这里不能用mid--给局部变量赋值，否则会导致mid也发生了变化
int tempIndex = mid - 1;
//向左查找
while (tempIndex >= 0 && arr[tempIndex] == value) {
list.add(tempIndex);
tempIndex--;
}
//添加mid
list.add(mid);
//向右查找
tempIndex = mid + 1;
//注意脚本不能越级的情况下判断是否相等，注意arr.length - 1是存在的，所有要用等于号
while (tempIndex <= arr.length - 1 && arr[tempIndex] == value) {
list.add(tempIndex);
tempIndex++;
}
return list;
}
}
}
插值查找
前提：数组有序
原理
插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right.key 就是前面我们讲的 findVal。
int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low])
公式的意义：所预测的数字的位置占数组总长度的比例，可以理解为要寻找的值key到low的距离占整个区间的距离，值小靠左，值大靠右。
插值.png
注意：这个要求数据尽量均匀分布。插值类似于平常查英文字典的方法，在查一个以字母C开头的英文单词时，决不会用二分查找，从字典的中间一页开始，因为知道它的大概位置是在字典的较前面的部分，因此可以从前面的某处查起，这就是插值查找的基本思想。
插值查找除要求查找表是顺序存储的有序表外，还要求数据元素的关键字在查找表中均匀分布，这样，就可以按比例插值。
思路分析
插值2.png
代码示例
插值查找注意事项
- 对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快.
- 关键字分布不均匀的情况下，该方法不一定比折半查找要好.
/**
* 测试插值次数
* 找到了对应的数组下标为：46
*/
public class InterpolationSearch {
public static void main(String[] args) {
int[] arr = new int[100];
//创建0到100的均匀有序数组
for (int i = 0; i < 100; i++) {
arr[i] = i + 1;
}
int index = interpolationSearch(arr, 0, arr.length - 1, 47);
if (index != -1) {
System.out.println("找到了对应的数组下标为：" + index);
} else {
System.out.println("数组中找不到对应的元素");
}
}
/**
* 前提是有序数组
* 插值查找，适合数据尽量均匀分布的有序数组
*
* @param arr 数组
* @param left 左索引
* @param right 右索引
* @param value 要查找的值
* @return 找到返回数组下标，找不到返回-1
*/
public static int interpolationSearch(int[] arr, int left, int right, int value) {
// 测试插值次数
System.out.println("测试插值次数");
//如果不在最初对要查找的值进行最大最小的比较排除，则因为要查找的值是会进公式计算出mid的，
// 计算结果会因为value值而无线膨胀或者缩小导致mid值失去意义，且会造成mid角标越级异常
//Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 108 ：这是用109测试时的结果
//value < arr[0] || value > arr[arr.length - 1] 必须需要
if (left > right || value < arr[0] || value > arr[arr.length - 1]) {
return -1;
}
int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);
//要找的值比中间值大，向右递归
if (value > arr[mid]) {
return interpolationSearch(arr, mid + 1, right, value);
//要找的值比中间值小，向左递归
} else if (value < arr[mid]) {
return interpolationSearch(arr, left, mid - 1, value);
} else {
return mid;
}
}
}
斐波那契查找——黄金分割法查找
基本介绍
黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这是一个神奇的数字，会带来意向不大的效果。
斐波那契数列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55 } 发现斐波那契数列的两个相邻数的比例，无限接近 黄金分割值0.618。
/**
* 斐波那契数列:返回第几位斐波那契数列的值
*
* @param number 第几位斐波那契数列
* @return
*/
public static long fibonacci(long number) {
if ((number == 0) || (number == 1)) {
return number;
} else {
return fibonacci(number - 1) + fibonacci(number - 2);
}
}
思路分析
斐波那契.png
代码示例
//找到了对应的数组下标为：5
public class FibonacciSearch {
private static int maxSize = 20;
public static void main(String[] args) {
int[] array = {1, 8, 10, 89, 1000, 1234};
int index = fibonacciSearch(array, 1234);
if (index != -1) {
System.out.println("找到了对应的数组下标为：" + index);
} else {
System.out.println("数组中找不到对应的元素");
}
}
/**
* 斐波那契查找
*
* @param arr 数组
* @param value 查找值
* @return 返回数组下标，找不到返回-1
*/
public static int fibonacciSearch(int[] arr, int value) {
//因为mid = low + f[k - 1] - 1;所以要创建一个斐波那契数列返回第几位下斐波那契的值
//获取斐波那契数组
int[] f = createFibonacci();
//表示斐波那契分割数值对应的数组对应的下标
int k = 0;
int low = 0;
int high = arr.length - 1;
int mid = 0;
//这是其实是为了把查询数组分割成一个长度为8的线段，然后按照斐波那契的规律进行获取黄金分割点进行查找，
// 1,1,2,3,5,8从后往前就是各个位置的黄金分割点
//获取斐波那契数值对应的数组下标，这里的k=5,f[k]=8,因为我们的数组有6个数，所以斐波那契值刚好大于等于他的是8,
while (high > f[k] - 1) {
k++;
}
//将原查找表扩展为长度为F[n](如果要补充元素，则补充重复最后一个元素，直到满足F[n]个元素)
//补充最后一个元素是因为我们的数组是有序的，不能补充0，否则在比较是会出问题，补充最后一个元素刚好
//保证数组有序
int[] tempArr = Arrays.copyOf(arr, f[k]);
for (int j = high + 1; j < tempArr.length; j++) {
tempArr[j] = arr[high];
}
//low <= high 则可以继续寻找
while (low <= high) {
mid = low + f[k - 1] - 1;
//
if (value > tempArr[mid]) {
// k -= 2是因为 f[k]=f[k-1]+f[k-2],向右边则是查找f[k-2],则k-2
//这时候f[k-2] =f[k-3]+f[k-4]
k -= 2;
//向右查找则最低点变成mid + 1;
low = mid + 1;
//向数组的左边查找，把高位改为mid - 1
} else if (value < tempArr[mid]) {
// k -= 1是因为 f[k]=f[k-1]+f[k-2],向左边查找也就是查找f[k-1]，则k-1;向右边则是查找f[k-2],则k-2
//这时候f[k-1] =f[k-2]+f[k-3]
k -= 1;
//向左查找则最高点变成mid -1;
high = mid - 1;
} else {
if (mid >= arr.length) {
return high;
} else {
return mid;
}
}
}
return -1;
}
//非递归方式斐波那契数组
private static int[] createFibonacci() {
int[] f = new int[maxSize];
f[0] = 1;
f[1] = 1;
for (int i = 2; i < f.length; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f;
}
private static int[] createFibonacci(int k) {
int[] f = new int[k];
f[0] = 1;
f[1] = 1;
for (int i = 2; i < f.length; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f;
}
/**
* 斐波那契数列:返回第几位斐波那契数列的值
*
* @param number 第几位斐波那契数列
* @return
*/
public static long fibonacci(long number) {
if ((number == 0) || (number == 1)) {
return number;
} else {
return fibonacci(number - 1) + fibonacci(number - 2);
}
}
}
哈希表——Hashtable——散列表
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希表.png
哈希表的结构示意图——数组+链表的结构（JDK1.8是数组+链表+红黑树）
哈希表2.png
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
代码示例
google公司的一个上机题:
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,名字,住址..),当输入该员工的id时,要求查找到该员工的所有信息.
要求:
不使用数据库,,速度越快越好=>哈希表(散列)
添加时，保证按照id从低到高插入 [课后思考：如果id不是从低到高插入，但要求各条链表仍是从低到高，怎么解决?]
使用链表来实现哈希表, 该链表不带表头[即: 链表的第一个结点就存放雇员信息]
思路分析并画出示意图
代码实现[增删改查(显示所有员工，按id查询)]
public class HashTable<E> {
private SingleLinkedList<E>[] singleLinkedListArr;
private int size;
public HashTable(int size) {
this.size = size;
this.singleLinkedListArr = new SingleLinkedList[size];
for (int i = 0; i < this.singleLinkedListArr.length; i++) {
singleLinkedListArr[i] = new SingleLinkedList();
}
}
public void add(E e) {
singleLinkedListArr[hash(e)].add(e);
}
public void list() {
for (int i = 0; i < singleLinkedListArr.length; i++) {
if (singleLinkedListArr[i].getSize() > 0) {
singleLinkedListArr[i].list();
}
}
}
public E findById(int id) {
return singleLinkedListArr[id%size].findById(id);
}
private int hash(E e) {
if (e instanceof Employee) {
Employee employee = (Employee) e;
return employee.getId() % size;
} else {
return e.hashCode() % size;
}
}
}
public class SingleLinkedList<E> {
//head指向第一个元素，没有专门的head头结点
private Node<E> head;
private int size;
public int getSize() {
return size;
}
public void add(E e) {
if (head == null) {
head = new Node<E>(e);
size++;
} else {
Node<E> temp = head;
while (temp.next != null) {
temp = temp.next;
}
Node<E> node = new Node<E>(e);
temp.next = node;
size++;
}
}
public void list() {
if (head == null) {
return;
} else {
Node<E> temp = head;
while (temp != null) {
System.out.printf("%s\t", temp.getE());
temp = temp.next;
}
System.out.println();
}
}
public E findById(int id) {
boolean flag = false;
Node<E> temp = this.head;
while (temp != null) {
if (temp.getE() instanceof Employee) {
Employee employee = (Employee) temp.getE();
if (employee.getId() == id) {
flag = true;
break;
}
}
temp = temp.next;
}
if (flag) {
return temp.getE();
}
return null;
}
public void delete(E e) {
if (head == null) {
return;
} else {
boolean flag = false;
Node<E> temp = head.next;
while (temp.next != null) {
if (temp.next.getE().equals(e)) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.next = temp.next.next;
}
}
}
private static class Node<E> {
private E e;
private Node<E> next;
public E getE() {
return e;
}
public Node<E> getNext() {
return next;
}
public Node(E e) {
this.e = e;
}
@Override
public String toString() {
return "Node{" +
"e=" + e +
'}';
}
}
}
public class Employee {
private Integer id;
private String name;
public Employee() {
}
public Employee(Integer id,String name){
this.id = id;
this.name =name;
}
public Integer getId() {
return id;
}
public void setId(Integer id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "Employee{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
public class HashTableTest {
public static void main(String[] args) {
HashTable<Employee> hashTable = new HashTable<Employee>(10);
hashTable.add(new Employee(1,"小强"));
hashTable.add(new Employee(2,"艾米"));
hashTable.add(new Employee(12,"艾米"));
hashTable.list();
System.out.printf("查找%d的元素的值%s",12,hashTable.findById(12));
System.out.println();
System.out.printf("查找%d的元素的值%s",13,hashTable.findById(13));
}
/**
* Employee{id=1, name='小强'}
* Employee{id=2, name='艾米'} Employee{id=12, name='艾米'}
* 查找12的元素的值Employee{id=12, name='艾米'}
* 查找13的元素的值null
*/
}
扩展：有了一级缓存，为什么还要二级缓存？
一级缓存不够就可以再加一级缓存，变成二级缓存。二级缓存的作用又是什么呢？简单地说，二级缓存就是一级缓存的缓冲器：一级缓存制造成本很高因此它的容量有限，二级缓存的作用就是存储那些CPU处理时需要用到、一级缓存又无法存储的数据。同样道理，三级缓存和内存可以看作是二级缓存的缓冲器，它们的容量递增，但单位制造成本却递减。需要注意的是，无论是二级缓存、三级缓存还是内存都不能存储处理器操作的原始指令，这些指令只能存储在CPU的一级指令缓存中，而余下的二级缓存、三级缓存和内存仅用于存储CPU所需数据。
缓存.png
树
为什么需要树这种数据结构
- 数组存储方式的分析——查找快，增删慢
优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。
缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低 。
arraylist.png
- 链式存储方式的分析——查找慢，增删快
优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可， 删除效率也很好)。
缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)
链表.png
- 树存储方式的分析——查找增删都相对较快
能提高数据存储，读取的效率, 比如利用二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。
二叉排序树.png
扩展
ArrayList底层扩容说明
arraylist2.png
树的常用术语
树.png
二叉树简介
树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
二叉树的子节点分为左节点和右节点。
只有左节点或者只有右节点也是一个二叉树。
二叉树.png
满二叉树和完全二叉树
满二叉树节点总数=2^n -1,满二叉树是特殊的完全二叉树。
满二叉树.png
二叉树的遍历
二叉树的遍历有前序、中序、后续遍历三种方式。
前序遍历: 先输出父节点，再遍历左子树和右子树
中序遍历: 先遍历左子树，再输出父节点，再遍历右子树
后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点
小结: 看输出父节点的顺序，就确定是前序，中序还是后序
前序遍历—— Preorder Traversal
前序遍历（VLR）， 是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。
中序遍历——Inorder Traversal
中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。
后序遍历——Postorder Traversal
后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。
树的遍历思路分析
二叉树遍历.png
代码示例——前序、中序、后续遍历
public class BinaryTree<E> {
private TreeNode<E> root;
//前序
public void preOrder(){
if (this.root != null) {
this.root.preOrder();
}
}
//中序
public void inOrder(){
if (this.root != null) {
this.root.inOrder();
}
}
//后序
public void postOrder(){
if (this.root != null) {
this.root.postOrder();
}
}
public BinaryTree(TreeNode<E> root) {
this.root = root;
}
public TreeNode<E> getRoot() {
return root;
}
public void setRoot(TreeNode<E> root) {
this.root = root;
}
public static class TreeNode<E> {
private E item;
private TreeNode<E> left;
private TreeNode<E> right;
public TreeNode(E item) {
this.item = item;
}
/**
* 前序遍历
*/
public void preOrder() {
System.out.println(this.getItem());
//递归向左子树前序遍历
if (this.getLeft() != null) {
this.getLeft().preOrder();
}
//递归向右子树前序遍历
if (this.getRight() != null) {
this.getRight().preOrder();
}
}
/**
* 中序遍历
*/
public void inOrder() {
//递归向左子树中序遍历
if (this.getLeft() != null) {
this.getLeft().inOrder();
}
System.out.println(this.getItem());
//递归向右子树中序遍历
if (this.getRight() != null) {
this.getRight().inOrder();
}
}
public void postOrder() {
//递归向左子树后序遍历
if (this.getLeft() != null) {
this.getLeft().postOrder();
}
//递归向右子树后序遍历
if (this.getRight() != null) {
this.getRight().postOrder();
}
System.out.println(this.getItem());
}
public E getItem() {
return item;
}
public void setItem(E item) {
this.item = item;
}
public TreeNode<E> getLeft() {
return left;
}
public void setLeft(TreeNode<E> left) {
this.left = left;
}
public TreeNode<E> getRight() {
return right;
}
public void setRight(TreeNode<E> right) {
this.right = right;
}
}
}
public class Hero {
private Integer id;
private String name;
public Hero(Integer id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "Hero{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
/**
* --------------前序------------------
* Hero{id=1, name='艾米哈珀'}
* Hero{id=2, name='大青山'}
* Hero{id=3, name='霍恩斯'}
* Hero{id=5, name='绿儿'}
* Hero{id=4, name='池傲天'}
* --------------中序------------------
* Hero{id=2, name='大青山'}
* Hero{id=1, name='艾米哈珀'}
* Hero{id=5, name='绿儿'}
* Hero{id=3, name='霍恩斯'}
* Hero{id=4, name='池傲天'}
* --------------后序------------------
* Hero{id=2, name='大青山'}
* Hero{id=5, name='绿儿'}
* Hero{id=4, name='池傲天'}
* Hero{id=3, name='霍恩斯'}
* Hero{id=1, name='艾米哈珀'}
*/
public class BinaryTreeTest {
public static void main(String[] args) {
BinaryTree tree = createBinaryTree();
System.out.println("--------------前序------------------");
tree.preOrder();
System.out.println("--------------中序------------------");
tree.inOrder();
System.out.println("--------------后序------------------");
tree.postOrder();
}
public static BinaryTree createBinaryTree(){
BinaryTree.TreeNode<Hero> root = new BinaryTree.TreeNode<>(new Hero(1, "艾米哈珀"));
BinaryTree.TreeNode<Hero> node2 = new BinaryTree.TreeNode<>(new Hero(2, "大青山"));
BinaryTree.TreeNode<Hero> node3 = new BinaryTree.TreeNode<>(new Hero(3, "霍恩斯"));
BinaryTree.TreeNode<Hero> node4 = new BinaryTree.TreeNode<>(new Hero(4, "池傲天"));
BinaryTree.TreeNode<Hero> node5 = new BinaryTree.TreeNode<>(new Hero(5, "绿儿"));
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
node3.setLeft(node5);
BinaryTree<Hero> tree = new BinaryTree<>(root);
tree.setRoot(root);
return tree;
}
}
二叉树查找——通过前序、中序、后序查找
思路分析
二叉树查找.png
二叉树删除
删除要通过判断当前节点的子节点是否为要删除的对象来进行删除，，因为树的当前节点没有保存父节点的信息，是单向的，跟单向链表要找被删除节点的前一个节点一样。
思路分析
二叉树删除.png
二叉树查找和删除代码示例
public class BinaryTree {
private HeroNode root;
public BinaryTree(HeroNode root) {
this.root = root;
}
public HeroNode getRoot() {
return root;
}
public void setRoot(HeroNode root) {
this.root = root;
}
/**
* 二叉树删除
* 如果删除的节点是叶子节点，则删除该节点
* 如果删除的节点是非叶子节点，则删除该子树
* @param id
*/
public void delete(Integer id) {
//先判断节点是否为空
if (root == null) {
System.out.println("根节点为空，无法删除");
return;
}
//第一步先判断根节点是否为要删除的节点
if (Objects.equals(root.getId(),id)) {
this.setRoot(null);
return;
}
//递归判断删除
this.root.deleteNode(id);
}
//前序
public void preOrder() {
if (this.root != null) {
this.root.preOrder();
}
}
//中序
public void inOrder() {
if (this.root != null) {
this.root.inOrder();
}
}
//后序
public void postOrder() {
if (this.root != null) {
this.root.postOrder();
}
}
//前序
public HeroNode preOrderSearch(Integer id) {
if (this.root != null) {
return this.root.preOrderSearch(id);
}
return null;
}
//中序
public HeroNode inOrderSearch(Integer id) {
if (this.root != null) {
return this.root.inOrderSearch(id);
}
return null;
}
//后序
public HeroNode postOrderSearch(Integer id) {
if (this.root != null) {
return root.postOrderSearch(id);
}
return null;
}
public static class HeroNode {
private Integer id;
private String name;
private HeroNode left;
private HeroNode right;
public HeroNode(Integer id, String name) {
this.id = id;
this.name = name;
}
public Integer getId() {
return id;
}
public void setId(Integer id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public HeroNode getLeft() {
return left;
}
public void setLeft(HeroNode left) {
this.left = left;
}
public HeroNode getRight() {
return right;
}
public void setRight(HeroNode right) {
this.right = right;
}
/**
* 递归删除节点
* 删除要通过判断当前节点的子节点是否为要删除的对象来进行删除，
* 因为树的当前节点没有保存父节点的信息，是单向的，跟单向链表要找被删除节点的前一个节点一样。
*/
public void deleteNode(Integer id) {
//这边是按照一直往左比较递归的思路写的，如果要按照树的结构来进行删除的话
//就要在判断左节点不相等后判断右节点是否相等，只有两个都不相等时，
//才能向左递归删除，再向右递归删除
if (this.left != null) {
if (Objects.equals(this.left.id,id)) {
this.left = null;
return;
} else {
this.left.deleteNode(id);
}
}
if (this.right != null) {
if (Objects.equals(this.right.id,id)) {
this.right = null;
return;
} else {
this.right.deleteNode(id);
}
}
}
/**
* 前序查找
*/
public HeroNode preOrderSearch(Integer id) {
if (Objects.equals(this.id, id)) {
return this;
}
HeroNode node = null;
if (this.left != null) {
node = this.left.preOrderSearch(id);
}
if (node == null && this.right != null) {
node = this.right.preOrderSearch(id);
}
return node;
}
/**
* 中序查找
*/
public HeroNode inOrderSearch(Integer id) {
HeroNode node = null;
if (this.left != null) {
node = this.left.inOrderSearch(id);
}
if (node == null && Objects.equals(this.id, id)) {
return this;
}
if (node == null && this.right != null) {
node = this.right.inOrderSearch(id);
}
return node;
}
/**
* 后序查找
*/
public HeroNode postOrderSearch(Integer id) {
HeroNode node = null;
if (this.left != null) {
node = this.left.postOrderSearch(id);
}
if (node == null && this.right != null) {
node = this.right.postOrderSearch(id);
}
if (node == null && Objects.equals(this.id, id)) {
node = this;
}
return node;
}
/**
* 前序遍历
*/
public void preOrder() {
System.out.println(this);
//递归向左子树前序遍历
if (this.getLeft() != null) {
this.getLeft().preOrder();
}
//递归向右子树前序遍历
if (this.getRight() != null) {
this.getRight().preOrder();
}
}
/**
* 中序遍历
*/
public void inOrder() {
//递归向左子树中序遍历
if (this.getLeft() != null) {
this.getLeft().inOrder();
}
System.out.println(this);
//递归向右子树中序遍历
if (this.getRight() != null) {
this.getRight().inOrder();
}
}
public void postOrder() {
//递归向左子树后序遍历
if (this.getLeft() != null) {
this.getLeft().postOrder();
}
//递归向右子树后序遍历
if (this.getRight() != null) {
this.getRight().postOrder();
}
System.out.println(this);
}
@Override
public String toString() {
return "HeroNode{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
}
/**
* --------------前序------------------
* HeroNode{id=1, name='艾米哈珀'}
* HeroNode{id=2, name='大青山'}
* HeroNode{id=3, name='霍恩斯'}
* HeroNode{id=5, name='绿儿'}
* HeroNode{id=4, name='池傲天'}
* --------------中序------------------
* HeroNode{id=2, name='大青山'}
* HeroNode{id=1, name='艾米哈珀'}
* HeroNode{id=5, name='绿儿'}
* HeroNode{id=3, name='霍恩斯'}
* HeroNode{id=4, name='池傲天'}
* --------------后序------------------
* HeroNode{id=2, name='大青山'}
* HeroNode{id=5, name='绿儿'}
* HeroNode{id=4, name='池傲天'}
* HeroNode{id=3, name='霍恩斯'}
* HeroNode{id=1, name='艾米哈珀'}
* --------------前序查找------------------
* 前序查找:HeroNode{id=5, name='绿儿'}
* --------------中序查找------------------
* 中序查找:HeroNode{id=5, name='绿儿'}
* --------------后序查找------------------
* 后序查找:HeroNode{id=5, name='绿儿'}
* 后序查找:null
* --------------删除节点5------------------
* --------------删除后前序遍历------------------
* HeroNode{id=1, name='艾米哈珀'}
* HeroNode{id=2, name='大青山'}
* HeroNode{id=3, name='霍恩斯'}
* HeroNode{id=4, name='池傲天'}
*
* Process finished with exit code 0
*/
public class BinaryTreeTest {
public static void main(String[] args) {
BinaryTree tree = createBinaryTree();
System.out.println("--------------前序------------------");
tree.preOrder();
System.out.println("--------------中序------------------");
tree.inOrder();
System.out.println("--------------后序------------------");
tree.postOrder();
System.out.println("--------------前序查找------------------");
System.out.println("前序查找:" + tree.preOrderSearch(5));
System.out.println("--------------中序查找------------------");
System.out.println("中序查找:" + tree.inOrderSearch(5));
System.out.println("--------------后序查找------------------");
System.out.println("后序查找:" + tree.postOrderSearch(5));
System.out.println("后序查找:"+tree.postOrderSearch(20));
System.out.println("--------------删除节点5------------------");
tree.delete(5);
System.out.println("--------------删除后前序遍历------------------");
tree.preOrder();
}
public static BinaryTree createBinaryTree() {
BinaryTree.HeroNode root = new BinaryTree.HeroNode(1, "艾米哈珀");
BinaryTree.HeroNode node2 = new BinaryTree.HeroNode(2, "大青山");
BinaryTree.HeroNode node3 = new BinaryTree.HeroNode(3, "霍恩斯");
BinaryTree.HeroNode node4 = new BinaryTree.HeroNode(4, "池傲天");
BinaryTree.HeroNode node5 = new BinaryTree.HeroNode(5, "绿儿");
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
node3.setLeft(node5);
BinaryTree tree = new BinaryTree(root);
tree.setRoot(root);
return tree;
}
}
顺序存储二叉树
基本概念
从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组。
顺序存储二叉树.png
特点
- 顺序二叉树通常只考虑完全二叉树。
- 第n个元素的左子节点为 2 * n + 1 。
- 第n个元素的右子节点为 2 * n + 2。
- 第n个元素的父节点为 (n-1) / 2。
注意 ： n表示二叉树中的第几个元素(按0开始编号如上图所示)
代码示例——顺序存储二叉树遍历
/**
* 顺序存储二叉树前序遍历
* 1 2 4 5 3 6 7
* 顺序存储二叉树中序遍历
* 4 2 5 1 6 3 7
* 顺序存储二叉树后序遍历
* 4 5 2 6 7 3 1
*/
public class ArrayBinaryTree {
public static void main(String[] args) {
//给你一个数组 {1,2,3,4,5,6,7}，要求以二叉树前中后序遍历的方式进行遍历。
int[] array = {1, 2, 3, 4, 5, 6, 7};
ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(array);
System.out.println("顺序存储二叉树前序遍历");
arrayBinaryTree.preOrder();
System.out.println("\n顺序存储二叉树中序遍历");
arrayBinaryTree.inOrder();
System.out.println("\n顺序存储二叉树后序遍历");
arrayBinaryTree.postOrder();
}
private int[] array;
public ArrayBinaryTree(int[] array) {
this.array = array;
}
//重载方法，不对外暴露传递的参数，避免参数随意传递
public void preOrder() {
preOrder(0);
}
//顺序存储二叉树数组前序遍历
private void preOrder(int index) {
if (array == null || array.length == 0) {
System.out.print("顺序存储二叉树数组为空！\t");
return;
}
//输出当前数组
System.out.print(array[index] + "\t");
//向左遍历递归
if (2 * index + 1 < array.length) {
preOrder(2 * index + 1);
}
if (2 * index + 2 < array.length) {
preOrder(2 * index + 2);
}
}
public void inOrder() {
inOrder(0);
}
//顺序存储二叉树数组中序遍历
public void inOrder(int index) {
if (array == null || array.length == 0) {
System.out.print("顺序存储二叉树数组为空！\t");
return;
}
if (2 * index + 1 < array.length) {
inOrder(2 * index + 1);
}
//输出当前数组
System.out.print(array[index] + "\t");
if (2 * index + 2 < array.length) {
inOrder(2 * index + 2);
}
}
public void postOrder() {
postOrder(0);
}
//顺序存储二叉树数组后序遍历
public void postOrder(int index) {
if (array == null || array.length == 0) {
System.out.print("顺序存储二叉树数组为空！\t");
return;
}
if (2 * index + 1 < array.length) {
postOrder(2 * index + 1);
}
if (2 * index + 2 < array.length) {
postOrder(2 * index + 2);
}
//输出当前数组
System.out.print(array[index] + "\t");
}
}
线索化二叉树
基本介绍
- n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）。
- 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
- 一个结点的前一个结点，称为前驱结点。
- 一个结点的后一个结点，称为后继结点。
注意：n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】 个空指针域。
解释：2n表示每个节点都有左右两个指针，因此n个节点就有2n个指针，然后除去根节点外的每个节点都有被指针指向，这时候就使用了n-1个指针了，剩余空指针域就等于2n - (n-1) = n+1。
思路分析
线索化二叉树.png
遍历线索化二叉树
说明：对前面的中序线索化的二叉树， 进行遍历
分析：因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。 遍历的次序应当和中序遍历保持一致。
代码示例——前序、中序、后序线索二叉树及其遍历
public class ThreadedBinaryTree {
private HeroNode root;
//为了实现线索化，需要创建指向当前节点的前驱节点的指针，也就是保留上一个节点的指针地址，才能进行线索化
//递归线索化时pre总是保留前一个节点的指针
private HeroNode pre;
public ThreadedBinaryTree(HeroNode root) {
this.root = root;
}
//中序遍历线索化二叉树
public void threadedBinaryTreeListInOrder() {
HeroNode temp = root;
while (temp != null) {
//循环找到leftType=1的节点，第一个找到的就是第一个节点
while (temp.getLeftType() == 0) {
temp = temp.getLeft();
}
//打印当前这个节点
System.out.println(temp);
//如果当前节点的右指针指向的是后继节点，则一直输出
while (temp.getRightType() == 1) {
//获取当前节点的后继节点
temp = temp.getRight();
System.out.println(temp);
}
//向右替换这个变量的节点，让遍历走下去
temp = temp.getRight();
}
}
//前序遍历线索化二叉树,（按照后继线索遍历）
public void threadedBinaryTreeListPreOrder() {
HeroNode node = root;
while (node != null) {
while (node.getLeftType() == 0) {
System.out.println(node);
node = node.getLeft();
}
System.out.println(node);
node = node.getRight();
}
}
public void threadedBinaryTreeListPostOrder() {
threadedBinaryTreeListPostOrder(root);
}
//后序遍历线索化二叉树
public void threadedBinaryTreeListPostOrder(HeroNode node) {
if (node.getLeftType() == 0) {
threadedBinaryTreeListPostOrder(node.getLeft());
}
if (node.getRightType() == 0) {
threadedBinaryTreeListPostOrder(node.getRight());
}
System.out.println(node);
}
//重载
public void threadedBinaryTreeInOrder() {
threadedBinaryTreeInOrder(root);
}
public void threadedBinaryTreePreOrder() {
threadedBinaryTreePreOrder(root);
}
public void threadedBinaryTreePostOrder() {
threadedBinaryTreePostOrder(root);
}
/**
* 二叉树后序线索化
*
* @param node 当前需要线索化的节点
*/
public void threadedBinaryTreePostOrder(HeroNode node) {
//为空不能线索化
if (node == null) {
return;
}
//线索化左子树
threadedBinaryTreePreOrder(node.getLeft());
//线索化右子树
threadedBinaryTreePreOrder(node.getRight());
//线索化当前节点
//前驱节点设置 pre无需关注是否为null
if (node.getLeft() == null) {
node.setLeft(pre);
//修改当前节点的左指针类型为1:前驱节点
node.setLeftType(1);
}
//后继节点设置,在递归的时候在下一个节点的时候进行设置前一个节点的后继节点，这个时候才知道后继节点是哪个，才能进行后继节点设置
if (pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}
//每处理完一个节点后，设置当前节点为下一个要处理的节点的前驱节点
pre = node;
}
/**
* 二叉树中序线索化
*
* @param node 当前需要线索化的节点
*/
public void threadedBinaryTreeInOrder(HeroNode node) {
//为空不能线索化
if (node == null) {
return;
}
//1先线索化左子树（中序是左根右）
threadedBinaryTreeInOrder(node.getLeft());
//线索化当前节点
//前驱节点设置 pre无需关注是否为null
if (node.getLeft() == null) {
node.setLeft(pre);
//修改当前节点的左指针类型为1:前驱节点
node.setLeftType(1);
}
//后继节点设置,在递归的时候在下一个节点的时候进行设置前一个节点的后继节点，这个时候才知道后继节点是哪个，才能进行后继节点设置
if (pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}
//每处理完一个节点后，设置当前节点为下一个要处理的节点的前驱节点
pre = node;
//3先线索化右子树（中序是左根右）
threadedBinaryTreeInOrder(node.getRight());
}
public void threadedBinaryTreePreOrder(HeroNode node) {
if (node == null) {
return;
}
//当前节点处理
if (node.getLeft() == null) {
node.setLeft(pre);
node.setLeftType(1);
}
if (pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}
if (node != root) {
pre = node;
}
//线索化左子树
if (node.getLeftType() == 0) {
threadedBinaryTreePreOrder(node.getLeft());
}
//3先线索化右子树
if (node.getRightType() == 0) {
threadedBinaryTreePreOrder(node.getRight());
}
}
public static class HeroNode {
private Integer id;
private String name;
private HeroNode left;
private HeroNode right;
//使用int是因为int默认为0,而不是null
private int leftType;//0表示左子树，1表示前驱节点
private int rightType;//0表示右子树，1表示后继节点
@Override
public String toString() {
return "HeroNode{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
public int getLeftType() {
return leftType;
}
public void setLeftType(int leftType) {
this.leftType = leftType;
}
public int getRightType() {
return rightType;
}
public void setRightType(int rightType) {
this.rightType = rightType;
}
public HeroNode(Integer id, String name) {
this.id = id;
this.name = name;
}
public Integer getId() {
return id;
}
public void setId(Integer id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public HeroNode getLeft() {
return left;
}
public void setLeft(HeroNode left) {
this.left = left;
}
public HeroNode getRight() {
return right;
}
public void setRight(HeroNode right) {
this.right = right;
}
}
}
public class ThreadedBinaryTreeTest {
public static void main(String[] args) {
ThreadedBinaryTree.HeroNode root = new ThreadedBinaryTree.HeroNode(1, "艾米哈珀");
ThreadedBinaryTree.HeroNode node2 = new ThreadedBinaryTree.HeroNode(3, "大青山");
ThreadedBinaryTree.HeroNode node3 = new ThreadedBinaryTree.HeroNode(6, "霍恩斯");
ThreadedBinaryTree.HeroNode node4 = new ThreadedBinaryTree.HeroNode(8, "池傲天");
ThreadedBinaryTree.HeroNode node5 = new ThreadedBinaryTree.HeroNode(10, "绿儿");
ThreadedBinaryTree.HeroNode node6 = new ThreadedBinaryTree.HeroNode(14, "池寒枫");
root.setLeft(node2);
root.setRight(node3);
node2.setLeft(node4);
node2.setRight(node5);
node3.setLeft(node6);
ThreadedBinaryTree tree = new ThreadedBinaryTree(root);
tree.threadedBinaryTreeInOrder();
//以10号节点测试前驱和后继节点
System.out.println(node5.getLeft());
System.out.println(node5.getRight());
/**
* HeroNode{id=3, name='大青山'}
* HeroNode{id=1, name='艾米哈珀'}
*/
System.out.println("线索化二叉树中序遍历");
tree.threadedBinaryTreeListInOrder();
/**
* HeroNode{id=3, name='大青山'}
* HeroNode{id=1, name='艾米哈珀'}
* 线索化二叉树中序遍历
* HeroNode{id=8, name='池傲天'}
* HeroNode{id=3, name='大青山'}
* HeroNode{id=10, name='绿儿'}
* HeroNode{id=1, name='艾米哈珀'}
* HeroNode{id=14, name='池寒枫'}
* HeroNode{id=6, name='霍恩斯'}
*/
// System.out.println("线索化二叉树中前序遍历");
// tree.threadedBinaryTreePreOrder();
// tree.threadedBinaryTreeListPreOrder();
/**
* 线索化二叉树中前序遍历
* HeroNode{id=1, name='艾米哈珀'}
* HeroNode{id=3, name='大青山'}
* HeroNode{id=8, name='池傲天'}
* HeroNode{id=10, name='绿儿'}
* HeroNode{id=6, name='霍恩斯'}
* HeroNode{id=14, name='池寒枫'}
*/
// System.out.println("线索化二叉树中后序遍历");
// tree.threadedBinaryTreePostOrder();
// tree.threadedBinaryTreeListPostOrder();
/**
* 线索化二叉树中前序遍历
* HeroNode{id=1, name='艾米哈珀'}
* HeroNode{id=3, name='大青山'}
* HeroNode{id=8, name='池傲天'}
* HeroNode{id=10, name='绿儿'}
* HeroNode{id=6, name='霍恩斯'}
* HeroNode{id=14, name='池寒枫'}
*/
}
}
树结构的实际应用
堆排序
堆排序——Heap Sort——O(n log n)——选择排序的优化
堆排序是对选择排序的优化。
基本介绍
- 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
- 堆是具有以下性质的完全二叉树：
- 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
- 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
- 一般升序采用大顶堆，降序采用小顶堆 。
堆排序.png
堆排序2.png
基本思想
- 将待排序序列构造成一个大顶堆
- 此时，整个序列的最大值就是堆顶的根节点。
- 将其与末尾元素进行交换，此时末尾就为最大值。
- 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了.
思路分析
把一个待排序的数组看成是逻辑上的完全二叉树，这时候我们根据要进行升序还是降序排序，对数组重新构造成一颗大顶堆还是小顶堆，大顶堆则根节点是元素最大的值，小顶堆则是元素最小的值，因为每次都把根节点的值放在数组的最后，因此，大顶堆对应的是升序排列，而小顶堆对应的是降序排列。拿升序排列举例，这时候我们要对数组进行大顶堆初始化，这时候就要对二叉树的非叶子节点进行大顶堆排序，从右向左，从下往上一直到根节点进行排序，每次排序都递归得往下判断交换的值在子节点也是个父节点时是否满足大顶堆的条件，即父节点的值大于或等于其左右孩子节点的值。当一颗大顶堆二叉树构建成功后，我们就把根节点的值也就是arr[0]与数组末尾的值进行交互，这时候末尾的值就是此次排序的最大值了；然后对剩余的n-1个元素继续构造大顶堆，这时候其实只要对根节点的这个元素进行大顶堆构建即可，因为其他位置已经符合条件了，在对根节点进行大顶堆构建时要注意继续对其替换的子节点继续进行判断，直到叶节点为止。这样重复arr.length-1次，排序就完成了。
代码示例
/**
* 排序前:
* [4, 6, 8, 5, 9]
* 排序后:
* [4, 5, 6, 8, 9]
* 十万条数据排序耗时15
*/
public class HeapSort {
public static void main(String[] args) {
int[] array = {4, 6, 8, 5, 9,11,54,-9,28,-78,39,50,9,80,100};
System.out.println("排序前:");
System.out.println(Arrays.toString(array));
heapSort(array);
System.out.println("排序后:");
System.out.println(Arrays.toString(array));
int[] arrayTest = new int[10_0000];
for (int i = 0; i < 10_0000; i++) {
arrayTest[i] = (int) (Math.random() * 10_00000);
}
long start = System.currentTimeMillis();
heapSort(arrayTest);
// shellSortBySwap(arrayTest);//十万条数据排序耗时13043
long end = System.currentTimeMillis();
System.out.println("十万条数据排序耗时"+(end-start));
}
//堆排序
public static void heapSort(int[] arr) {
int temp = 0;
//1将无序序列构建成一个堆，根据升序降序需求选择大顶堆还是小顶堆，升序用大顶堆，降序用小顶堆
//从倒数最后一个父节点开始调整堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
//一开始构建大顶堆的时候要从最后一个父节点开始进行调整堆位置，根据完全二叉树的特点，下一个父节点就是i--,一直到根节点0
//这样就在一开始得到一个大顶堆
adjustHeap(arr, i, arr.length);
}
//2将堆顶元素与数组末尾元素交换，这样就依次将每次堆中的最大袁术沉淀到数组的末端，最大的沉淀在最后一个元素，倒数第二大的在倒数第二个位置，选择排序的优化版本
//重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前数组末尾元素，返回执行调整+交换步骤，知道整个数组有序
//只需要执行arr.length - 1次比较即可
for (int j = arr.length - 1; j > 0; j--) {
//交换
temp = arr[j];
arr[j] = arr[0];//此时大顶堆的第一个元素arr[0]就是最大的值
arr[0] = temp;
//每次进行交互完后只是根节点也就是arr[0]的位置不准确了，这时候只要调用一次从根节点出发的堆调整，就会一直往下对子节点及其子节点进行调整，调整到最后的叶子节点
//也就重新构建好一个大顶堆了
adjustHeap(arr, 0, j);
}
}
/**
* 完成以i对应的非叶子节点的树调整为大顶堆
*
* @param arr 待调整数组
* @param i 表示非叶子节点在数组中的索引
* @param length 表示对多少个元素进行调整，length在逐渐减少
*/
public static void adjustHeap(int[] arr, int i, int length) {
//先取出当前元素的值，保存在临时变量中
int temp = arr[i];
//for循环是为了在发生替换后继续判断子节点如果是父节点，是否需要再进行交互位置，完成大顶堆，比如从根节点0进来的元素
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
//如果左子节点的值小于右子节点的值，则把k指向右子节点，用于拿较大的子节点替换父节点
if (k + 1 < length && arr[k] < arr[k + 1]) {
k++;
}
//如果子节点大于父节点，则把较大的值赋值给当前节点
if (arr[k] > temp) {
arr[i] = arr[k];
i = k;//i指向k是为了保留最终要替换的那个值的位置，继续循环比较，
} else {
break;
}
}
//当for循环结束后，我们就将以i为父节点的树的最大值，放到了最顶部（局部）
arr[i] = temp;
}
}
哈夫曼树——WPL最小
哈夫曼树一般用来给字符编码，压缩数据用的。
基本介绍
- 给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。
- 赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
概念
- 路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
- 结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
- 树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和（注意是所有的叶子节点的的带权路径长度），记为WPL(weighted path length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。
- WPL最小的就是赫夫曼树。
哈夫曼树.png
构成赫夫曼树的步骤
- 从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树
- 取出根节点权值最小的两颗二叉树
- 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
- 再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树
思路分析
在构建哈夫曼树时，每次都取权值最小的两个数来构建一颗新的树，这时候后移除最小的两个权值的数，再由最小两个权值构建成的树的父节点加入队列中继续排序得到新的最小的两个数，继续取最小的两个数进行构建树操作，直到队列中只剩一个节点。
哈夫曼树2.png
代码示例
/**
* Node{value=67}
* Node{value=29}
* Node{value=38}
* Node{value=15}
* Node{value=7}
* Node{value=8}
* Node{value=23}
* Node{value=10}
* Node{value=4}
* Node{value=1}
* Node{value=3}
* Node{value=6}
* Node{value=13}
*/
public class HuffmanTree {
public static void main(String[] args) {
int[] arr = {13, 7, 8, 3, 29, 6, 1};
Node root = createHuffmanTree(arr);
root.preOrderList();
}
/**
* //创建哈夫曼树
* @param arr 待创建哈夫曼树的数组
* @return 创建好后的哈夫曼树的root节点
*/
public static Node createHuffmanTree(int[] arr) {
//遍历数组把元素封装为Node放到ArrayList中
List<Node> nodes = new ArrayList<>(arr.length);
for (int value : arr) {
nodes.add(new Node(value));
}
while (nodes.size() > 1) {
//排序，node节点实现Comparable接口
Collections.sort(nodes);
//取出权值最小的两个节点，构建一个新的权限节点加入到List中，并移除最小的两个节点，继续循环排序取出构建新节点操作
Node left = nodes.get(0);
Node right = nodes.get(1);
Node parent = new Node(left.getValue() + right.getValue());
parent.setLeft(left);
parent.setRight(right);
//根据下标移除时要注意移除完后原来1的下标就变为0了，需要继续移除的是0下标的值
// nodes.remove(0);
// nodes.remove(0);
nodes.remove(left);
nodes.remove(right);
nodes.add(parent);
}
return nodes.get(0);
}
//前序遍历方法
public void preOrderList(Node root) {
if (root == null) {
System.out.println("哈夫曼树不存在");
return;
}
root.preOrderList();
}
}
public class Node implements Comparable<Node> {
private int value;
private Node left;
private Node right;
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
/**
* 前序遍历
*/
public void preOrderList() {
System.out.println(this);
if (this.left != null) {
this.left.preOrderList();
}
if (this.right != null) {
this.right.preOrderList();
}
}
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
@Override
public int compareTo(Node node) {
//从小到大排序
return this.value - node.value;
//从大到小排序
// return -(this.value - node.value);
}
}
