[数据结构与算法]算法和数据结构体系班 01.认识复杂度、对数器、二分法

笔记链接：https://www.processon.com/view/link/613702207d9c081c75400c31?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJleHAiOjE2NjQ3Njc4ODQsImZpbGVHVUlEIjoiUXhYOXh5M1Z0VEdQV3BodCIsImlhdCI6MTY2NDc2NzU4NCwiaXNzIjoidXBsb2FkZXJfYWNjZXNzX3Jlc291cmNlIiwidXNlcklkIjotNzIxMzY0MzczNn0.uV8vDWPYvVhF57rQJs-rWXtgRWxoUWkYg8WfJxU2g08#outline（大佬记得笔记，后面只是我自己的查漏补缺）

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);
        }
    }
}

认识对数器

通过自己编写的随机测试用例来测试程序。