数组的排序算法

1.冒泡排序算法/*** 冒泡排序算法* 90,8,7,6,100* 第一次大循环参与排序的数据90,8,7,6,100 [1,4]* 8,90,7,6,100* 8,7,90,6,100* 8,7,6,90,100* 8,7,6,90,100** 第二次大循环参与排序的数据8,7,6,90 [2,3]* 7,8,6,90* 7,6,8,90* 7,6,8,90** 第三次大循环参与排序的数据7,6,8 [3,2]* 6,7,8* 6,7,8** 第四次大循环:参与排序的数据6,7 [4,1]* 6,7*/package com.bit.array; import java.util.Arrays; public class BubbleSort { public static void main(String[] args) { int[] arr{90,8,7,6,100}; for (int i 0; i arr.length - 1; i) { for (int j 0; j arr.length - i - 1; j) { if (arr[j]arr[j1]){ //交换一次位置 swap(arr,j,j1); } } } System.out.println(Arrays.toString(arr)); } private static void swap(int[] arr, int i, int j) { int tmparr[i]; arr[i]arr[j]; arr[j]tmp; } }优化后的冒泡排序package com.bit.array; import java.util.Arrays; public class BubbleSort2 { public static void main(String[] args) { //int[] arr{90,8,7,6,100}; int[] arr{1,2,3,4,5}; for (int i 0; i arr.length - 1; i) { //假设剩下的元素都不用排序了 // System.out.println(); boolean flagtrue; for (int j 0; j arr.length - i - 1; j) { if (arr[j]arr[j1]){ flagfalse; //交换一次位置 swap(arr,j,j1); } } if (flag){ break; } } System.out.println(Arrays.toString(arr)); } private static void swap(int[] arr, int i, int j) { int tmparr[i]; arr[i]arr[j]; arr[j]tmp; } }2.选择排序算法/*** 需要排序的90,8,7,6,100 采用选择排序的方式* 1.冒泡排序的缺点很多次的交换没有意义效率较低* 2.选择排序减少交换次数提高效率但实际上元素之间的比较次数和冒泡排序是一样的* 3.选择排序的原理* 第一次大循环参与比较的数据90,8,7,6,100 (参与比较的数据中最左侧元素下标0)* 6,8,7,90,100** 第二次大循环参与比较的数据8,7,90,100 (参与比较的数据中最左侧元素下标1)* 7,8,90,100** 第三次大循环参与比较的数据8,90,100 (参与比较的数据中最左侧元素下标2)* 8,90,100** 第四次大循环参与比较的数据90,100 (参与比较的数据中最左侧元素下标3)* 90,100* 4.描述一下选择排序的固定算法* 找出“参与比较的这些数据中”最小的元素那最小的元素和“参与比较的这些数据中”的最左侧元素交换位置。*/package com.bit.array; import java.util.Arrays; public class SelectSort { public static void main(String[] args) { int[] arr{90,8,7,6,100}; for (int i 0; i arr.length - 1; i) { //i 下标 0 1 2 3 //i永远是参与比较的这对数据中最左边那个元素的下标 //假设最左边的元素最小 int mini; for (int j i1; j arr.length; j) { if (arr[min]arr[j]){ minj; } } if (min!i){ swap(arr,min,i); } } System.out.println(Arrays.toString(arr)); } private static void swap(int[] arr, int i, int j) { int tmparr[i]; arr[i]arr[j]; arr[j]tmp; } }3.二分算法前提数组元素必须是排好序的有“二段性”思路定义两个变量记录最小索引和最大索引折半的动作不止一次应该使用循环 条件while(minmax)循环中计算出中间索引加入判断元素如果大于中间元素minmid1;元素如果小于中间元素maxmid-1;元素如果等于中间元素将索引返回(mid)细节处理循环条件 为什么是 minmax 意味着区间内有未比较的元素而不是minmax? minmax意味着minmax他们指向的元素也会参与比较 minmax只意味着mid 指向的元素参与比较(minmax)/2有没有问题假设数组非常大会越界class Solution { public int search(int[] nums, int target) { //1.定义两个变量记录最小索引和最大索引 int min0; int maxnums.length-1; //2.折半的动作不止一次应该使用循环 while(minmax){ //3.计算中间索引 int midleft(right-left)/2; //4.比对 if(targetnums[mid]){ minmid1; }else if(targetnums[mid]){ maxmid-1; }else{ return mid; } } //5.没找到返回-1 return -1; } }