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

目录
  • 一、快速排序
    • 1、基本介绍
    • 2、代码实现
  • 二、归并排序
    • 1、基本介绍
    • 2、代码实现
  • 三、基数排序
    • 1、基本介绍
    • 2、代码实现

一、快速排序

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;
                /*
                  放对应的桶中,
                  bucketcount[elentData]表示对应的桶的数据,
                  假如第一个数为579,要放入bucketcount[9](第九个桶)的第一个位置,
                  默认初始化为0,所以第一个数放入的位置是bucketcount[9] = 0
                */
                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快速排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 图解Java经典算法快速排序的原理与实现

    目录 快速排序 算法原理 图解 Java代码实现 算法分析 快速排序 通过一趟排序将待排元素分成独立的两部分,其中一部分为比基准数小的元素,另一部分则是比基准数大的元素.然后对这两部分元素再按照前面的算法进行排序,直到每一部分的元素都只剩下一个. 本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法. 算法原理 从数列中挑出一个元素作为基准点 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面 然后基准值左右两边,重复上述步骤 通过递归把基准值元素左右两侧的

  • 图解Java经典算法归并排序的原理与实现

    目录 归并排序 算法原理 动图演示 代码实现 复杂度 归并排序 归并排序主要分成两部分实现,分.合两部分,分是把数组分成两半,再递归的对子数组进行 分 操作,直到分成一个个单独的数.合是把两个数组合并为有序数组,在对有序数组进行合并,直到全部子数组合并为一个完整的数组. 算法原理 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤c直

  • Java语言实现基数排序代码分享

    算法思想:依次按个位.十位...来排序,每一个pos都有分配过程和收集过程,array[i][0]记录第i行数据的个数. package sorting; /** * 基数排序 * 平均O(d(n+r)),最好O(d(n+r)),最坏O(d(n+r));空间复杂度O(n+r);稳定;较复杂 * d为位数,r为分配后链表的个数 * @author zeng * */ public class RadixSort { //pos=1表示个位,pos=2表示十位 public static int g

  • JAVA十大排序算法之基数排序详解

    目录 基数排序 代码实现 时间复杂度 算法稳定性 基数排序 vs 桶排序 vs 计数排序 总结 基数排序 常见的数据元素一般是由若干位组成的,比如字符串由若干字符组成,整数由若干位0~9数字组成. 基数排序按照从右往左的顺序,依次将每一位都当做一次关键字,然后按照该关键字对数组排序,同时每一轮排序都基于上轮排序后的结果:当我们将所有的位排序后,整个数组就达到有序状态.基数排序不是基于比较的算法. 基数是什么意思?对于十进制整数,每一位都只可能是0~9中的某一个,总共10种可能.那10就是它的基,

  • 图解Java中归并排序算法的原理与实现

    目录 一.基本思想 二.算法分析 1.算法描述 2.过程分析 3.动图演示 三.算法实现 一.基本思想 归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为2-路归并. 二.算法分析 1.算法描述 把长度为n的输入序列分成两个长度为n/2的子序列:对这两个子序列分别采用归并排序:将两个排序好的子序列合并

  • Java实现归并排序的示例代码

    目录 1.算法理解 2.实现代码 3.实现效果 1.算法理解 参考:图解Java中归并排序算法的原理与实现 2.实现代码 import java.lang.reflect.Array; import java.util.*; public class MergeSort{ // 我们的算法类不允许产生任何实例 private MergeSort(){} // 将arr[l...mid]和arr[mid+1...r]两部分进行归并 private static void merge(Compara

  • Java实现快速排序算法可视化的示例代码

    实现效果 示例代码 import java.awt.*; public class AlgoVisualizer { private static int DELAY = 100; private SelectionSortData data; private AlgoFrame frame; public AlgoVisualizer(int sceneWidth, int sceneHeight, int N){ data = new SelectionSortData(N, sceneHe

  • 基数排序简介及Java语言实现

    基本思想 基数排序(RadixSort)是在桶排序的基础上发展而来的,两种排序都是分配排序的高级实现.分配排序(DistributiveSort)的基本思想:排序过程无须比较关键字,而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶:O(n). 基数排序是一种稳定的排序算法,但有一定的局限性: 1.关键字可分解. 2.记录的关键字位数较少,如果密集更好 3.如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序. 先来看一

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

    目录 一.快速排序 1.基本介绍 2.代码实现 二.归并排序 1.基本介绍 2.代码实现 三.基数排序 1.基本介绍 2.代码实现 一.快速排序 1.基本介绍 以上面的数组为例分析快速排序. 首先要传入三个值,数组arr[ ] ,最左边下标left ,最右边下标 right.然后将根据左右的下标值计算出中间值mid. 我们要做的就是将左边的值大于mid的放到右边,将右边小于mid的值放到左边. 左右两边分别单独循环,左边找到比mid大的数,右边找到比mid小的数. 两边分别找到符合条件的数后,进

  • 排序算法图解之Java快速排序的分步刨析

    目录 1.快速排序简介 2.思路简介及图解 3.实现代码及运行结果 1.快速排序简介 快速排序是对冒泡排序的一种改进.基本思想为:通过一趟排序将要排序的数据分割为独立的两个部分,其中一部分的所有数据比另外一部分的所有数据要小,然后按照此方法对这两部分分别进行快速排序,整个过程可以递归进行,以此达到整个数据变成有序序列. 2.思路简介及图解 快速排序算法通过多次比较和交换来实现排序,其排序流程如下: (1)首先设定一个分界值,通过该分界值将数组分成左右两部分. (2)将大于或等于分界值的数据集中到

  • java实现的各种排序算法代码示例

    折半插入排序 折半插入排序是对直接插入排序的简单改进.此处介绍的折半插入,其实就是通过不断地折半来快速确定第i个元素的 插入位置,这实际上是一种查找算法:折半查找.Java的Arrays类里的binarySearch()方法,就是折半查找的实现,用 于从指定数组中查找指定元素,前提是该数组已经处于有序状态.与直接插入排序的效果相同,只是更快了一些,因 为折半插入排序可以更快地确定第i个元素的插入位置 代码: package interview; /** * @author Administrat

  • Java实现8种排序算法的示例代码

    冒泡排序 O(n2) 两个数比较大小,较大的数下沉,较小的数冒起来. public static void bubbleSort(int[] a) { //临时变量 int temp; //i是循环次数,也是冒泡的结果位置下标,5个数组循环5次 for (int i = 0; i < a.length; i++) { //从最后向前面两两对比,j是比较中下标大的值 for (int j = a.length - 1; j > i; j--) { //让小的数字排在前面 if (a[j] <

  • Java实现常见的排序算法的示例代码

    目录 一.优化后的冒泡排序 二.选择排序 三.插入排序 四.希尔排序 五.快速排序 六.随机化快速排序 七.归并排序 八.可处理负数的基数排序 一.优化后的冒泡排序 package com.yzh.sort; /* 冒泡排序 */ @SuppressWarnings({"all"}) public class BubbleSort { public static void BubbleSort(int[]a){ for (int i = 0; i <a.length-1 ; i+

  • Java开发工具IntelliJ IDEA安装图解

    这篇文章主要介绍了Java开发工具IntelliJ IDEA安装图解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 > 开发工具概述 IDEA是一个专门针对Java的集成开发工具(IDE),由Java语言编写.所以,需要有JRE运行环境并配置好环境变量. 它可以极大地提升我们的开发效率.可以自动编译,检查错误.在公司中,使用的就是IDEA进行开发. IDEA软件安装 进入官网http://www.jetbrains.com/选择需要的版本下载.

  • C语言非递归算法解决快速排序与归并排序产生的栈溢出

    目录 1.栈溢出原因和递归的基本认识 2.快速排序(非递归实现) 3.归并排序(非递归实现) 建议还不理解快速排序和归并排序的小伙伴们可以先去看我上一篇博客​​​​​​哦!C语言超详细讲解排序算法下篇 1.栈溢出原因和递归的基本认识 我们先简单来了解下内存分布结构: 栈区:用于存放地址.临时变量等:                                                                            堆区:程序运行期间动态分配所使用的场景: 静态区

  • Java用数组实现循环队列的示例

    复习了下数据结构,用Java的数组实现一下循环队列. 队列的类 //循环队列 class CirQueue{ private int QueueSize; private int front; private int rear; private int[] queueList ; public CirQueue(int QueueSize){ this.QueueSize = QueueSize; queueList = new int[QueueSize]; front = 0; rear =

  • Java编程redisson实现分布式锁代码示例

    最近由于工作很忙,很长时间没有更新博客了,今天为大家带来一篇有关Redisson实现分布式锁的文章,好了,不多说了,直接进入主题. 1. 可重入锁(Reentrant Lock) Redisson的分布式可重入锁RLock Java对象实现了java.util.concurrent.locks.Lock接口,同时还支持自动过期解锁. public void testReentrantLock(RedissonClient redisson){ RLock lock = redisson.getL

随机推荐