查找算法和排序算法

1.基本查找

在数组或集合中挨个元素查找需要的元素

1.1需求一:

需求:定义一个方法利用基本查找,查询某个元素是否存在
数据如下：{131，127，147，81，103，23，7，79}

public static void main(String[] args) {  int[] arr1 = {131,127,147,81,103,23,7,79};  System.out.println(Check(arr1,131));  }  public static boolean Check(int[] arr,int num){  for (int i = 0; i < arr.length; i++) {  if(arr[i] == num){  return true;  }  }  return false;  }  
}

1.2需求二:

需求：定义一个方法利用基本查找，查询某个元素在数组中的索引
要求：需要考虑数组中元素有重复的可能性 {131,127,147,81,103,23,7,79,81}
查找81，想要返回的是所有索引3 8
==//如果需要返回多个数据,则把数据放在数组或集合中,将数组或集合返回就可以了 ==

public static void main(String[] args) int[] arr = {131,127,147,81,103,23,7,79,81};  ArrayList<Integer> list1 = new ArrayList<>();  list1 = Check(arr,81);  for (int i = 0; i < list1.size(); i++) {  System.out.print(list1.get(i)+" ");  }  
}//如果需要返回多个数据,则把数据放在数组或集合中,将数组或集合返回就可以了  
public static ArrayList<Integer> Check(int[] arr, int num){  //创建一个新的集合来放多个索引  ArrayList<Integer> list = new ArrayList<>();  for (int i = 0; i < arr.length; i++) {  if(arr[i] == num){  list.add(i);  }  }  return list;  
}

2.二分查找

前提条件: 数组中的数据必须是有序的
核心逻辑: 每次排除一半的查找范围
1)min和max表示当前要查找的范围
2)mid是在min和max中间的
3)如果要查找的元素在mid的左边，缩小范围时，min不变，max等于mid减1
4)如果要查找的元素在mid的右边，缩小范围时，max不变，min等于mid加 1

 int[] arr = {7,23,79,81,103,127,131,147};  System.out.println(Check(arr,79));  
}  
public static int Check(int[] arr ,int num){  int min = 0;  int max = arr.length - 1;  while(true){  if(min > max){  return -1;  }  //找到min和max的中间位置  int mid = (min + max) / 2;  if(arr[mid] > num){  max = mid - 1;  }else if(arr[mid] < num){  min = mid + 1;  }else{  return mid;  }  }

3.分块查找

分块的原则1：前一块中的最大数据，小于后一块中所有的数据（块内无序，块间有序）
分块的原则2：块数数量一般等于数字的个数开根号。比如：16个数字一般分为4块左右。
核心思路：先确定要查找的元素在哪一块，然后在块内挨个查找。
1)创建标准的javaBean类,每一块创建一个对象,再把对象放进数组中

//javaBean类里需要存在的三个成员变量private int max;//每一块中的最大值  private int startIndex;//块的起始索引  private int endIndex;//块的结束索引

  int[] arr={16,5,9,12,21,18,//前一块的最大值必须比后一块的所有值都要小  32,23,37,26,45,34,  50,48,61,52,73,66};  
//      System.out.println(arr.length);//arr的长度为18,至少将arr分成4块  //创建块的对象  Block b1 = new Block(21,0,5);  Block b2 = new Block(45,6,11);  Block b3 = new Block(73,12,17);  //把三个对象放进数组里  Block[] b = {b1,b2,b3};  //定义一个变量来记录需要查找的元素  int num = 45;  System.out.println(getIndex(b,num,arr));

2)定义一个方法找到元素所在的块的下标

//先确定num在哪一块中  public static int getIndexBlock(Block[] b,int num){  
//        Block b1 = new Block(21,0,5);-----0  
//        Block b2 = new Block(45,6,11);----1  
//        Block b3 = new Block(73,12,17);---2  //从0索引开始遍历b数组,如果num小于max,则表示num在这一块当中  for (int i = 0; i < b.length; i++) {  if(num <= b[i].getMax()){  return i;//返回块的下标  }  }  return -1;//查找的数据不在表中  }

3)从块的下标中找到对应块的开始索引和节数索引,遍历块并找到元素

//确定了num在哪一块中,再去那块中寻找num的索引  
public static int getIndex(Block[] b,int num,int[] arr){  int indexBlock = getIndexBlock(b,num);//得到返回的块的下标  if(indexBlock == -1){//返回-1则表示数据不在数组中  return -1;  }else{  int startIndex = b[indexBlock].getStartIndex();//得到块的开始索引  int endIndex = b[indexBlock].getEndIndex();//得到块的结束索引  for (int i = startIndex; i <= endIndex; i++) {//从开始索引遍历到结束索引  if(arr[i] == num){  return i;  }  }  return -1;  }

3.1分块查找的扩展

主要用于没有规律的数据
1)分块时,块与块之间不能有交集
2)分块查找的拓展比正常的分块查找的javaBean类多了一个成员变量
private int min;

4.冒泡排序

冒泡排序: 相邻的数据两两比较,小的放前面,大的放后面

public static void main(String[] args) {//冒泡排序  int[] arr={5,3,2,1,4};  //外循环,表示要执行多少轮,如果有n个数据,则执行n-1轮  for (int i = 0; i < arr.length; i++) {  //内循环:每一轮中比较数据找到当前的最大值  //-1 为了防止索引越界  //-i 为了体改效率,每一轮执行的次数应该比上一轮少一次  for (int j = 0; j < arr.length - 1 - i; j++) {  if(arr[j] > arr[j+1]){  int temp = arr[j];  arr[j] = arr[j + 1];  arr[j + 1] = temp;  }  }  }  for (int i = 0; i < arr.length; i++) {//遍历数组,看冒泡排序是否成功  System.out.print(arr[i] + " ");//1 2 3 4 5  }  
}

5.选择排序

从0索引开始，拿着每一个索引上的元素跟后面的元素依次比较,小的放前面，大的放后面，以此类推。

    int[] arr={5,3,2,1,4};  //外循环:几轮  for (int i = 0; i < arr.length; i++) {  //内循环,拿着i和i后面的数据进行比较和交换  for (int j = i + 1; j < arr.length ; j++) {  if(arr[i] > arr[j]){  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  }  }  
}

6.插入排序

将0索引的元素到n索引的元素看作是有序的,把n+1索引的元素到最后一个当成是无序的。遍历无序的数据,将遍历的元素插入有序序列中的适当位置,如果遇到相同数据,则插在后面

1.找到无序的那一组数组是从哪个索引开始的

//思路:如果前一个数据大于后一个数据,则该后一个数据就是无序数组的开始  //例:44>38 则38就是无序数组的开始 44就是有序数组的结束  for (int i = 0; i < arr.length; i++) {  if(arr[i] > arr[i + 1]){  System.out.println(i);//1 表示有序数组到1索引就结束了  break;  }  }  
}

2.//把无序数组的数据插入到有序数组中

//遍历从startIndex开始到最后一个元素,依次得到无序的那一个数组中的每个元素  
for (int i = startIndex; i < arr.length; i++) {  for (int j = 0 ; j <= i; j++) {  if(arr[j] > arr[i]){//arr[j]为有序数组的数据 arr[i]为无序数组的数据  //若arr[j]>arr[i] 则为后面的数据大于前面的数据 需要交换位置  int temp = arr[j];  arr[j] = arr[i];  arr[i] = temp;  }  }  
}  
for (int i = 0; i < arr.length; i++) {  System.out.print(arr[i] + " ");  
}

7.快速排序(递归算法)

递归: 自己调用自己
递归一定要有出口,否则就会内存溢出
第一轮：把0索引的数字作为基准数，确定基准数在数组中正确的位置
比基准数小的全部在左边，比基准数大的全部在右边。

 public static void main(String[] args) {  
//        快速排序：  
//        第一轮：以0索引的数字为基准数，确定基准数在数组中正确的位置。  
//        比基准数小的全部在左边，比基准数大的全部在右边。  
//        后面以此类推  int[] arr={6,1,2,7,9,3,4,5,10,8};  quickSort(arr,0,arr.length - 1);  for (int i = 0; i < arr.length; i++) {  System.out.print(arr[i] + " ");  }  }  //参数一:我们要排序的数组  //参数二:要排序的数组的起始索引  //参数三,要排序数组的结束索引  public static void quickSort(int[] arr,int i,int j){  int start = i;//记录数组的起始位置  int end = j;  int baseNumber = arr[i];  while(start != end){  //用end ,从后开始往前找比基准数小的数字  while(true){  if(end <= start || arr[end] < baseNumber){  break;  }  end--;  }  //用start,从前开始往后找比基准数大的数字  while(true){  if(end <= start || arr[start] > baseNumber){//找到值后结束循环,并挪动start指向的位置  break;  }  start++;  }  //把end和start元素进行交换  int temp = arr[start];  arr[start] = arr[end];  arr[end] = temp;  }  //基准数归位,将start下标的和基准数交换位置  int temp = arr[start];  arr[start] = arr[i];  arr[i] = temp;  
//        int temp = arr[start];  
//        arr[start] = baseNumber;  
//        baseNumber = temp;  //虽然arr[i]=baseNumber 此处改变的事baseNumber的值,并没有改变数组中的基准值,所以要用arr[i]来实现交换  }

第二轮,基准值左边的使用递归重新定义基准值和进行快速排序,右边同理\