中国建设部门官方网站,公众号平台登陆,php网站制作流程,怎样安装免费的wordpress目录
冒泡排序算法
冒泡排序的基础算法
冒泡排序的优化算法
二分法查找 冒泡排序算法 冒泡排序是最常用的排序算法#xff0c;在笔试中也非常常见#xff0c;能手写出冒泡排序算法可以说是 基本的素养。
冒泡排序的基础算法 冒泡排序算法重复地走访过要排序的数列#…目录
冒泡排序算法
冒泡排序的基础算法
冒泡排序的优化算法
二分法查找 冒泡排序算法 冒泡排序是最常用的排序算法在笔试中也非常常见能手写出冒泡排序算法可以说是 基本的素养。
冒泡排序的基础算法 冒泡排序算法重复地走访过要排序的数列一次比较两个元素如果他们的顺序错误就 把他们交换过来这样越大的元素会经由交换慢慢“浮”到数列的顶端。 冒泡排序算法的运作如下
比较相邻的元素。如果第一个比第二个大就交换他们两个对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。在这一点最 后的元素应该会是最大的数针对所有的元素重复以上的步骤除了最后一个持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较
import java.util.Arrays;public class Test {public static void main(String[] args) {int[ ] values { 3, 1, 6, 2, 9, 0, 7, 4, 5, 8 };bubbleSort(values);System.out.println(Arrays.toString(values));}public static void bubbleSort(int[ ] values) {int temp;for (int i 0; i values.length; i) {for (int j 0; j values.length - 1 - i; j) {if (values[j] values[j 1]) {temp values[j];values[j] values[j 1];values[j 1] temp;}}}}
} 冒泡排序的优化算法 们可以把冒泡排序的算法优化一下
整个数列分成两部分前面是无序数列后面是有序数列。初始状态下整个数列都是无序的有序数列是空。每一趟循环可以让无序数列中最大数排到最后也就是说有序数列的元素个数增加 1也就是不用再去顾及有序序列。每一趟循环都从数列的第一个元素开始进行比较依次比较相邻的两个元素比较到 无序数列的末尾即可而不是数列的末尾如果前一个大于后一个交换。判断每一趟是否发生了数组元素的交换如果没有发生则说明此时数组已经有序 无需再进行后续趟数的比较了。此时可以中止比较。
import java.util.Arrays;public class Test {public static void main(String[] args) {int[ ] values { 3, 1, 6, 2, 9, 0, 7, 4, 5, 8 };bubbleSort(values);System.out.println(Arrays.toString(values));}public static void bubbleSort(int[ ] values) {int temp;int i;// 外层循环n个元素排序则至多需要n-1趟循环for (i 0; i values.length - 1; i) {// 定义一个布尔类型的变量标记数组是否已达到有序状态boolean flag true;/*内层循环每一趟循环都从数列的前两个元素开始进行比较比较到无序数组的最后*/for (int j 0; j values.length - 1 - i; j) {// 如果前一个元素大于后一个元素则交换两元素的值if (values[j] values[j 1]) {temp values[j];values[j] values[j 1];values[j 1] temp;//本趟发生了交换表明该数组在本趟处于无序状态需要继续比较flag false;}}//根据标记量的值判断数组是否有序如果有序则退出无序则继续循环。if (flag) {break;}}}
} 二分法查找 二分法检索binary search又称折半检索二分法检索的基本思想是设数组中的元素 从小到大有序地存放在数组array中首先将给定值 key 与数组中间位置上元素的关键码 (key)比较如果相等则检索成功 否则若 key 小则在数组前半部分中继续进行二分法检索; 若 key 大则在数组后半部分中继续进行二分法检索。 这样经过一次比较就缩小一半的检索区间如此进行下去直到检索成功或检索失败。 二分法检索是一种效率较高的检索方法。比如我们要在数组[7, 8, 9, 10, 12, 20, 30, 40, 50, 80, 100]中查询到 10 元素过程如下 import java.util.Arrays;public class Test {public static void main(String[] args) {int[ ] arr { 30,20,50,10,80,9,7,12,100,40,8};int searchWord 20; // 所要查找的数Arrays.sort(arr); //二分法查找之前一定要对数组元素排序System.out.println(Arrays.toString(arr));System.out.println(searchWord元素的索引binarySearch(arr,searchWord));}public static int binarySearch(int[ ] array, int value){int low 0;int high array.length - 1;while(low high){int middle (low high) / 2;if(value array[middle]){return middle; //返回查询到的索引位置}if(value array[middle]){low middle 1;}if(value array[middle]){high middle - 1;}}return -1; //上面循环完毕说明未找到返回-1}
}
