java-冒泡，选择排序，二分查找

冒泡排序

-概述：数值小的上浮，数值大的下沉

-比较方法：int[] arr = {12,54,21,67,33}

                *第一次：arr[0]与arr[1]比较，arr[1]与arr[2]比较，arr[2]与arr[3]比较，arr[3]与arr[4]比较，共比较4次，arr[4]必然是最大的数

               *第二次：arr[0]与arr[1]比较，arr[1]与arr[2]比较，arr[2]与arr[3]比较，共比较3次，arr[3]是剩下数中最大的

               *第三次：arr[0]与arr[1]比较，arr[1]与arr[2]比较，共比较2次

               *第四次：arr[0]与arr[1]比较，只比较1次

-外循环：决定比较的次数

-内循环：决定相邻两个数比较的次数

public static void main(String[] args) { int[] arr = {12,54,21,67,33}; bubbleSort(arr); print(arr); } public static void bubbleSort(int[] arr){ for (int i = 0; i < arr.length; i++) { //控制比较次数,外循环只需要比较arr.length-1次就好了 for (int j = 0; j < arr.length-1-i; j++) { //-1为了防止溢出 if(arr[j]>arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } public static void print (int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]+" "); } }

48.选择排序

-概述：用一个索引位置的元素依次与其他索引位置的元素比较，小的在前，大的在后

-比较方法：int[] arr = {12,54,21,67,33}

                  *第一次：arr[0]分别与arr[1-4]比较，比较4次

                  *第二次：arr[1]分别与arr[2-4]比较，比较3次

                  *第三次：arr[2]分别a与rr[3-4]比较，比较2次

                  *第四次：arr[3]分别与arr[4]比较，比较1次

-图解：

public static void main(String[] args) { int[] arr = {12,54,21,67,33}; selectSort(arr); print(arr); } public static void selectSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { for (int j = i; j < arr.length; j++) { if(arr[i]>arr[j]){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } } public static void print (int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]+" "); } }

附上一个另外一种思路的C的选择排序

void test01(int *arr,int len) { for(int i=0;i<len-1;i++){ int min = i; for(int j=i+1;j<len;j++){ //每一轮都选出数组中最小的元素，并让它和当前未归序的首元素互换 if(arr[j]<arr[min]){ min = j; } } if(min!=i){ int temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } } }

49.二分查找

-使用前提：数组有序

-比较方法：

                *int left = 0;

                *int right = arr.length-1;

                *int middle = (left +right) / 2;

-图解：

public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("请输入你想要查询的值:"); int value = sc.nextInt(); int[] arr = {11,22,33,44,55,66}; int index = Method(arr,value); if(index!=-1){ System.out.println("所查询数字在数组中的索引是:"+index); }else{ System.out.println("所查询数字在数组中不存在！！"); } } public static int Method(int[] arr, int value) { int left = 0; int right = arr.length-1; while(left<=right){ int middle = (left + right) /2; //当找到value时，返回此时的索引 if(arr[middle] == value) return middle; else if(arr[middle] < value){ left = middle +1; }else{ right = middle -1; } } return -1; //当数组中不存在value时，返回-1 }