文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java快速排序与归并排序及基数排序图解示例

2024-04-02 19:55

关注

一、快速排序

1、基本介绍

以上面的数组为例分析快速排序。

首先要传入三个值,数组arr[ ] ,最左边下标left ,最右边下标 right。然后将根据左右的下标值计算出中间值mid。

我们要做的就是将左边的值大于mid的放到右边,将右边小于mid的值放到左边。

左右两边分别单独循环,左边找到比mid大的数,右边找到比mid小的数。

两边分别找到符合条件的数后,进行交换。

然后继续比较并交换,此刻 l 和 mid 都指向3,r 指向 5 。

这时需要进行判断,如果arr[l] 等于mid 则 r--,如果arr[r] 等于mid则 l++ 。此时又进行判断arr[l] 是否等于arr[r],等于则退出。第一轮就结束了。

第一次完以后,我们使用递归,递归会重复上面的操作,从而完成排序。

2、代码实现

//参数传入数组arr , 最左边的下标left,最右边的下标 right
public static void quickSort(int[] arr , int left , int right){
        //分别用临时变量代替
        int l = left;
        int r = right;
        //中间的下标
        int middle = arr[(left + right) / 2];
        //临时变量,用于交换数据
        int temp = 0;
        //进行循环,只要右边的下标 l 小于 左边的下标 r 就进行循环
        while (l < r){
            //左边l 到 中间middle 单独循环,找到比middle大的值
            while (arr[l] < middle){
                l += 1;
            }
            //中间middle 到 右边 r 单独循环,找到比middle小的值
            while (arr[r] > middle){
                r -= 1;
            }
            //退出循环,表示找到,不过先判断 l 是否大于等于 r 
            //满足就可以退出循环,不需要执行下面的代码了
            if(l >= r){
                break;
            }
            //找到的数据进行交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //此时进行判断,如果arr[l] 等于middle  则 r--
            if(arr[l] == middle){
                r -= 1;
            }
            //如果  arr[r] 等于middle 则 l++
            if(arr[r] == middle){
                l += 1;
            }
        }
        //退出循环,l 会等于 r,此时要将两者移位,l进行加一,r进行减一
        if(l == r){
            l += 1;
            r -= 1;
        }
        //第一轮完成后进行递归
        //重复上面的方法,向左递归
        if(left < r){
            //r 继续往前移的,所以左下标为left ,右下标为 r
            quickSort(arr, left , r);
        }
        //重复上面的操作,向右递归
        if(right > l){
            //l 继续往后移的,所以左下标为 l ,右下标为 right
            quickSort(arr, l , right);
        }
    }

二、归并排序

1、基本介绍

2、代码实现

▶ 首先实现合并

public static void merger(int[] arr , int left ,int mid , int right , int[] temp){
        int i = left;
        int j = mid + 1;
        int t = 0;//数组temp的下标
        //将arr数组按顺序放入temp 数组
        while (i <= mid  && j <= right){
            //从中间分隔开,左边和右边相互比较
            //如果左边更小,先放入temp数组,否则右边先放入
            if(arr[i] < arr[j]){
                temp[t] = arr[i];
                i++;
                t++;
            }else {
                temp[t] = arr[j];
                j++;
                t++;
            }
        }
        //有可能有一边还没放完,于是继续循环放放入
        //左边没放完
        while (i <= mid){
            temp[t] = arr[i];
            t++;
            i++;
        }
        //右边没放完
        while (j <= right){
            temp[t] = arr[j];
            j++;
            t++;
        }
        //将temp中数据拷入到arr
        t = 0;
        int leftind = left;
        //第一次(leftind,right)是(0,1)(2,3)(4,5)(6,7)
        //第二次(leftind,right)是(0,3)(4,7)
        //第三次(leftind,right)是(0,7)
        while (leftind <= right){
            arr[leftind] = temp[t];
            t++;
            leftind++;
        }
    }

▶ 分隔和合并进行递归

public static void mergerSort(int[] arr, int left,int right, int[] temp){
        //判断
        if (left < right){
            //求出中间值
            int mid = (left + right) / 2;
            //调用自己,向左递归
            mergerSort(arr, left, mid , temp);
            //调用自己,向右递归
            mergerSort(arr , mid + 1, right, temp);
            //调用merger进行合并
            merger(arr, left , mid, right, temp);
        }
    }

三、基数排序

1、基本介绍

首先我们需要10个数组,分别对应10个桶,每个桶有对应的下标。

然后按每个数的个位数大小放入对应的桶中,放好后,按桶的顺序依次取出。

第二次是看每个数的十位,不及十位的就当做0,依旧是依次放入对应的桶中,并按顺序取出。

第三次是看每个数的百位,重复上面的操作,最后得到的就是有序的数组。

2、代码实现

public static void cardinalitySort(int[] arr){
        //首先找到数组中最大数的位数
        int max = arr[0];
        for(int i = 1; i < arr.length - 1; i++ ){
            if(arr[i] > max){
                max = arr[i];
            }
        }
        int maxLength = (max + "").length();
        //定义10个桶,每个桶大小为数组大小
        int[][] bucket = new int[10][arr.length];
        //定义一个数组来表示每个桶存放的数据
        int[] bucketcount = new int[10];
        //n是用来进行位数处理的
        for(int i = 1, n = 1; i <= maxLength ; i++,n *= 10){
            for(int j = 0; j < arr.length ; j++){
                //对每位数进行位处理,并放入桶中
                int elentData = arr[j] / n % 10;
                
                bucket[elentData][bucketcount[elentData]] = arr[j];
                //第一个数放完后,这个桶中数据进行++,
                //下次再放入这个桶时,bucketcount[9] = 1
                bucketcount[elentData]++;
            }
            int index = 0;
            //遍历每一个桶
            for(int k = 0; k < bucketcount.length; k++){
                //第一次默认为bucketcount[k] = 0
                //所以如果第一个数为零,就说明这个桶为空
                if(bucketcount[k] != 0){
                    //有数据,则桶bucketcount[k]就会有对应数据多少的大小,进行遍历
                    for(int l = 0; l < bucketcount[k] ; l++){
                        //放入原来的数组
                        arr[index++] = bucket[k][l];
                    }
                }
                //桶中的数放回原数组放完后,进行置空
                bucketcount[k] = 0;
            }
        }
    }

到此这篇关于Java快速排序与归并排序及基数排序图解示例的文章就介绍到这了,更多相关Java快速排序内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯