01.认识复杂度、对数器、二分法
常数时间操作（和数据量有关的操作）
不是常数时间的操作（和数据量无关）
选择排序：
在0-n-1个数中遍历，当找到最小的一个数，把它放到第0位
在1-n-1个数中遍历，当找到最小的一个数，把它放到第1位
在2-n-1个数中遍历，当找到最小的一个数，把它放到第2位。
public class code01_SelectionSort { public static void selectionSort(int [] arr){ if(arr==null || arr.length<2){ return ; } for(int i=0;i<arr.length;i++){ int minIndex=i; for(int j=i+1;j<arr.length;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; } public static void main(String[] args) { int []arr={3,5,8,45,1,2}; selectionSort(arr); for (int item: arr) { System.out.println(item); } } }
冒泡排序
比较相邻的两个数，把比较大的一个数往后排，这样排完一次过后最大的数就变成了最右边。
public class Code02_BubbleSort { public static void BubbleSort(int [] arr){ if(arr==null || arr.length<2){ return ; } for(int i=arr.length-1;i>0;i--){//循环N-1次就可以完成排序 for(int j=0;j<i;j++){//放置数组越界 if(arr[j]>arr[j+1]){ swap(arr,j,j+1); } } } } public static void swap(int [] arr,int m,int q){ int temp=arr[m]; arr[m]=arr[q]; arr[q]=temp; } public static void main(String[] args) { int []arr={3,5,8,45,1,100,2,1,10}; BubbleSort(arr); for (int item: arr) { System.out.println(item); } } }
插入排序 时间复杂度（o(n2)在数据流程最差的时候来表示这个数据)
首先保证下标0位置上有序，然后保证0，1位置上有序，如果后边的比前边的小，就让它前移。
直到保证在0到n上有序。
public class Code03_InsertionSort { public static void insertionSort(int []arr){ if(arr==null ||arr.length<2){ return ; } for(int i=1;i<arr.length;i++){ for(int j=i-1;j>=0&&arr[j]>arr[j+1];j--){ swap(arr,j,j+1); } } } public static void swap(int []arr,int i,int j){ arr[i]=arr[i]^arr[j]; arr[j]=arr[i]^arr[j]; arr[i]=arr[i]^arr[j]; } public static void main(String[] args) { int arr[]={3,4,2,1,78,7,15}; insertionSort(arr); for (int i: arr ) { System.out.println(i); } } }
认识对数器
通过自己编写的随机测试用例来测试程序。
