冒泡排序:从0索引开始向后比较,比后一位数大就交换位置,每次循环结束找出一个大的数放到最后。

    1. //冒泡排序
    2. private static void bubbleSort(int[] arr) {
    3. for (int i = 0; i < arr.length; i++) {
    4. //内循环是用于排序
    5. for (int j = 0; j < arr.length - i - 1; j++) {
    6. if (arr[j] > arr[j + 1]) {
    7. //比下一个数大就交换位置
    8. int temp = arr[j];
    9. arr[j] = arr[j + 1];
    10. arr[j + 1] = temp;
    11. }
    12. }
    13. }
    14. }

    快速排序:主要思想——假定一个基准数,一般设定0索引处,然后将小的数放到左边,大的放到右边。然后将两边的数组递归。

     //快速排序
        private static void quickSort(int[] arr, int low, int high) {
            //跳出递归条件
            if (low >= high) {
                return;
            }
            //先记录开始的索引
            int left = low;
            int right = high;
            //基准数
            int temp = arr[low];
            while (left < right) {
                //升序排列先从右边开始
                while (left < right && arr[right] >= temp) {
                    //如果右边的数比基准数大就指针左移,直到找到小的数
                    right--;
                }
                while (left < right && arr[left] <= temp) {
                    //如果左边的数比基准数小就指针右移,直到找到大的数
                    left++;
                }
                //交换找到的两个数
                int tempT = arr[left];
                arr[left] = arr[right];
                arr[right] = tempT;
            }
            //循环结束将指针停下的位置跟基准数原位置交换
            arr[low] = arr[left];
            arr[left] = temp;
            //再将两边的数递归排序
            quickSort(arr, low, left);
            quickSort(arr, left + 1, high);
        }
    

    插入排序:主要思想——将待插入数放入已排好序的数组中,找到合适插入位置就停下插入。
    一般把1索引处当成插入数,0索引当作已排好序得数组
    image.png
    image.png

     //插入排序
        private static void insertSort(int[] arr) {
            //必须是长度大于1.
            /*for (int i = 1; i < arr.length; i++) {
                //待插入数
                int temp=arr[i];
                while (temp < arr[i - 1]) {
                    //待插入的数比原来的数小就将原来的数往后移动1位
                    arr[i] = arr[i - 1];
                    if (i-- == 1) {
                        break;
                    }
                }
                arr[i]=temp;
            }
            */
            for (int i = 0; i < arr.length - 1; i++) {
                //待插入数
                int temp = arr[i + 1];
                while (arr[i] > temp) {
                    arr[i + 1] = arr[i];
                    if (i-- == 0) {
                        break;
                    }
                }
                //循环结束将待插入数放到指针停下位置
                //这里循环跳出时,不满足的数是arr[i],应在i+1处插入
                arr[i + 1] = temp;
            }
        }
    

    归并排序:主要思想——将数组不断拆分,然后分别排序,两两合并。
    image.png
    image.png

     //归并排序
        private static void mergeSort(int[] arr, int low, int high) {
            //跳出递归条件
            if (low == high) {
                return;
            }
            //找出中间数,分治两个数组
            int mid = (high + low) / 2;//这里是+法运算
            mergeSort(arr, low, mid);
            mergeSort(arr, mid + 1, high);
            //将有序的两个数组合并
            merge(arr, low, mid, high);
        }
    
        //将有序的两个数组合并
        private static void merge(int[] arr, int low, int mid, int high) {
            //创建一个跟传进来数据个数相同长度的临时数组
            int[] arrTemp = new int[high - low + 1];
            //定义三个指针
            int left = low;
            int right = mid + 1;
            int temp = 0;
            while (left <= mid && right <= high) {
                if (arr[left] < arr[high]) {
                    //左边的小,放入临时数组中
                    arrTemp[temp] = arr[left];
                    //指针右移
                    temp++;
                    left++;
                } else {
                    //右边的小,放入临时数组中
                    arrTemp[temp] = arr[right];
                    //指针右移
                    temp++;
                    right++;//
                }
            }
            //循环结束,总有一边是先把数装完的,还剩一部分
            while (left <= mid) {
                arrTemp[temp] = arr[left];
                //指针右移
                temp++;
                left++;
            }
            while (right <= high) {
                arrTemp[temp] = arr[right];
                //指针右移
                temp++;
                right++;//
            }
    
            //讲排好序的临时数组放回原数组中
            for (int i = 0; i < arrTemp.length; i++) {
                arr[low] = arrTemp[i];
                low++;
            }
        }