二.排序

一.冒泡排序

1. 定义俩个变量，外层变量i(循环轮数)与内层变量j(比较的次数)
2. 遍历每一次外层循环时集合的数据（其中每次遍历数量是递减的，因为当你经过一次冒泡后已经排好了一个元素），找到最大元素，其中，如果前一个元素大于后一个元素，那么二者交换
3. 外层进行下一次循环

public class BubbleDemo1 {
    public static void main(String[] args) {
        int[] arr = { 2, 4, 5, 3, 1 };
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}

二.选择排序

与冒泡排序有些类似，但是还是有不同，以下列举部分不同(通义辅助)

public class SelectionDemo1 {
    public static void main(String[] args) {
        int[] arr = { 2, 5, 1, 4, 3 };
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}

三.插入排序

在数列中找到无序数列开始的位置（一般从-1开始查找然后依次增加查找变量）

public class InsertDemo1 {
    public static void main(String[] args) {
        int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
        int startIndex = -1;//从-1开始查找无序位置，如果本身是有序的，那么-1就是无效索引，将不会执行排序的代码
        for(int i = 0; i < arr.length; i++) {//遍历数组，找到无序开始的位置
            if (arr[i] < arr[i + 1]) {
                startIndex = i + 1;
                break;
            }
        }

        for (int i = startIndex; i < arr.length; i++) {//从上方拿到无序索引，然后排序无序的部分
            int j = i;
            while (j > 0 && arr[j] < arr[j - 1]) {//如果后一个比前一个大，那么就交换位置
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                j--;
            }
        }

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }


    }

}

四.快速排序

快速排序用了递归

1. 选择基准值（Pivot）：从数组中选择一个元素作为基准值，通常选择第一个元素或最后一个元素
2. 分区（Partition）：重新排列数组，使得比基准值小的元素放在基准值左边，比基准值大的元素放在基准值右边
3. 递归排序：对基准值左右两个子数组分别进行快速排序

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {6,1,2,7,9,3,4,5,10,8};
        quickSort(arr, 0, arr.length - 1);

        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

    }

    public static void quickSort(int[] arr, int i, int j) {
        int start = i;
        int end = j;
        

        if (start > end) {
            return;
        }

        int baseNum = arr[i];//要先经过上面的if判断，如果已经排序完，传过来的i是10，那么就会把索引10的元素给baseNum了，然鹅并不存在10索引，市议会报错

        while (start != end) {
            while(true) {
                if(end <= start || arr[end] < baseNum) {
                    break;
                }
                end--;
            }
            while(true) {
                if(start >= end || arr[start] > baseNum) {
                    break;
                }
                start++;
            }

            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
        int temp = arr[i];
        arr[i] = arr[start];
        arr[start] = temp;

        quickSort(arr, i, start - 1);
        quickSort(arr, start + 1, j);

    }
    
}

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com.cn/developer/support-plan?invite_code=1r244lfzquqoz