冒泡排序：从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++;
        }
    }