二分查找和常用排序算法

vlambda
2020-05-20

二分查找和常用排序算法

二分查找

需要查找的数组必须有序

package com.hzy;
import org.junit.Test;
/** 查找算法* */public class LookUp { //二分查找，前提必须有序 @Test public void test1(){ int ele=78; int[] arr={21,32,42,56,78,98}; int indexByELE = getIndexByELE(arr, ele); System.out.println("该元素出现的索引:"+indexByELE); }
 private int getIndexByELE(int[] arr,int ele) { //定义最小索引，中间索引，最大索引 int minIndex=0; int maxIndex=arr.length-1; int centerIndex=(minIndex+maxIndex)/2; //如果需要查询的元素正好等于中间的元素，返回中间的元素 while (minIndex<=maxIndex){//如果最小索引<最大索引就一直循环 if(ele==arr[centerIndex]){ return centerIndex; //如果你要找的元素大于中间的元素，那么你就移动最小索引 }else if(ele>arr[centerIndex]){ minIndex=centerIndex+1; //如果你要找的元素小于中间的元素，那么你就移动最大索引 }else if(ele<arr[centerIndex]){ maxIndex=centerIndex-1; } //重新计算中间索引 centerIndex=(minIndex+maxIndex)/2; } return -1;//如果没有找到 }}

常用排序算法

二分查找和常用排序算法 1、冒泡排序
排序原理：数组元素两两比较，交换位置，大元素往后放，那么经过一轮比较后，最大的元素，就会出现在最大索引处。

/*冒泡排序*/ @Test public void test1(){ int[] arr={24,69,80,57,13};//待排序数组 //双重循环进行比较 for (int j = 0; j < arr.length-1; j++) {//循环元素下标 for (int i = 0; i < arr.length-1-j; i++) {//循环比较，第一次比较之后最大的在最后(无需比较)，所以-j if(arr[i]>arr[i+1]){//如果前面的元素大于后面的元素(交换位置) //交换位置 int t=arr[i]; arr[i]=arr[i+1]; arr[i+1]=t; } } } System.out.println(Arrays.toString(arr)); }

2、选择排序
排序原理：从0索引处开始，依次和后面的元素进行比较，小的元素向前放，经过一轮比较后，小的元素就出现在了最小索引处。
二分查找和常用排序算法

/*选择排序*/ @Test public void test2(){ int[] arr={12,26,46,54,21,32,45,46}; for (int i = 0; i < arr.length-1; i++) {//循环各个元素 for (int j = 1+i; j < arr.length-1; j++) {//使用上一层循环中的i和i以后的元素j进行比较交换 if(arr[i]>arr[j]){//用第一个元素(交换后使用交换后的值接着向后比较，直到比较一轮)依次和后面的元素进行比较 arr[i]=arr[j]+arr[i]; arr[j]=arr[i]-arr[j]; arr[i]=arr[i]-arr[j]; } } } System.out.println(Arrays.toString(arr)); }

3、插入排序
排序算法：算法思路：直接插入排序，是一种最简单的排序方法，他的基本操作是将一个记录插入到一个长度为m的有序表中，使之仍保持有序。

/*插入排序*/ @Test public void test3(){ //直接插入排序，从1索引处开始，将后面的元素，插入到之前的有序表中使之仍保持有序 int[] arr={12,26,46,54,21,32,45,46};
// for (int i = 0; i < arr.length-1; i++) {//外层循环定义轮次// //进行比较插入// int j=i;// while (j>0&&arr[j+1]<arr[j]){// int t=arr[j+1];// arr[j+1]=arr[j];// arr[j]=t;// j--;// }// } for (int i = 0; i < arr.length-1; i++) { for (int j = i+1; j > 0; j--) { if(arr[j]<arr[j-1]){ int t=arr[j-1]; arr[j-1]=arr[j]; arr[j]=t; } } } System.out.println(Arrays.toString(arr)); }

4、希尔排序
二分查找和常用排序算法
希尔排序又称缩小增量排序
直接插入排序，其实就是增量为1的希尔排序
基本思想：先将原表按增量ht分组，每个子文件按照直接插入法排序。同样，用下一个增量ht/2将文件再分为子文件，再直接插入法排序。直到ht=1时整个文件排好序。
关键：选择合适的增量。
希尔排序算法9-3：可以通过三重循环来实现

/*希尔排序*/ @Test public void test4(){ //希尔排序：他是对插入排序的一个优化，核发思想就是合理的选取增量，经过一轮排序后，就会让序列大致有序 //然后不断的缩小增量，进行插入排序，直到增量为1 那 整个排序结束 //直接插入排序，其实就是增量为1的希尔排序 int[] arr={12,26,46,54,21,32,45,46,20}; //定义一个增量,第一次增量选取数组长度的一半 //我们第一次增量选取数组长度的一半还不是很高效 //我们可以使用一种序列叫做克努特序列 //根据克努特序列选取我们第一次的增量 int jiange=1; while (jiange<=arr.length/3){ jiange=jiange*3+1; } for (int h = jiange; h > 0 ; h=(h-1)/3) { for (int i = h; i < arr.length; i++) { //进行比较插入 int j=i; while (j>h-1&&arr[j]<arr[j-h]){ int t=arr[j-h]; arr[j-h]=arr[j]; arr[j]=t; j-=h; } } } System.out.println(Arrays.toString(arr)); }

5、快速排序
实现思路：挖坑填数：

将基准数挖出形成第一个坑。
由后向前找出比他小的数，找到后挖出些数填到前一个坑中。
由前向后找出比他大或等于的数，找出后也挖出此类填到间一个坑中。
再重复执行2，3步骤。

/*快速排序*/ @Test public void test5(){ int[] arr={12,26,46,54,21,32,45,46}; int start=0; int end=arr.length-1; quickSort(arr,start,end); System.out.println(Arrays.toString(arr)); } private void quickSort(int[] arr,int start,int end){ //找出分左右两区的索引位置，然后对左右两区进行递归调用 if(start<end){ int index=getIndex(arr,start,end);//找到基数填到了哪个坑中 quickSort(arr,start,index-1);//左区 quickSort(arr,index+1,end);//右区 } } /* * 1. 将基准数挖出形成第一个坑。 2. 由后向前找出比他小的数，找到后挖出些数填到前一个坑中。 3. 由前向后找出比他大或等于的数，找出后也挖出此类填到间一个坑中。 4. 再重复执行2，3步骤。 * */ private int getIndex(int[] arr,int start,int end){ int i=start; int j=end; int x=arr[i]; while (i<j){ //由后向前找出比他小的数，找到后挖出些数填到前一个坑中。 while (i<j&&arr[j]>=x){ j--; } if(i<j){ arr[i]=arr[j]; i++; } //由前向后找出比他大或等于的数，找出后也挖出此类填到间一个坑中。 while (i<j&&arr[i]<x){ i++; } if(i<j){ arr[j]=arr[i]; j--; } } arr[i]=x;//把基准数迁到最后一个坑中 return i; }

6、归并排序
分而治之：先拆分再归并

 //归并排序 @Test public void test6(){ int[] arr={12,26,46,54,21,32,45,46}; //拆分并归并 chaifen(arr,0,arr.length-1);
 //归并 //guiBing(arr,0,3,arr.length-1); System.out.println(Arrays.toString(arr)); }
 private void chaifen(int[] arr, int startIndex, int endIndex) { //计算中间索引 int centerIndex=(startIndex+endIndex)/2; if(startIndex<endIndex){ chaifen(arr,startIndex,centerIndex); chaifen(arr,centerIndex+1,endIndex); guiBing(arr,startIndex,centerIndex,endIndex); } }
 private void guiBing(int[] arr, int startIndex, int centerIndex, int endIndex) { //定义一个临时数据 int[] tempArr=new int[endIndex-startIndex+1]; //定义左边数组的起始索引 int i=startIndex; //定义右边数组的起始索引 int j=centerIndex+1; //定义临时数组的起始索引 int index=0; //比较左右两个数组的元素大小，往临时数组中放 while (i<=centerIndex&&j<=endIndex){ if(arr[i]<=arr[j]){ tempArr[index]=arr[i]; i++; }else { tempArr[index]=arr[j]; j++; } index++; } //处理剩余元素 while (i<=centerIndex){ tempArr[index]=arr[i]; i++; index++; } while (j<=endIndex){ tempArr[index]=arr[j]; j++; index++; } //将临时数组中的元素取到原数组中 for (int k = 0; k < tempArr.length; k++) { arr[k+startIndex]=tempArr[k]; }
 }

7、基数排序
通过分配再收集进行排序

//基数排序 @Test public void test7(){ //基数排序：通过分配再收集的方式进行排序 int[] arr={12,26,46,54,21,32,45,46}; //得确定排序轮次 sortArray(arr); System.out.println(Arrays.toString(arr)); }
 private void sortArray(int[] arr) { //定义二维数组，放10个桶 int[][] tempArr=new int[10][arr.length]; //定义统计数组 int[] counts=new int[10]; //获取数组中的最大值 int max=getMax(arr); int len = String.valueOf(max).length(); //循环轮次 for (int i = 0,n=1; i < len; i++,n*=10) { for (int j = 0; j < arr.length; j++) { //获取每个位上的数字 int ys=arr[j]/n%10; tempArr[ys][counts[ys]++]=arr[j]; } //取出桶中的元素 int index=0; for (int k = 0; k < counts.length; k++) { if(counts[k]!=0){ for (int h = 0; h < counts[k]; h++) { //从桶中取出元素放回原数组 arr[index]=tempArr[k][h]; index++; } counts[k]=0;//清除上一次统计的个数 } } }
 }
 private int getMax(int[] arr) { int max=arr[0]; for (int i = 1; i < arr.length; i++) { if(arr[i]>max){ max=arr[i]; } } return max; }

8、堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序
堆排序的基本思想是：

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。
将其与末尾元素进行交换，此时末尾就为最大值。
然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。
如此反复执行，便能得到一个有序序列了。
添加完全二叉树，从上往下，从左往右。

//堆排序 @Test public void test8(){ //定义一个数组 int[] arr={1,0,6,7,2,3,4,5,12,34,24}; //调整成大顶堆的方法 //定义开始调整的位置 int startIndex=(arr.length-1)/2; //循环开始调 for (int i = startIndex; i >= 0 ; i--) { toMaxHeap(arr,arr.length,i); } System.out.println(Arrays.toString(arr)); //经过上面的操作后，已经把数组变成了一个大顶堆，把根元素和最后一个元素进行调换 for (int i = arr.length-1; i > 0; i--) { //进行调换 int t=arr[0]; arr[0]=arr[i]; arr[i]=t; //换完之后，我们再把剩余的元素调成大顶堆 toMaxHeap(arr,i,0); } System.out.println(Arrays.toString(arr)); }
 //数组 调整的元素个数 从哪里开始调整 private void toMaxHeap(int[] arr, int size, int index) { //获取左右字节的索引 int leftNodeIndex=index*2+1; int rightNodeIndex=index*2+2; //查找最大节点所对应的索引 int maxIndex=index; if(leftNodeIndex<size&&arr[leftNodeIndex]>arr[maxIndex]){ maxIndex=leftNodeIndex; } if(rightNodeIndex<size&&arr[rightNodeIndex]>arr[maxIndex]){ maxIndex=rightNodeIndex; } //我们来调换位置 if(maxIndex!=index){ int t=arr[maxIndex]; arr[maxIndex]=arr[index]; arr[index]=t; //调换完之后，可能会影响到下面的子树，不是大顶堆，我们还需要再次调换 toMaxHeap(arr,size,maxIndex); } }