java中数组排序方法都有哪些_java基础知识点整理

java中数组排序方法都有哪些_java基础知识点整理文章目录一、数组排序1.冒泡排序2.选择排序3.二分查找4.快速排序5.插入排序6.归并排序一、数组排序1.冒泡排序原理从第一个元素开始,两两进行比较,将较大的数往后移,这样就将最大的数放在了最

一、数组排序

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

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

今天的文章java中数组排序方法都有哪些_java基础知识点整理分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/78058.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注