网站优化西安,工程建设专业,考研资料找微信hyhyk1推广可以,wordpress自动换行声明#xff1a;该专栏本人重新过一遍java知识点时候的笔记汇总#xff0c;主要是每天的知识点题解#xff0c;算是让自己巩固复习#xff0c;也希望能给初学的朋友们一点帮助#xff0c;大佬们不喜勿喷(抱拳了老铁#xff01;) Java学习day05#xff1a;排序#xff0…声明该专栏本人重新过一遍java知识点时候的笔记汇总主要是每天的知识点题解算是让自己巩固复习也希望能给初学的朋友们一点帮助大佬们不喜勿喷(抱拳了老铁) Java学习day05排序选择、冒泡、快速、二分、杨辉三角
一、选择排序
1.原理 找到最小值的索引然后和第1个数据进行交换。再找除了第一个数据以外的最小值的索引。然后和第二个数据交换 2.代码示例
public class Demo1 {public static void main(String[] args) {//选择排序int[] arr {3,4,1,5,2};/*** i0 04 true minIndex0 * 进入内层的for循环* j0 05 true arr[0] arr[0]false j* j1 15 true arr[0] arr[1] false j* j2 25 true arr[0]arr[2]true minIndex2 j* j3 35 true arr[2]arr[3]fasle j* j4 45 true arr[2]arr[4] fasle j* j5 55fasle循环结束* 执行交换代码* temp arr[2]1* arr[2] arr[0] {3,4,3,5,2}* arr[0] 1 {1,4,3,5,2} i* i1 14 true minIndex 1* ......* */for (int i 0; i arr.length - 1; i) {//控制的是轮数int minIndex i;for (int j i; j arr.length; j) {//遍历咱们的数据找到最小值的索引的if (arr[minIndex] arr[j]) {minIndex j;}}//交换位置int temp arr[minIndex];arr[minIndex] arr[i];arr[i] temp;}System.out.println(Arrays.toString(arr));}} 代码写的非常详细大家把代码看懂就好
二、冒泡排序 1.原理 从小到大排序比较两个相邻的数据如果左边比右边元素大就交换位置。如果左边比右边小就不变 2.代码示例
public class Demo2 {public static void main(String[] args) {//冒泡 排序和索引没有关系int[] arr {1,5,2,3};for (int i 0; i arr.length - 1; i) {//最内层的循环两两比较交换位置//4-1-ii0 第1轮 3次//4-1-ii1 第2轮 2次//4-1-ii2 第3轮 1次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;}}}System.out.println(Arrays.toString(arr));}
}
3.二者比较
这里要提的一点区分选择排序和冒泡排序选择排序是每次遍历所有数据找出最大的那个并和第一个交换所以代码里是内层for循环结束后在外层for循环里交换而冒泡排序则是每次把相邻的两个数进行比较如果前面的大则交换位置这样比较下去最终最大的那个数就会冒出来这也就是为什么冒泡是在内存for循环里交换并且变量j的初始值为0而不是i。
三、快速排序
1.原理 快速排序是一种常用的排序算法它的基本思想是通过分治的方法将一个大问题拆分成若干个小问题来解决选择一个基准元素通常选择数组的第一个元素将数组分成两部分一部分小于基准元素一部分大于基准元素对这两部分分别进行快速排序递归地重复以上步骤直到每个子数组只有一个元素或者为空。 2.代码示例
举个例子假设我们要对数组[5, 3, 8, 2, 1, 9]进行快速排序选择基准元素为5将数组分成[3, 2, 1]和[8, 9]两部分对两部分分别进行快速排序得到[1, 2, 3]和[8, 9]最后得到排序后的数组为[1, 2, 3, 5, 8, 9]
public class QuickSort {public static void main(String[] args) {int[] arr {5, 3, 8, 2, 1, 9};quickSort(arr, 0, arr.length - 1);System.out.println(排序后的数组);for (int num : arr) {System.out.print(num );}}public static void quickSort(int[] arr, int low, int high) {if (low high) {int pivot partition(arr, low, high); // 获取基准元素的位置quickSort(arr, low, pivot - 1); // 对基准元素左边的子数组进行快速排序quickSort(arr, pivot 1, high); // 对基准元素右边的子数组进行快速排序}}public static int partition(int[] arr, int low, int high) {int pivot arr[low]; // 选择第一个元素作为基准元素while (low high) {while (low high arr[high] pivot) {high--;}arr[low] arr[high]; // 将比基准元素小的元素移到低位while (low high arr[low] pivot) {low;}arr[high] arr[low]; // 将比基准元素大的元素移到高位}arr[low] pivot; // 将基准元素放到最终位置return low; // 返回基准元素的位置}
}
另外拓展一小点java面向对象里封装了sort方法该方法底层就是快速排序
int[] arrnew int[]{123,523,1,4,244,14231,122};
Arrays.sort(arr);//sort的底层是快排效率最高
System.out.println(Arrays.toString(arr));
四、杨辉三角
1.什么是杨辉三角 杨辉三角是一个由数字排列成的三角形其中每个数字是它上方两个数字的和。它的第n行有n个数字第一个和最后一个数字都是1其他数字是上一行相邻两个数字的和。 举个例子下面是一个4行的杨辉三角 1 1 1 1 2 1 1 3 3 1 2.代码示例
如何生成指定行数的杨辉三角通过使用二维数组来存储杨辉三角的每个数字然后利用动态规划的思想根据每个数字等于上一行两个相邻数字的和的规律来生成杨辉三角。
public class PascalTriangle {public static void main(String[] args) {int numRows 5;generatePascalTriangle(numRows);}public static void generatePascalTriangle(int numRows) {int[][] triangle new int[numRows][];for (int i 0; i numRows; i) {triangle[i] new int[i 1];triangle[i][0] 1; // 每行的第一个数字为1triangle[i][i] 1; // 每行的最后一个数字为1for (int j 1; j i; j) {triangle[i][j] triangle[i - 1][j - 1] triangle[i - 1][j]; // 每个数字等于上一行两个相邻数字的和}}// 打印杨辉三角for (int i 0; i numRows; i) {for (int j 0; j i; j) {System.out.print(triangle[i][j] );}System.out.println();}}
} 五、二分法查找算法
1.原理 二分法查找算法是一种高效的查找算法它适用于已排序的数组。如何使用二分法查找算法在有序数组中查找指定的目标值通过不断缩小查找范围将数组分成两部分并与目标值进行比较从而确定目标值在数组中的位置。如果找到目标值返回它在数组中的索引如果找不到目标值返回-1。 2.具体步骤
具体步骤如下 1)选择数组的中间元素 2)如果中间元素等于目标值则查找成功 3)如果中间元素大于目标值则在数组的前半部分继续查找 4)如果中间元素小于目标值则在数组的后半部分继续查找 5)重复以上步骤直到找到目标值或者数组为空
3.代码示例
举个例子假设我们要在有序数组[1, 2, 3, 5, 8, 9]中查找数字5选择中间元素为3由于3小于5所以在数组的后半部分[5, 8, 9]中继续查找选择中间元素为8由于8大于5所以在数组的前半部分[5]中继续查找找到目标值5查找成功
public class BinarySearch {public static void main(String[] args) {int[] arr {1, 2, 3, 5, 8, 9};int target 5;int index binarySearch(arr, target);if (index ! -1) {System.out.println(目标值 target 在数组中的索引为 index);} else {System.out.println(目标值 target 不在数组中);}}public static int binarySearch(int[] arr, int target) {int low 0;int high arr.length - 1;while (low high) {int mid (low high) / 2;if (arr[mid] target) {return mid; // 找到目标值返回索引} else if (arr[mid] target) {low mid 1; // 目标值在数组的后半部分} else {high mid - 1; // 目标值在数组的前半部分}}return -1; // 目标值不在数组中}
} 今天没有习题理解为主其中选择排序和冒泡排序是现在必须要理解的至于后面的快速排序、杨辉三角、二分查找等则先理解后面还会再次讲解。
