排序
时间频度T(n)
时间复杂度O(f(n))
| 排序方法 | 平均时间复杂度 | 最差时间复杂度 |
|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) |
| 选择排序 | centered | $12 |
| zebra stripes | are neat | $1 |
冒泡排序
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class BubbleSort {
public static void main(String[] args) {
int[] arr = new int[80000];
for(int i =0; i < 80000;i++) {
arr[i] = (int)(Math.random() * 8000000); //生成一个[0, 8000000) 数
}
Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(data1);
System.out.println("排序前的时间是=" + date1Str);
//测试冒泡排序
sort2(arr);
Date data2 = new Date();
String date2Str = simpleDateFormat.format(data2);
System.out.println("排序后的时间是=" + date2Str);
// 测试时间 8秒
}
//普通版冒泡排序
public static void sort1(int [] arr) {
int length = arr.length;
for(int i=0 ; i<length-1 ; i++) { //进行length -1 轮循环， 第一趟排出最大的数 ，第二趟排出第二大的数 依次。。。
for(int j =0;j<(length-1)- i;j++) {//第一轮需要比较4次，第二轮需要比较3次 第n轮需要比较(length-1)-i次
if(arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
System.out.println("排序后的结果"+Arrays.toString(arr));
}
System.out.println("第"+(i+1)+"趟排序后的结果"+Arrays.toString(arr));
}
}
/**
* 优化版冒泡排序
* 上面普通版的排序 在第1轮排序后得到的结果是[-10, 3, 7, 8, 22]
* 其实，这就是最终结果，后面的排序是不必要的。因此我们可以将排序结束
*/
public static void sort2(int [] arr) {
int length = arr.length;
for(int i=0 ; i<length-1 ; i++) { //进行length -1 轮循环， 第一趟排出最大的数 ，第二趟排出第二大的数 依次。。。
boolean flag = false;
for(int j =0;j<(length-1)- i;j++) {//第一轮需要比较4次，第二轮需要比较3次 第n轮需要比较(length-1)-i次
if(arr[j]>arr[j+1]) {
flag = true;
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
if(!flag) {
break;
}else {
flag = false;//重置flag
}
}
}
}
选择排序
选择排序思想， 以升序排序为例子，选择排序是第一次 找出最小的数，这个数与arr[0]进行交换，第二次选出除arr[0]之外的最小数 这个数与arr[1]交换，第三轮 选出除arr[0],arr[1]之外的最小数 这个数与arr[2]进行交换，依次类推。。。 这就是选择排序，其时间复杂度为：
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
//选择排序
public class SelectSort {
public static void main(String[] args) {
// int [] arr = {101, 34, 119, 1, -1, 90, 123};
// selectSort(arr);
//
//创建要给80000个的随机的数组
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
}
System.out.println("排序前");
Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(data1);
System.out.println("排序前的时间是=" + date1Str);
selectSort(arr);
Date data2 = new Date();
String date2Str = simpleDateFormat.format(data2);
System.out.println("排序后的时间是=" + date2Str);
//测试时间 1秒
}
//选择排序
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;//记录最小数的索引
int min = arr[i];// 记录最小数
/**
* 随着j的增加 min的值越来越小 ，导致在后面的比较中，碰到比min更小数的概率越来越低 ，
* 因此减少了交换次数 这是选择排序比冒泡排序快的原因 ，然而其时间复杂度依然是 O(n^2),
* 因为其减少的是交换次数 ，而不是比较次数
*/
for (int j = i + 1; j < arr.length; j++) {
if (min > arr[j]) { // 说明假定的最小值，并不是最小
min = arr[j]; // 重置min
minIndex = j; // 重置minIndex
}
}
// 将最小值，放在arr[0], 即交换
if (minIndex != i) {
arr[minIndex] = arr[i];
arr[i] = min;
}
//
// System.out.println("第"+(i+1)+"轮后~~");
// System.out.println(Arrays.toString(arr));// 1, 34, 119, 101
}
}
}
插入排序
插入排序思想: 以升序为例子， 插入排序是这样的 将一个无序数组看作两个部分，一部分有序 一部分无序，最开始的时候arr[0] 为有序部分 并且这个有序部分就这一个元素，其余的arr[1] ~ arr[length-1]作为无序部分，这是最初始化的状态 ，然后我们从
1 到(length-1)遍历，依次将arr[1],arr[2]... 加入到有序部分中去，加入的时候我们需要找到待加入的数在有序部分的位置，具体步骤是这样的:我们将待加入的数与有序部分的最后一个数(arr[insertIndex])比较，如果arr[insertIndex]比待加入的数大，那么将arr[insertIndex]后移，然后待插入的数与arr[insertIndex-1]比较 依次比较即可找到待插入数据的位置的前一个数arr[target],我们将待插入的数放到arr[target+1]上去 即可
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class InsertSort {
public static void main(String[] args) {
// int[] arr = {101, 34, 119, 1, -1,101,34, 89};
// insertSort(arr) ;
// System.out.println(Arrays.toString(arr));
// 创建要给80000个的随机的数组
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
}
System.out.println("插入排序前");
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);
//测试时间 2秒
}
//插入排序
public static void insertSort(int[] arr) {
int insertVal = 0;
int insertIndex = 0;
for(int i = 1; i < arr.length; i++) {
insertVal = arr[i];//定义待插入的数
insertIndex = i - 1; // 即待插入数据的前一个数据
// 给insertVal 找到插入的位置
// 说明
// 1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界
// 2. insertVal < arr[insertIndex] 待插入的数，说明还没有找到插入位置
// 3. 就需要将 arr[insertIndex]数据 后移
while (insertIndex >= 0 && insertVal < arr[insertIndex]) { //这里数据交换的次数明显比选择排序多，选择排序是每一轮只需要交换一次
arr[insertIndex + 1] = arr[insertIndex];//将被比较的数后移
insertIndex--;
}
// 当退出while循环时，说明插入的位置找到, insertIndex + 1
// 举例：理解不了，我们一会 debug
//这里我们判断是否需要赋值
if(insertIndex + 1 != i) {
arr[insertIndex + 1] = insertVal;
}
//System.out.println("第"+i+"轮插入");
//System.out.println(Arrays.toString(arr));
}
}
}
我们来看插入排序存在的问题 对于数组{2,6,8,9,5,1},我们在处理1的时候，需要移动5,9,8,6,2。当插入的数据是比较小的数的时候，后移的次数明显增多，这对效率有明显影响。
希尔排序：希尔排序是将记录按照下标的一定增量分组，对每一组进行插入排序算法排序，随着增量的逐渐减少，当增量减小为1时，每个整个数组恰好被分为一组，算法结束
image.png
image.png
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class ShellSort {
public static void main(String[] args) {
// int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
//
// shellSort(arr);//移位方式
// 创建要给80000个的随机的数组
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
}
System.out.println("排序前");
Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(data1);
System.out.println("排序前的时间是=" + date1Str);
// shellSort(arr); //交换式 测试时间 6秒
shellSort2(arr);//移位方式 测试时间 几乎0秒
Date data2 = new Date();
String date2Str = simpleDateFormat.format(data2);
System.out.println("排序前的时间是=" + date2Str);
//System.out.println(Arrays.toString(arr));
}
// 使用逐步推导的方式来编写希尔排序
// 希尔排序时， 对有序序列在插入时采用交换法,
// 思路(算法) ===> 代码
public static void shellSort(int[] arr) {
int temp = 0;
// 根据前面的逐步分析，使用循环处理
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
// 遍历各组中所有的元素(共gap组，每组有个元素), 步长gap
for (int j = i - gap; j >= 0; j -= gap) {
// 如果当前元素大于加上步长后的那个元素，说明交换
if (arr[j] > arr[j + gap]) {
temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
// System.out.println("希尔排序第" + (++count) + "轮 =" + Arrays.toString(arr));
}
}
//对交换式的希尔排序进行优化->移位法
public static void shellSort2(int[] arr) {
// 增量gap, 并逐步的缩小增量
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// 从第gap个元素，逐个对其所在的组进行直接插入排序
for (int i = gap; i < arr.length; i++) {
int j = i;
int temp = arr[j];
if (arr[j] < arr[j - gap]) {
while (j - gap >= 0 && temp < arr[j - gap]) {
//移动
arr[j] = arr[j-gap];
j -= gap;
}
//当退出while后，就给temp找到插入的位置
arr[j] = temp;
}
}
}
}
}
快速排序
快速排序是对冒泡排序的一种改进，基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的数据都比另外一部分的数据小，然后再通过这个方法将这两部分的数据分部进行快速排序，从而到达整个数组有序。示意图如下：
image.png
图中是以最后一个数为基准，我们以中间的数字为基准来写代码
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = {-9,-21,-1,-2,0,12,33,-56,-3,44,1,3,5};
quickSort(arr, 0, arr.length-1);
System.out.println("arr=" + Arrays.toString(arr));
// //测试快排的执行速度
// // 创建要给80000个的随机的数组
// int[] arr = new int[80000];
// for (int i = 0; i < 80000; i++) {
// arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
// }
//
// System.out.println("排序前");
// Date data1 = new Date();
// SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
// String date1Str = simpleDateFormat.format(data1);
// System.out.println("排序前的时间是=" + date1Str);
//
// quickSort(arr, 0, arr.length-1);//测试时间 不到1秒
//
// Date data2 = new Date();
// String date2Str = simpleDateFormat.format(data2);
// System.out.println("排序前的时间是=" + date2Str);
// //System.out.println("arr=" + Arrays.toString(arr));
}
public static void quickSort(int [] arr,int left,int right){
int temp = 0;//定义一个交换的数
int l = left;
int r = right;
int pivot = arr[(l + r) / 2];
while(l < r) {
while(arr[l] < pivot) {//在pivot 左侧找出一个大于或者等于pivot的数
l = l+1;
}
while(arr[r] > pivot) {//在pivot 右侧找出一个小于或者等于pivot的数
r= r-1;
}
/**
* 如果左索引都大于有索引了 说明它们的循环查找的时候已经碰头了
* 这个时候左边的数据都小于等于pivot，右边的数据都大于等于pivot
*/
if(l >= r) {
break;
}
//两个数进行交换
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
//如果arr[l] 与pivot相等，那么要将索引向前推进一位，否则arr[l]这个数会导致上面的while循环一直退出 形成死循环
//因为arr[i] 是由arr[r]交换得来的 所以我们将r左进一位
if(arr[l] == pivot) {
r = r-1;
}
// 同理 我们让i右移一位
if(arr[r] == pivot) {
l = l+1;
}
}
if(l ==r) {//如果左索引和右索引重合 我们需要将他们错开，其实重合索引对应的那个数就是privot,而
// 这个privot是已经确定好位置了的 我们不需要在将他放进来比较
l = l+1;
r = r-1;
}
//将左部分的数据 进行递归
if(left < r) {
quickSort(arr, left, r);
}
if(l<right) {
quickSort(arr, l, right);
}
}
}
归并排序
归并排序采用经典的分治策略，分：将一个问题分成小问题 然后递归求解，治：将将分之后的结果"修补"在一起：思路示意图如下
image.png
image.png
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class MergetSort {
public static void main(String[] args) {
//int arr[] = { 8, 4, 5, 7, 1, 3, 6, 2 }; //
//测试快排的执行速度
// 创建要给80000个的随机的数组
int[] arr = new int[8000000];
for (int i = 0; i < 8000000; i++) {
arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
}
System.out.println("排序前");
Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(data1);
System.out.println("排序前的时间是=" + date1Str);
int temp[] = new int[arr.length]; //归并排序需要一个额外空间
mergeSort(arr, 0, arr.length - 1, temp);
Date data2 = new Date();
String date2Str = simpleDateFormat.format(data2);
System.out.println("排序前的时间是=" + date2Str);
//System.out.println("归并排序后=" + Arrays.toString(arr));
}
//分+合方法
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if(left < right) {
int mid = (left + right) / 2; //中间索引
//向左递归进行分解
mergeSort(arr, left, mid, temp);
//向右递归进行分解
mergeSort(arr, mid + 1, right, temp);
//每分解一轮就合并一轮
merge(arr, left, mid, right, temp);
}
}
//合并的方法
/**
*
* @param arr 排序的原始数组
* @param left 左边有序序列的初始索引
* @param mid 中间索引
* @param right 右边索引
* @param temp 做中转的数组
*/
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left; // 初始化i, 左边有序序列的初始索引
int j = mid + 1; //初始化j, 右边有序序列的初始索引
int t = 0; // 指向temp数组的当前索引
//(一)
//先把左右两边(有序)的数据按照规则填充到temp数组
//直到左右两边的有序序列，有一边处理完毕为止
while (i <= mid && j <= right) {//继续
//如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
//即将左边的当前元素，填充到 temp数组
//然后 t++, i++
if(arr[i] <= arr[j]) {
temp[t] = arr[i];
t += 1;
i += 1;
} else { //反之,将右边有序序列的当前元素，填充到temp数组
temp[t] = arr[j];
t += 1;
j += 1;
}
}
//(二)
//把有剩余数据的一边的数据依次全部填充到temp
while( i <= mid) { //左边的有序序列还有剩余的元素，就全部填充到temp
temp[t] = arr[i];
t += 1;
i += 1;
}
while( j <= right) { //右边的有序序列还有剩余的元素，就全部填充到temp
temp[t] = arr[j];
t += 1;
j += 1;
}
//(三)
//将temp数组的元素拷贝到arr
//注意，并不是每次都拷贝所有
t = 0;
int tempLeft = left; //
//第一次合并 tempLeft = 0 , right = 1 // tempLeft = 2 right = 3 // tL=0 ri=3
//最后一次 tempLeft = 0 right = 7
while(tempLeft <= right) {
arr[tempLeft] = temp[t];
t += 1;
tempLeft += 1;
}
}
}
基数排序
基数排序基本思想 ：将所有带比较的数值统一为二位同样长度的数字，然后由最低位开始 依次进行进行排序，这样从最低位排序一直到最高位排序完成，数据就变成了一个有序的序列。其实基数排序利用的就是 一个数a如果大于一个数b,那么a的高位数字大于b的高位数字或者二者的高位数字相等 但是a的低位数字肯定比b的低位数字大。
image.png
image.png
基数排序的特性
- 速度非常快，800万条数据排序只需1秒
- 基数排序采用的是空间换时间策略，占用内存比较大 ，容易造成OutOfMemoryError
- 基数排序是稳定的排序，假如 arr[i] = arr[i+m] = k,经过排序之后arr[i] 依然排在arr[i+m]之前
- 有负数的数组不能采用基数排序,如果需要支持负数 参考https://code.i-harness.com/zh-CN/q/e98fa9
public class RadixSort {
public static void main(String[] args) {
int arr[] = { 53, 3, 542, 748, 14, 214};
// 80000000 * 11 * 4 / 1024 / 1024 / 1024 =3.3G
// int[] arr = new int[8000000];
// for (int i = 0; i < 8000000; i++) {
// arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
// }
System.out.println("排序前");
Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(data1);
System.out.println("排序前的时间是=" + date1Str);
radixSort(arr);
Date data2 = new Date();
String date2Str = simpleDateFormat.format(data2);
System.out.println("排序前的时间是=" + date2Str);
System.out.println("基数排序后 " + Arrays.toString(arr));
}
//基数排序方法
public static void radixSort(int[] arr) {
//根据前面的推导过程，我们可以得到最终的基数排序代码
//1. 得到数组中最大的数的位数
int max = arr[0]; //假设第一数就是最大数
for(int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
//得到最大数是几位数
int maxLength = (max + "").length();
//定义一个二维数组，表示10个桶, 每个桶就是一个一维数组
//说明
//1. 二维数组包含10个一维数组
//2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为arr.length
//3. 名明确，基数排序是使用空间换时间的经典算法
int[][] bucket = new int[10][arr.length];
//为了记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
//可以这里理解
//比如：bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数
int[] bucketElementCounts = new int[10];
//这里我们使用循环将代码处理
for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) {
//(针对每个元素的对应位进行排序处理)， 第一次是个位，第二次是十位，第三次是百位..
for(int j = 0; j < arr.length; j++) {
//取出每个元素的对应位的值
int digitOfElement = arr[j] / n % 10;
//放入到对应的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
//按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
int index = 0;
//遍历每一桶，并将桶中是数据，放入到原数组
for(int k = 0; k < bucketElementCounts.length; k++) {
//如果桶中，有数据，我们才放入到原数组
if(bucketElementCounts[k] != 0) {
//循环该桶即第k个桶(即第k个一维数组), 放入
for(int l = 0; l < bucketElementCounts[k]; l++) {
//取出元素放入到arr
arr[index++] = bucket[k][l];
}
}
//第i+1轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
bucketElementCounts[k] = 0;
}
//System.out.println("第"+(i+1)+"轮，对个位的排序处理 arr =" + Arrays.toString(arr));
}
}
}
image.png
image.png
查找算法
线性查找
线性查找：一个一个的去查找，不要求数组有序
public class SeqSearch {
public static void main(String[] args) {
int arr[] = { 1, 9, 11, -1, 34, 89 };// 没有顺序的数组
int index = seqSearch(arr, -11);
if(index == -1) {
System.out.println("没有找到到");
} else {
System.out.println("找到，下标为=" + index);
}
}
//这里我们实现的线性查找是找到一个满足条件的值，就返回
public static int seqSearch(int[] arr, int value) {
// 线性查找是逐一比对，发现有相同值，就返回下标
for (int i = 0; i < arr.length; i++) {
if(arr[i] == value) {
return i;
}
}
return -1;
}
}
二分查找
二分查找：思路
image.png
import java.util.ArrayList;
import java.util.List;
//注意：使用二分查找的前提是 该数组是有序的.
public class BinarySearch {
public static void main(String[] args) {
//int arr[] = { 1, 8, 10, 89,1000,1000, 1234 };
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
//
int resIndex = binarySearch(arr, 0, arr.length - 1, 1000);
System.out.println("resIndex=" + resIndex);
// List<Integer> resIndexList = binarySearch2(arr, 0, arr.length - 1, 1);
// System.out.println("resIndexList=" + resIndexList);
}
// 二分查找算法
/**
*
* @param arr 数组
* @param left 左边的索引
* @param right 右边的索引
* @param findVal 要查找的值
* @return 如果找到就返回下标，如果没有找到，就返回 -1
*/
public static int binarySearch(int[] arr, int left, int right, int findVal) {
//在整个过程中 左递归right = mid -1 导致right越来越小，右递归 left = mid+1 导致left越来越大
// 当 left > right 时，说明递归整个数组，但是没有找到
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
int midVal = arr[mid];
if (findVal > midVal) { // 向 右递归
return binarySearch(arr, mid + 1, right, findVal);
} else if (findVal < midVal) { // 向左递归
return binarySearch(arr, left, mid - 1, findVal);
} else {
return mid;
}
}
/*
* {1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中，
* 有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000
*
* 思路分析
* 1. 在找到mid 索引值，不要马上返回
* 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
* 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
* 4. 将Arraylist返回
*/
public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
System.out.println("hello~");
// 当 left > right 时，说明递归整个数组，但是没有找到
if (left > right) {
return new ArrayList<Integer>();
}
int mid = (left + right) / 2;
int midVal = arr[mid];
if (findVal > midVal) { // 向 右递归
return binarySearch2(arr, mid + 1, right, findVal);
} else if (findVal < midVal) { // 向左递归
return binarySearch2(arr, left, mid - 1, findVal);
} else {
// * 思路分析
// * 1. 在找到mid 索引值，不要马上返回
// * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
// * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
// * 4. 将Arraylist返回
List<Integer> resIndexlist = new ArrayList<Integer>();
//向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
int temp = mid - 1;
while(true) {
if (temp < 0 || arr[temp] != findVal) {//退出
break;
}
//否则，就temp 放入到 resIndexlist
resIndexlist.add(temp);
temp -= 1; //temp左移
}
resIndexlist.add(mid); //
//向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
temp = mid + 1;
while(true) {
if (temp > arr.length - 1 || arr[temp] != findVal) {//退出
break;
}
//否则，就temp 放入到 resIndexlist
resIndexlist.add(temp);
temp += 1; //temp右移
}
return resIndexlist;
}
}
}
插值查找
插值查找类似于二分查找 ，二分查找每次都是从中间mid开始比较查找，插值查找是从自适应位置mid开始比较查找的
image.png
image.png
public class InsertValueSearch {
public static void main(String[] args) {
// int [] arr = new int[100];
// for(int i = 0; i < 100; i++) {
// arr[i] = i + 1;
// }
int arr[] = { 1,2,3,4,5,6,7, 8, 10, 89,90,91, 1234,22222,55555,67891,999999 };
int index = insertValueSearch(arr, 0, arr.length - 1, 8);//插值查找需要查找8次
// int index = binarySearch(arr, 0, arr.length, 1);//二分查找需要查找4次
System.out.println("index = " + index);
//System.out.println(Arrays.toString(arr));
}
//编写插值查找算法
//说明：插值查找算法，也要求数组是有序的
/**
*
* @param arr 数组
* @param left 左边索引
* @param right 右边索引
* @param findVal 查找值
* @return 如果找到，就返回对应的下标，如果没有找到，返回-1
*/
public static int insertValueSearch(int[] arr, int left, int right, int findVal) {
System.out.println("插值查找次数~~");
//注意：findVal < arr[0] 和 findVal > arr[arr.length - 1] 必须需要
//否则我们得到的 mid 可能越界
if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
return -1;
}
// 求出mid, 自适应
int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
int midVal = arr[mid];
if (findVal > midVal) { // 说明应该向右边递归
return insertValueSearch(arr, mid + 1, right, findVal);
} else if (findVal < midVal) { // 说明向左递归查找
return insertValueSearch(arr, left, mid - 1, findVal);
} else {
return mid;
}
}
}
插值查找需要注意的地方是：
- 当数据有序且比较均匀，使用插值查找速度很快。
- 当数据有序 但是不均匀，插值查找速度不一定比二分查找快。
斐波那契查找： 好难理解
