Java-排序~查找算法
1 冒泡排序
-
冒泡排序 : 将一组数据按照从小到大的顺序进行排序
-
冒泡排序原理 : 相邻元素两两作比较 , 大的元素往后放
/*冒泡排序 : 将一组数据按照从小到大的顺序进行排序冒泡排序的原理 : 相邻元素两两作比较 , 大的元素往后放需求 : 将数组中的元素 {3,5,2,1,4} 进行升序排序*/
public class SortDemo {public static void main(String[] args) {int[] arr = {3, 5, 2, 1, 4};for (int j = 0; j < arr.length - 1; j++) {// 比较的轮次// 每轮相邻元素比较的次数for (int i = 0; i < arr.length - 1 - j; i++) {if (arr[i] > arr[i + 1]) {int temp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = temp;}}System.out.println("第" + (j + 1) + "轮排序:" + Arrays.toString(arr));}}
}
2 选择排序
-
选择排序原理 : 它的工作原理是每一次从待排序的数据元素中选出最小的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到已排序序列的末尾。以此类推,直到全部待排序的数据元素排完。
-
注意事项 :
-
有n个元素,那么就要比较n-1轮次。
-
每一趟中都会选出一个最值元素,较前一趟少比较一次
/*选择排序工作原理 :它的工作原理是每一次从待排序的数据元素中选出最小的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到已排序序列的末尾。以此类推,直到全部待排序的数据元素排完。注意 :1 有n个元素,那么就要比较n-1趟。2 每一趟中都会选出一个最值元素,较前一趟少比较一次*/import java.util.Arrays;public class SortDemo {public static void main(String[] args) {int[] arr = {4, 1, 5, 3, 2};// 遍历数组for (int i = 0; i < arr.length - 1; i++) {// 记录当前元素和其之后所有元素的最小值索引int minIndex = i;int min = arr[i];for (int j = i; j < arr.length; j++) {if (arr[j] < min) {minIndex = j; // 把当前最小值的索引赋值给minIndexmin = arr[j];// 替换最小值}}if (i != minIndex) {int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}System.out.println(Arrays.toString(arr));} }
3 二分查找
-
原理 : 每次去掉一般的查找范围
-
前提 : 数组必须有序
package com.itheima.arraysort_demo.binarysearch_demo;/*二分查找 :原理 : 每次去掉一般的查找范围前提 : 数组必须有序步骤 :1,定义两个变量,表示要查找的范围。默认min = 0 , max = 最大索引2,循环查找,但是min <= max3,计算出mid的值4,判断mid位置的元素是否为要查找的元素,如果是直接返回对应索引5,如果要查找的值在mid的左半边,那么min值不变,max = mid -1.继续下次循环查找6,如果要查找的值在mid的右半边,那么max值不变,min = mid + 1.继续下次循环查找7,当 min > max 时,表示要查找的元素在数组中不存在,返回-1.*/ public class BinarySearchDemo {public static void main(String[] args) {int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};int i = binarySearch(arr, 8);System.out.println(i);}public static int binarySearch(int[] arr, int num) {// 定义两个变量,表示要查找的范围。默认min = 0 , max = 最大索引int max = arr.length - 1;int min = 0;// 2,循环查找,但是min <= maxwhile (min <= max) {// 3,计算出mid的值int mid = (min + max) / 2;if (arr[mid] == num) {// 4,判断mid位置的元素是否为要查找的元素,如果是直接返回对应索引return mid;} else if (arr[mid] > num) {// 5,如果要查找的值在mid的左半边,那么min值不变,max = mid -1.继续下次循环查找max = mid - 1;} else if (arr[mid] < num) {// 6,如果要查找的值在mid的右半边,那么max值不变,min = mid + 1.继续下次循环查找min = mid + 1;}}return -1;} }
-