type
status
date
slug
summary
tags
category
icon
password

一、快速排序

  • 算法思路:方法用的是递归,确定左边缘与右边缘,以及一个初始数,如果右边缘数大于最高初始数则左移,否则停下,之后再将左边缘与初始数比较如果比初始数小就右移,直到不符合条件,此时有两种情况①左=右,直接将指向的这个数与初始数替换。②左≠右,交换左右,然后重复左移右移直到①情况出现,然后会出现交换后的左边一块乱的,右边一块乱的。用上述思想完成也就是递归。
notion image
  • 递归的思想
package top.ltyzqhh.Annotation; import java.util.Arrays; public class QuickSort { public static void main(String[] args) { int[] a={324,234,532,1313,1,3,553}; System.out.println(Arrays.toString(a)); quickSort(a,0,a.length-1); System.out.println(Arrays.toString(a)); } public static void quickSort(int[] array,int left,int right){ if (array==null || array.length==0) { //当数值长度为零或者为空直接跳出 return; } if(left>right){ // 当左边缘数大于右边边缘 return; } int key =array[left]; int l=left; int r=right; while(l != r){ while (array[r]>=key && l<r){ //如果没有等号就会丢失key r--; } while (array[l]<=key && l<r){ l++; } if(l<r){ //防止乱放值,不然当l>r时候也换 int temp=array[r]; array[r]=array[l]; array[l]=temp; } } array[left]=array[l]; array[l]=key; quickSort(array,left,r-1); quickSort(array,l+1,right); } }

二、选择排序

  • 通过两个记录值来存储最小的数以及最小数的下标,之后遍历比较一遍后面的元素,如果发现比记录值更小的元素,就将记录值其赋值为该元素。知道最后,然后将第一个与最小的交换,如此往复
 
notion image
package top.ltyzqhh.Annotation; import java.util.Arrays; public class SelectSort { public static void main(String[] args) { int[] a={324,234,532,1313,1,3,553}; System.out.println(Arrays.toString(a)); selectSort(a); System.out.println(Arrays.toString(a)); } public static void selectSort(int[] array){ int min=0; int minindex=0; //外层循环,判断我们这个要走多少次; for (int i = 0; i <array.length-1 ; i++) { min=array[i];//记录最小的数 默认第一个数为最小值 minindex=i;//记录最小数的下标 //内层循环,将记录值与元素比较,如果记录值<该元素就将 该将记录值赋值为该元素。 for (int j = i+1; j <array.length ; j++) { if (min>array[j]) { min=array[j]; minindex=j; } } if(i!=minindex) { //将第一个值与最小值做比较。 array[minindex] = array[i]; array[i] = min; } } } }

三、冒泡排序

  • 冒泡排序 1. 比较数组中,两个相邻的元素,如果第一个比第二个打,交换位置 2. 每一次比较,都会产生出一个最大,或者最小的数字; 3. 下一轮则可以少一次排序! 4. 一次循环直到结束
notion image
package top.ltyzqhh.Annotation; import java.util.Arrays; public class Array { public static void main(String[] args) { int[] a={324,234,532,1313,1,3,553}; System.out.println(Arrays.toString(a)); sort(a); } //冒泡排序 //1. 比较数组中,两个相邻的元素,如果第一个比第二个打,交换位置 //2. 每一次比较,都会产生出一个最大,或者最小的数字; //3. 下一轮则可以少一次排序! //4。一次循环直到结束 public static void sort(int[] array){ //临时变量 int temp=0; //外层循环,判断我们这个要走多少次; for (int i = 0; i <array.length-1 ; i++) { boolean flag =false; //通过flag标示位减少没有意义的比较 //内层循环,比较判断两个数,如果一个数,比第二个数大,则交换位置 for (int j = 0; j <array.length-1-i ; j++) { if (array[j]>array[j+1]) { temp=array[j]; array[j]=array[j+1]; array[j+1]=temp; flag=true; } } if (flag==false){ break; } } /*for (int i = 0; i <array.length ; i++) { System.out.print(array[i]+", "); }*/ System.out.println(Arrays.toString(array)); } }

四、插入排序

  • 插入排序
    • 把第一个数当做有序数列,第二个到最后当做无序数列,开始扫描比较,每次将选择有序数列后一个数开始与有序数列比较,当比较到当前数大于时候有序数时,则插入,循环往复。
notion image
package top.ltyzqhh.Annotation; import java.util.Arrays; public class InsertionSort { public static void main(String[] args) { int[] a={234,334,532,1313,1,3,553}; System.out.println(Arrays.toString(a)); insertionSort(a); System.out.println(Arrays.toString(a)); } public static void insertionSort(int[] array){ //外层循环,判断我们这个要走多少次; for (int i = 1; i <array.length; i++) { int temp=array[i]; int tempindex=i; //内层循环,判断如果这个数比前一个小的话则交换直到不能交换为止 // 这个tempindex-1>=0条件要先于temp<array[tempindex-1],不然会先执行temp<array[tempindex-1],导致坐标越界 while( tempindex-1>=0 && temp<array[tempindex-1] ){ array[tempindex]=array[tempindex-1]; tempindex--; } array[tempindex] =temp; } } }

五、希尔排序

 
  • 1959年Shell发明,第一个突破O(n2)的排序算法,是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序
 
notion image
先分组再排序
package top.ltyzqhh.Annotation; import java.util.Arrays; public class ShellSort { public static void main(String[] args) { int[] a={324,234,532,1313,1,3,553}; System.out.println(Arrays.toString(a)); shellSort(a); System.out.println(Arrays.toString(a)); } /* public static void insertionSort(int[] array){ //外层循环,判断我们这个要走多少次; for (int i = 1; i <array.length; i++) { int temp=array[i]; int tempindex=i; //内层循环,判断如果这个数比前一个小的话则交换直到不能交换为止 // 这个tempindex-1>=0条件要先于temp<array[tempindex-1],不然会先执行temp<array[tempindex-1],导致坐标越界 while( tempindex-1>=0 && temp<array[tempindex-1] ){ array[tempindex]=array[tempindex-1]; tempindex--; } array[tempindex] =temp; } }*/ public static void shellSort(int[] array){ //步长 for (int step= array.length/2 ; step >0 ; step/=2) { for (int i=step;i<array.length;i++) { int insertIndex =i; int insertValue=array[i]; while( insertIndex-step>=0 && insertValue<array[insertIndex-step] ){ array[insertIndex]=array[insertIndex-step]; insertIndex-=step; } array[insertIndex] =insertValue; } } } }

六、归并排序

  • 算法思路:先分到不可分为止(有点像先序遍历),再比较排序合并
notion image
package top.ltyzqhh.Annotation; import java.util.Arrays; public class MergeSort { public static void main(String[] args) { int[] a={1324,234,532,1313,1,3,553}; int[] temp= new int[a.length]; System.out.println(Arrays.toString(a)); mergeSort(a,0,a.length-1,temp); System.out.println(Arrays.toString(a)); } public static void mergeSort(int[] array,int left,int right,int[] temp){ if (left<right){ int mid=(left+right)/2; mergeSort(array,0,mid,temp);//将左边部分继续分 mergeSort(array,mid+1,right,temp);//将右边部分继续分 merge(array,left,mid,right,temp);//合 } } public static void merge(int[] array,int left,int mid, int right,int[] temp){ int i=left; int j=mid+1; int t=0;//表示临时数组的下标索引 while (i<=mid && j<=right){ if (array[i]<=array[j]){ temp[t]=array[i]; i++; t++; }else { temp[t]=array[j]; j++; t++; } } //如果左边的部分没有合并,则接着i继续合并 while (i<=mid){ temp[t]=array[i]; t++; i++; } //如果右边的部分没有合并,则接着j继续合并 while (j<=right){ temp[t]=array[j]; t++; j++; } //接着将temp里面的数组填充到指定位置 t=0; int tempLeft=left; while (tempLeft<=right) { array[tempLeft]=temp[t]; t++; tempLeft++; } } }

七、基数排序

算法思路:比较数量级,从个位比较到这组数中数量级最高的级数。
notion image
package top.ltyzqhh.Annotation; import java.util.Arrays; public class RedixSort { public static void main(String[] args) { int[] a={1324,234,532,1313,1,3,553}; System.out.println(Arrays.toString(a)); redixSort(a); System.out.println(Arrays.toString(a)); } public static void redixSort(int[] array){ int[][] bucket=new int[10][array.length-1];//桶里面所存的具体数值 int[] bucketElementCouonts = new int[10];//每个桶所存的元素个数 int max= array[0]; //求出最大的数 for (int i = 0; i <array.length ; i++) { if (max<array[i]) max=array[i]; } int maxCount=(max+"").length();//最大位数 for (int i = 0; i <maxCount ; i++) { //把数组中的数都放在桶里 for (int j = 0; j <array.length ; j++) { int value =array[j]/(int) Math.pow(10,i)%10; bucket[value][bucketElementCouonts[value]]=array[j]; bucketElementCouonts[value]++; } int index=0; for (int j = 0; j <bucketElementCouonts.length ; j++) {//遍历每个桶 if (bucketElementCouonts[j]!=0){ for (int k = 0; k <bucketElementCouonts[j] ; k++) {//遍历每个桶的元素 array[index]=bucket[j][k]; index++; } } bucketElementCouonts[j]=0;//清空桶,便于后面排序 } } } }
双亲委派机制(类加载机制)写一个Mybatis测试