二分查找、分块查找、冒泡排序、选择排序、插入排序、快速排序

二分查找/折半查找

• 前提条件：数组中的数据必须是有序的

• 核心逻辑：每次排除一半的查找范围

• 优点：提高查找效率

• 代码

  public static int binarySearch(int[] arr, int num) {int start = 0;int end = arr.length - 1;while (start <= end) {int mid = (start + end) / 2;if (num == arr[mid]) {// 找到return mid;} else if (num > arr[mid]) {// num在mid索引的右边start = mid + 1;} else {// num在mid索引的左边end = mid - 1;}}return -1;
  }
  

分块查找

• 分块的原则

  • 前一块中的最大数据，小于后一块中所有的数据（块内无序，块间有序）
  • 块数数量一般等于数字个数开根号。比如：16个数字一般分为4块左右
  • 核心思路：先确定要查找的元素在哪一块，然后在块内挨个查找

• 代码

  package com.gen.test;public class BlockSearchDemo {public static void main(String[] args) {int[] arr = {16, 5, 9, 12, 21, 18,32, 23, 37, 26, 45, 34,50, 48, 61, 52, 73, 66};// 创建3个对象Block block1 = new Block(21, 0, 5);Block block2 = new Block(45, 6, 11);Block block3 = new Block(73, 12, 17);// 定义数组管理3个块的对象（索引表）Block[] blockArr = {block1, block2, block3};// 获取索引int index = getIndex(blockArr, arr, 66);System.out.println(index);}/*** 获取索引** @param blockArr 索引表* @param arr      数组* @param num      要查找的数字* @return 返回数字在arr中的索引，-1表示不存在*/private static int getIndex(Block[] blockArr, int[] arr, int num) {// 1.先确定在哪一个块中int indexBlock = findIndexBlock(blockArr, num);// num比所有块的最大值要大，不存在数组中if (indexBlock == -1) {return -1;}// 2.在块中查找numint startIndex = blockArr[indexBlock].getStartIndex();int endIndex = blockArr[indexBlock].getEndIndex();for (int i = startIndex; i <= endIndex; i++) {if (num == arr[i]) {return i;}}return -1;}/*** 查找num在哪一个块中** @param blockArr* @param num* @return 返回块索引，-1表示不存在*/private static int findIndexBlock(Block[] blockArr, int num) {for (int i = 0; i < blockArr.length; i++) {if (num <= blockArr[i].getMax()) {return i;}}return -1;}}class Block {// 最大值private int max;// 起始索引private int startIndex;// 结束索引private int endIndex;public Block() {}public Block(int max, int startIndex, int endIndex) {this.max = max;this.startIndex = startIndex;this.endIndex = endIndex;}public int getMax() {return max;}public void setMax(int max) {this.max = max;}public int getStartIndex() {return startIndex;}public void setStartIndex(int startIndex) {this.startIndex = startIndex;}public int getEndIndex() {return endIndex;}public void setEndIndex(int endIndex) {this.endIndex = endIndex;}
  }
  

冒泡排序

• 排序逻辑

  1. 相邻的元素两两比较，大的放右边，小的放左边
  2. 第一轮循环结束，最大值已经找到，在数组的最右边
  3. 第二轮循环只要在剩余的元素找最大值就可以了
  4. 第二轮循环结束，次大值已经确定，第三轮循环继续在剩余数据中循环

• 核心

  • 相邻的元素两两比较，大的放右边，小的放左边
  • 第一轮比较完毕之后，最大值就已经确定，第二轮可以少循环一次，后面以此类推
  • 如果数组中有n个数据，总共我们只要执行n-1轮的代码即可

• 代码

  public static void bubbleSort(int[] arr) {for (int i = 0; i < arr.length - 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;}}}
  }
  

选择排序

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

• 代码

  public static void selectSort(int[] arr) {for (int i = 0; i < arr.length - 1; 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;}}}
  }
  

插入排序

• 将0索引的元素到N索引的元素看作是有序的，把N+1索引的元素到最后一个当成是无序的

• 遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面

• N的范围：0~最大索引

  package com.gen.test;public class InsertSortDemo {public static void main(String[] args) {int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};// 1.找到无序索引起始位置int startIndex = -1;for (int i = 0; i < arr.length - 1; i++) {if (arr[i] > arr[i + 1]) {startIndex = i + 1;break;}}// 2.遍历无序元素，依次插入到有序元素中for (int i = startIndex; i < arr.length; i++) {// 记录当前要插入数据的索引int j = i;while (j > 0 && arr[j] < arr[j - 1]) {// 交换位置int temp = arr[j];arr[j] = arr[j - 1];arr[j - 1] = temp;j--;}}}
  }
  

快速排序

第一轮：把0索引的数字作为基准数，确定基准数在数组中正确的位置。比基准数小的全部在左边，比基准数大的全部在右边

/*** 快速排序** @param arr 要排序的数组* @param i   开始索引* @param j   结束索引*/
public static void quickSort(int[] arr, int i, int j) {// 递归出口if (i >= j) {return;}int start = i;int end = j;// 记录基准数int baseNum = arr[i];while (start != end) {// 从后往前找，找到比基准数小的元素while (true) {if (start >= end || arr[end] < baseNum) {break;}end--;}// 从前往后找，找到比基准数大的元素while (true) {if (start >= end || arr[start] > baseNum) {break;}start++;}// 把start和end元素进行交换int temp = arr[start];arr[start] = arr[end];arr[end] = temp;}// 基准数归位arr[i] = arr[start];arr[start] = baseNum;// 递归排序左边的数quickSort(arr, i, start - 1);// 递归排序右边的数quickSort(arr, start + 1, j);
}

排序总结

• 冒泡排序
  • 相邻的元素两两比较，小的放前面，大的放后面
• 选择排序
  • 从0索引开始，拿着每一个索引上的元素跟后面的元素依次比较，小的放前面，大的放后面，以此类推
• 插入排序
  • 将数组分为有序和无序两组，遍历无序数据，将元素插入有序序列中即可
• 快速排序
  • 将排序范围中的第一个数字作为基准数，再定义两个变量start、end
  • start从前往后找比基准数大的，end从后往前找比基准数小的
  • 找到之后交换start和end指向的元素，并循环这一过程，直到start和end处于同一个位置，该位置是基准数在数组中应存入的位置，再让基准数归位
  • 归位后的效果：基准数左边的，比基准数小，基准数右边的，比基准数大