一、数组排序

1. 冒泡排序

• 原理
  • 从第一个元素开始，两两进行比较，将较大的数往后移，这样就将最大的数放在了最后。第二轮将第二大的数放在倒数第二个，以次类推，将元素按大小顺序排序
• 图示

• 代码实现

/**
     * 利用冒泡排序法对数组进行排序
     */
    public static int[] MaoPaoSequence(int[] arr) {

        for (int j = 0; j < arr.length - 1; j++) {//控制多少轮
            for (int i = 0; i < arr.length - 1 - j; i++) {//每执行一次就将一轮的最大值挪到最后
                if (arr[i] > arr[i + 1]) {//将较大的数挪到后面
                    int mid = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = mid;
                }
            }
        }
        return arr;
    }

2. 选择排序

• 原理
  • 从0索引处开始，依次与后边的元素进行比较，小的放前面，这样子一趟下来就得到了最小值，然后从1索引处开始，得到第二个较小值，依次循环下去
• 图示

• 代码实现

public static int[] selectSequence(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
//                比较，若外层循环的数大于内层循环的数，则交换位置（将最小的数交换到最前面）
                if (arr[i] > arr[j]) {
                    int mid = arr[i];
                    arr[i] = arr[j];
                    arr[j] = mid;
                }
            }
        }
        return arr;
    }

3. 二分查找

• 原理
  • 在有序数组中寻找一个元素x，先用数组的中间元素和x比较，如果相等则返回，x小于中间元素的话就在左半区寻找，大于中间元素就在右半区寻找，此时也可以用半区的中间元素进行比较，进一步缩小寻找范围，直到找到，可以采用递归的思想
• 图示

• 代码实现

/**
     * 利用二分查找返回元素在有序数组中的索引，没找到则返回-1
     */
    public static int getIndex(int[] arr, int num) {

        int minIndex = 0;
        int maxIndex = arr.length - 1;
        int midIndex = (minIndex + maxIndex) / 2;

        while (minIndex <= maxIndex) {
            if (num == arr[midIndex]) {
                return midIndex;
            } else if (num > arr[midIndex]) {
                minIndex = midIndex + 1;
            } else {
                maxIndex = midIndex - 1;
            }
            midIndex = (maxIndex + minIndex) / 2;
        }
        return -1;
    }

4. 快速排序

• 原理
  • 找一个基准点x，将数组中小于x的数放在x的左边，大于x的数放x的右边，这样就形成了两个分区；对两个分区执行同样的操作，一直到每个分区只有一个元素，此时数组元素就有序了，可以采用递归的方法
• 代码实现

 /**
     * @Description：对数组元素采用快速排序方法进行排序 .
     * 1.得到左右分区的中间索引
     * 2.对左边的分区再次分区
     * 3.对右边的分区再次分区
     * 4.重复3、4步，采用递归调用
     */
    public static int[] quickSort(int[] arr, int start, int ends) {
        if (start < ends) {
            int index = getIndex(arr, start, ends);//得到左右分区的中间索引
            quickSort(arr, start, index - 1);//对左边的区再次分区
            quickSort(arr, index + 1, arr.length - 1);//对右边的区再次分区
        }
        return arr;
    }

    /**
     * @Description：得到左右分区的中间索引 .
     * 1.定义基准变量，默认为分区的第一个元素
     * 2.从右往左遍历数组，比较数组元素
     * 3.如果比基准元素小，就把这个元素填进上一个索引处
     * 4.从左往右遍历数组，比较数组元素
     * 5.如果比基准元素大，就把这个元素填进上一个索引处
     * 6.重复2—5步骤，直到左右边界索引相遇
     * 7.将开始的基准变量填入最后一个元素处，即中间索引处
     * 8.返回分区的中间索引
     */
    private static int getIndex(int[] arr, int start, int ends) {
        int i = start;
        int j = ends;
        //定义基准变量
        int x = arr[i];
        //循环，当左右边界索引相遇时得到分区中间索引
        while (i < j) {
            //从右往左遍历，如果右边界的元素比基准数大，直接越过，右边界左移
            while (i < j && arr[j] >= x) {
                j--;
            }
            //如果右边界的元素比基准数小，且左边界小于右边界，将右边界的元素填入左边界对应元素中
            if (i < j) {
                arr[i] = arr[j];
                //填完后将左边界右移一位
                i++;
            }

            //从左往右遍历，如果左边界元素小于基准元素，则越过，左边界右移
            while (i < j && arr[i] < x) {
                i++;
            }
            //如果左边界元素比基准元素大，且左边界小于右边界，将左边界元素填入右边界对应元素中
            if (i < j) {
                arr[j] = arr[i];
                //填完后右边界左移一位
                j--;
            }
        }
        //将基准元素填入中间索引处
        arr[j] = x;
        //返回中间索引
        return i;
    }
}

5. 插入排序

• 原理
  • 将数组的第一个元素看作是一个有序数组，从第二个元素开始，将其与前面有序元素从左往右依次进行比较，当小于等于某一元素时将其插入，保证插入后也是有序的，依次将数组所有元素插入
• 代码实现

/**
     * 插入排序法，对数组排序并返回
     */
    public static int[] insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] < arr[j]) {
                    int mid = arr[i];
                    arr[i] = arr[j];
                    arr[j] = mid;
                }
            }
        }
        return arr;
    }
}

6. 归并排序

• 原理
  • 将一个右n个元素的数组拆成一个个单独的元素，这些单独的元素都可以认为是有序的，将这些单独的元素两个一组合并成n/2个有序数组，再将这n/2个有序数组合并成n/4个有序数组，最终得到长度为n的一个有序数组
• 代码实现

    /**
     * 归并排序方法
     */
    public static void mergeSort(int[] a, int start, int end) {

        if (start < end) {       //递归结束条件，当子序列中只有一个元素时结束
            int mid = (start + end) / 2;    //划分子序列，得到中间索引
            mergeSort(a, start, mid);     //对左侧子序列进行递归排序
            mergeSort(a, mid + 1, end);  //对右侧子序列进行递归排序
            merge(a, start, mid, end);      //合并
        }
    }

    /**
     * 将两个子序列按顺序合并
     */
    private static void merge(int[] a, int left, int mid, int right) {

        int[] tmp = new int[a.length];//中间数组
        int p1 = left, p2 = mid + 1, k = left;//p1、p2分别是左边界和中间边界，用来检测原数组元素的，k是给中间数组中填充元素

        //当左边界小于中间边界，且中间边界小于右边界时
        while (p1 <= mid && p2 <= right) {
            //如果左边界处的元素小于等于中间边界处的元素(符合排序规则)
            if (a[p1] <= a[p2])
                //将原数组左边界的元素从左往右依次存入中间数组
                //边界右移
                tmp[k++] = a[p1++];
            else if (a[p1] > a[p2])//如果左边界处元素大于中间边界处元素，则将中间边界处的元素依次存入中间数组
                //边界右移
                tmp[k++] = a[p2++];
        }

        while (p1 <= mid) tmp[k++] = a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
        while (p2 <= right) tmp[k++] = a[p2++];//同上

        //复制回原数组
        for (int i = left; i <= right; i++) {
            a[i] = tmp[i];
        }
    }
}

先更这么多，缺的图示后面会补上，觉得有帮助的可以点赞关注一下哦！