vlambda博客
学习文章列表

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;//如果没有找到 }}

/*冒泡排序*/ @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)); }

/*选择排序*/ @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)); }

/*插入排序*/ @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)); }

/*希尔排序*/ @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)); }

/*快速排序*/ @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; }

 //归并排序 @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]; }
 }

//基数排序 @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; }

//堆排序 @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); } }