冲刺大厂基础1

如果大家有什么问题，可以随时进行评论，每天晚上会进行解答。

如果大家把这个系列的代码掌握，可以达到一个很好的基础

1.选择排序

思路：每次从数组中选择一个最小值，依次放到数组[0…]位置。

public class Code01_SelectionSort {    public static void selectionSort(int[] arr){ if (arr == null || arr.length < 2){     return; } for(int i = 0; i < arr.length - 1; i++){     int minIndex = i;     for(int j = i + 1; j < arr.length - 1; j++){  minIndex = arr[j] < arr[minIndex] ? j : minIndex;     }     swap(arr, i, minIndex); }    }    public static void swap(int[] arr, int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;    }}

2.冒泡排序

思路：从数组0位置开始，依次两两相比，每一次比较，最大的数会放到最后。

public class Code02_BubbleSort {    public static void bubbleSort(int[] arr){ if(arr == null || arr.length < 2){     return; } for(int end = arr.length - 1 ; end > 0; end--){     for(int i = 0; i < end; i ++){  if(arr[i + 1] < arr[i]){      int temp = arr[i];      arr[i] = arr[i + 1];      arr[i + 1] = temp;  }     } }    }}

3.插入排序

思路：依次做到[0, 0]位置有序，[0, 1]位置有序，…,[0,N]位置有序。

public class Code03_InsertionSort {    public static void insertionSort(int[] arr){ if(arr == null || arr.length < 2){     return; } for(int end = 1; end < arr.length; end++){     for(int i = end - 1; i >= 0 ; i--){  if(arr[i + 1] < arr[i]){      int temp = arr[i + 1];      arr[i + 1] = arr[i];      arr[i] = temp;  }     } }    }}

4.指定升序（降序）数组中是否存在指定值

思路：如果遍历数组所有位置，时间复杂度为O(N)。可以注意到，给定数组为有序数组，所以，采用二分查找，可以做到时间复杂度为O(logN)。

public class Code04_BSExist {    public static boolean exist(int[] sortedArr, int num){ if(sortedArr == null || sortedArr.length == 0){     return false; } int L = 0; int R = sortedArr.length - 1; while(L < R){     int mid = L + ((R - L) >> 1);     if(sortedArr[mid] == num){  return true;     }else if(sortedArr[mid] < num){  L = mid + 1;     }else{  R = mid - 1;     } } return sortedArr[L] == num;    }}