Java实现常见排序算法(二)

简介: Java实现常见排序算法(二)

问题描述

上次的博客讨论了排序算法中的插入排序和交换排序两个大类,今天将剩下的常见排序算法全部梳理出来。

选择排序

简单选择排序

基本思想:每一趟排序从待排序的序列中选择出最小的元素,顺序放入到元素序列中,直到排序完成。该算法是一个不稳定的算法并且效率与初始数据顺序无关。

空间复杂度为O(1)

时间复杂度最高,平均,最低都为O(n2)
Java实现:

public static int[] selectInsert(int[] n) {

    int minPos,  temp;

    for (int i =  0; i < n.length; i++) {

        minPos =  i;

        //遍历找出最小数的位置

        for (int  j = i + 1; j < n.length; j++) {

            if  (n[j] < n[minPos]) {

                 minPos = j;

            }

        }

        //如果最小数位置不等于当前位置指针,就交换位置,即把数按照从小到大的顺序依次排列

        if  (minPos != i) {

             temp  = n[i];

            n[i]  = n[minPos];

             n[minPos] = temp;

        }

    }

    return n;

}

堆排序

基本原理:堆排序是一种树形选择排序算法,其原理是将R[1…n]看成一棵完全二叉树的顺序存储结构。利用完全二叉树中双亲节点和孩子结点的关系,在当前无序区中选择关键字最大(最小)的元素构建成大根堆(小根堆)。堆排序的主要流程便是,建立大(小)根堆,然后输出元素(顶部和底部元素进行交换),再调整堆,直到元素全部输出。堆排序是一个不稳定的算法。

堆的定义为:n个关键字序列R[1…n]称为堆,堆通常可以被看做一棵树的数组对象。

当且仅当序列满足R[i≤R[2i]且R[i]≤R[2i+1]时称为该堆为大根堆,其中1≤i≤⌊ n/2⌋

当且仅当序列满足R[i]≥R[2i]且R[i]≥R[2i+1]时称为该堆为小根堆,其中1≤i≤⌊n/2⌋

比如在大根堆中,最大的元素放在根节点中,且对于任一非根节点,它的值小于等于其双亲节点的值。

对于堆排序来说关键在于构造堆,而建堆是一个反复调整筛选的过程。首先从树的最后一个非叶子节点开始调整,按照堆的性质移动元素位置。如下图便是一个大顶推的调整过程。


初始堆建立完成后,就是进行排序操作,排序操作的主要步骤是:以大根堆为例,每一次排序将堆顶元素与堆尾元素进行交换,然后再调用调整堆的算法使除了堆尾元素以外剩下的堆再次调整成一个大根堆,这样循环length-1次就可以将元素调整为从小到大的顺序,完成排序。

空间复杂度为O(1)

时间复杂度的最高,平均,最低都为O(nlog2n)

Java实现:

//堆排序

private static int[] heapSort(int[] n) {

    //建立堆,从最后一个非叶子节点开始

    for (int i =  (n.length - 2) / 2; i >= 0; i--) {

         adjustHeap(n, i, n.length);

    }

    int temp;

    //完成排序,从最后一个元素进行输出,每次循环确定一个元素的位置

    for (int i =  n.length - 1; i >= 1; i--) {

        temp =  n[0];

        n[0] =  n[i];

        n[i] =  temp;

        // 筛选 R[0] 结点,得到i个结点的堆

         adjustHeap(n, 0, i);

    }

    return n;

}

 

//调整堆

public static void adjustHeap(int[] n, int k, int  length) {

    //设置堆顶的值

    int temp =  n[k];

     //从左孩子开始判断

    for (int i =  k * 2 + 1; i <= length - 1; i = 2 * i + 1) {

        //如果左孩子小于右孩子

        if (i + 1  < length && n[i] < n[i + 1]) {

             //取右孩子

             i++;

        }

        //如果堆顶的值大于左右孩子中的较大者,无需调整

        if (temp  >= n[i]) {

             break;

        } else {

            //否则的话,将左右孩子中的较大者换到双亲节点

            n[k]  = n[i];

            //然后将k值更新,方便继续向下调整

            k =  i;

        }

 

    }

    //将原堆顶位置当入最后调整出来的地方

    n[k] = temp;

}

归并排序和基数排序

归并排序

基本思想:“归并”的意思是指将两个或者两个以上的有序表合并成一个新的有序表。假设一个待排序的序列长度为n,首先我们可以将其视为n个有序表,即每个表中元素个数为1,然后我们将n个有序表进行两两归并,得到⌈ \lceil⌈n/2⌉ \rceil⌉个长度为2或者1的有序表然后再再次基础上进行两两归并直到得到一个长度为n的有序表为止。这种方法就称为2路归并排序。归并排序是一个稳定的排序算法。PS.归并排序的发明者是约翰·冯·诺伊曼,其速度仅次于快速排序(平均状况下)

例如我们有一个初始值为[22,11,32,2,12,83,10]的序列,才有2路归并排序

第一趟归并后:[11,22],[2,32],[12,83],[10]

第二趟归并后:[2,11,22,32],[10,12,83]

第三趟归并后:[2,10,11,12,22,32,83]

空间复杂度为O(n)

时间复杂度的最高,平均,最低都为O(nlog2n)

Java实现:

//归并排序

public static int[] mergeSort(int[] n, int low, int  high) {

    int mid =  (low + high) / 2;

    if (low <  high) {

         mergeSort(n, low, mid);

         mergeSort(n, mid + 1, high);

        merge(n,  low, mid, high);

    }

    return n;

}

 

//调整

public static void merge(int[] n, int low, int mid, int  high) {

    int[]  tempArr;

    int i = low,  j = mid + 1, k = 0;

    tempArr =  Arrays.copyOf(n, high - low + 1);

    // 把较小的数先移到新数组中

    while (i  <= mid && j <= high) {

        if (n[i]  < n[j]) {

            tempArr[k++] = n[i++];

        } else {

             tempArr[k++] = n[j++];

        }

    }

    // 把左边剩余的数移入数组

    while (i  <= mid) {

         tempArr[k++] = n[i++];

    }

    // 把右边边剩余的数移入数组

    while (j  <= high) {

         tempArr[k++] = n[j++];

    }

    // 把新数组中的数覆盖nums数组

     System.arraycopy(tempArr, 0, n, low, tempArr.length);

}

基数排序(桶子排序)

基本思想:基数排序是一种不基于比较的排序,而采用多关键字排序思想,即基于关键字各位的大小进行排序,主要使用“分配”和“收集”两种基本操作对单逻辑关键字进行排序。基数排序又分为最高位优先(MSD)排序和最低位优先(LSD)排序。他的主要思想是将待排序的整数按位数切割成不同的数字,然后对每一位的数进行单独的比较,具体做法是:将所有待比较数值统一为同样的数位长度,如有不同位数则在前面进行补零操作,然后从最低位开始,依次进行一次排序,这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

举个栗子:

待排序的数据为[222,123,580,996,965,854,775],使用最低位优先排序

第一趟将最低位进行排序:

[580,222,123,854,965,775,996]

第二趟将中间位进行排序:

[222,123,854,965,775,580,996]

第三趟将最高位进行排序:

[123,222,580,775,854,965,996]

空间复杂度:一趟排序需要的辅助空间为O®(r个队列或桶)用于存放d待排序的数

时间复杂度:O(d(n+r)),d趟的分配和收集,一趟分配为O(n),一趟收集为O®。

Java实现(代码参考百度百科)

//d表示最大的数有多少位

public static int[] radixSort(int[] number, int d) {

    //控制键值排序依据在哪一位

    int k = 0,n =  1,m = 1;

    //数组的第一维表示可能的余数0-9

    int[][] temp  = new int[10][number.length];

    //数组orderp[i]用来表示该位是i的数的个数

    int[] order =  new int[10];

    while (m  <= d) {

        for (int  value : number) {

            int  lsd = ((value / n) % 10);

             temp[lsd][order[lsd]] = value;

            order[lsd]++;

        }

        for (int  i = 0; i < 10; i++) {

            if  (order[i] != 0)

                 for (int j = 0; j < order[i]; j++) {

                     number[k] = temp[i][j];

                     k++;

                }

            order[i]  = 0;

        }

        n *= 10;

        k = 0;

        m++;

    }

    return  number;

}

总结

就此常见的几个排序算法就总结得差不多了,下一次的博客准备写一下JDK8中默认的排序算法是如何实现的以及介绍的这几种排序算法的实际使用案例和场景。


目录
打赏
0
0
0
0
14
分享
相关文章
Java 实现局域网电脑屏幕监控算法揭秘
在数字化办公环境中,局域网电脑屏幕监控至关重要。本文介绍用Java实现这一功能的算法,涵盖图像采集、数据传输和监控端显示三个关键环节。通过Java的AWT/Swing库和Robot类抓取屏幕图像,使用Socket进行TCP/IP通信传输图像数据,并利用ImageIO类在监控端展示图像。整个过程确保高效、实时和准确,为提升数字化管理提供了技术基础。
86 15
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
131 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。
解锁分布式文件分享的 Java 一致性哈希算法密码
在数字化时代,文件分享成为信息传播与协同办公的关键环节。本文深入探讨基于Java的一致性哈希算法,该算法通过引入虚拟节点和环形哈希空间,解决了传统哈希算法在分布式存储中的“哈希雪崩”问题,确保文件分配稳定高效。文章还展示了Java实现代码,并展望了其在未来文件分享技术中的应用前景,如结合AI优化节点布局和区块链增强数据安全。
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
84 16
企业局域网监控软件中 Java 优先队列算法的核心优势
企业局域网监控软件是数字化时代企业网络安全与高效运营的基石,犹如一位洞察秋毫的卫士。通过Java实现的优先队列算法,它能依据事件优先级排序,确保关键网络事件如异常流量、数据泄露等被优先处理,保障系统稳定与安全。代码示例展示了如何定义网络事件类并使用PriorityQueue处理高优先级事件,尤其在面对疑似风险时迅速启动应急措施。这一核心技术助力企业在复杂网络环境中稳健前行,护航业务腾飞。
66 32
剖析基于Java算法驱动的智能局域网管控之道
本文探讨了基于Java语言的局域网控制方案,结合链表数据结构与令牌桶算法,解决设备管理和流量调度难题。通过链表灵活存储网络设备信息,实现高效设备管理;令牌桶算法则精准控制流量,确保网络平稳运行。二者相辅相成,为校园、企业等局域网提供稳固高效的控制体系,保障业务连续性和数据安全。
【潜意识Java】深度解析黑马项目《苍穹外卖》与蓝桥杯算法的结合问题
本文探讨了如何将算法学习与实际项目相结合,以提升编程竞赛中的解题能力。通过《苍穹外卖》项目,介绍了订单配送路径规划(基于动态规划解决旅行商问题)和商品推荐系统(基于贪心算法)。这些实例不仅展示了算法在实际业务中的应用,还帮助读者更好地准备蓝桥杯等编程竞赛。结合具体代码实现和解析,文章详细说明了如何运用算法优化项目功能,提高解决问题的能力。
73 6
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
54 5
探秘局域网桌面监控:深入剖析 Java 语言核心算法
在数字化办公时代,局域网桌面监控如同企业的“智慧鹰眼”,确保工作效率与数据安全。本文以Java为载体,揭示哈希表在监控中的关键应用。通过高效的数据结构和算法,哈希表能快速索引设备连接信息,大幅提升监控的时效性和响应速度。代码示例展示了如何用Java实现设备网络连接监控,结合未来技术如AI、大数据,展望更智能的监控体系,助力企业在数字化浪潮中稳健前行。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等