您的位置:首页 > 教程 > JAVA/JAVA编程 > Java数据结构之选择排序算法的实现与优化

Java数据结构之选择排序算法的实现与优化

2023-01-22 05:43:18 来源:易采站长站 作者:

目录
初识选择排序算法实现优化后的算法实现选择排序 VS 冒泡排序

初识选择排序

算法思想[以升序为例]:

第一趟选择排序时,从第一个记录开始,通过n-1次关键字的比较,从第n个记录中选出关键字最小的记录,并和第一个记录进行交换

第二趟选择排序时,从第二个记录开始,通过n-2次关键字的比较,从第n-1个记录中选出关键字最小的记录,并和第二个记录进行交换

第i趟选择排序时,从第i个记录开始,通过n-i次关键字的比较,从n-i+1个记录中选择出关键字最小的记录,并和第i个记录进行交换

反复进行上述步骤,经过n-1趟选择排序,将把n-1个记录排到位,最后剩下的那个元素同样已经就位,所以共需进行n-1趟选择排序

文字描述[以升序为例]

将数组分为两个子集,排序的和未排序的,每一轮从未排序的子集中选出最小的元素,放入排序子集,重复上述步骤,直至整个数组有序

算法实现

代码如下:

package bin_find;
import java.util.Arrays;

public class selectionSort {
    public static void main(String[] args) {
        int[] a={5,3,7,2,1,9,8,4};
        selection(a);
    }

    private static void selection(int[] a){
        for(int i=0;i<a.length-1;i++) {//n个元素参与排序,需要进行n-1次
            for (int j = i + 1; j < a.length; j++) {//每轮i+1---a.length个元素之间相比较
                if (a[i] > a[j]) {//前者大于后者,则进行交换
                    swap(a, i, j);
                }
            }
            System.out.println("第"+(i+1)+"轮选择排序的结果"+Arrays.toString(a));
        }
    }
    public static void swap(int arr[],int i,int j){
        int t=arr[i];
        arr[i]=arr[j];
        arr[j]=t;
    }
}

输出如下:

第1轮选择排序的结果[1, 5, 7, 3, 2, 9, 8, 4]
第2轮选择排序的结果[1, 2, 7, 5, 3, 9, 8, 4]
第3轮选择排序的结果[1, 2, 3, 7, 5, 9, 8, 4]
第4轮选择排序的结果[1, 2, 3, 4, 7, 9, 8, 5]
第5轮选择排序的结果[1, 2, 3, 4, 5, 9, 8, 7]
第6轮选择排序的结果[1, 2, 3, 4, 5, 7, 9, 8]
第7轮选择排序的结果[1, 2, 3, 4, 5, 7, 8, 9]

优化后的算法实现

优化思路

减少交换次数,每一轮可以先找到最小的索引,再每轮最后再交换元素

代码如下:

package bin_find;
import java.util.Arrays;

public class selectionSort {
    public static void main(String[] args) {
        int[] a={5,3,7,2,1,9,8,4};
        selection(a);
    }

    private static void selection(int[] a){
        //代表每轮选择最小元素要交换到的目标索引
        for(int i=0;i<a.length-1;i++) {

            int s = i;//代表最小元素的索引[这里是升序]---第一次最小元素的索引为1,第二次最小元素的索引为2.....

            //从当前最小元素的下一位元素开始直到最后一个元素---完成一次选择排序
            for (int j = s + 1; j < a.length; j++) {
                //[这里是升序],前者大于后者,则将更小数的索引值赋值给s,因为变量s本身代表的含义为最小元素的索引
                if (a[s] > a[j]) {
                    s = j;
                }
            }
            if (s != i) {//若不是同一个数,则进行交换
                swap(a, s, i);
            }
            System.out.println("第"+(i+1)+"轮选择排序的结果"+Arrays.toString(a));
        }
    }
    public static void swap(int arr[],int i,int j){
        int t=arr[i];
        arr[i]=arr[j];
        arr[j]=t;
    }
}

输出:

第1轮选择排序的结果[1, 3, 7, 2, 5, 9, 8, 4]
第2轮选择排序的结果[1, 2, 7, 3, 5, 9, 8, 4]
第3轮选择排序的结果[1, 2, 3, 7, 5, 9, 8, 4]
第4轮选择排序的结果[1, 2, 3, 4, 5, 9, 8, 7]
第5轮选择排序的结果[1, 2, 3, 4, 5, 9, 8, 7]
第6轮选择排序的结果[1, 2, 3, 4, 5, 7, 8, 9]
第7轮选择排序的结果[1, 2, 3, 4, 5, 7, 8, 9]

未进行优化的算法输出:

进行优化的算法输出:

通过比较二者的输出结果,我们能够很明显的感觉到,经过优化后的算法在实现的过程中,数据之间的交换次数明显减少

选择排序>

1:二者的平均复杂度都是O(n^2),但是当有序数组使用冒泡排序时,其时间复杂度为O(n)

2:选择排序一般要快于冒泡排序,因为其交换的次数少

3:但如果集合有序度高,那么冒泡排序优先于选择排序

例:在上篇文章的冒泡排序优化算法中,我们通过设置变量,去判断当前的数组元素是否发生交换,如果未发生交换,则证明当前数组已经有序,不再进行排序

4:冒泡排序属于稳定排序算法,而选择属于不稳定排序

稳定 VS 不稳定:即为两个大小相等的数,在参与排序之前具有先后关系,若排序完成,这两个数的先后顺序并未发生改变,那么即为稳定排序,否则为不稳定排序

举例:

(3,3,2)

对于上述数组:

参与冒泡排序:

第一轮:3和3相等,无需交换位置,3和2交换位置

第二轮:3和2交换位置

排序结束,排序后的结果为(2,3,3)

参与选择排序:

第一轮:将3取出,与3比较,3不满足大于3,再与2进行比较,满足大于2,交换位置

第二轮:将3取出,与3进行比较,不满足大于3

排序结束,排序成功,排序后的结果为(2,3,3)

通过两种方法的排序结果,我们不难看出通过冒泡排序算法,两个大小相等的数的先后关系并没有发生改变,即为稳定的排序,而通过选择排序算法,两个大小相等的数的先后关系发生了改变,即为不稳定的排序

到此这篇关于Java数据结构之选择排序算法的实现与优化的文章就介绍到这了,更多相关Java选择排序算法内容请搜索易采站长站以前的文章或继续浏览下面的相关文章希望大家以后多多支持易采站长站!

如有侵权,请发邮件到 [email protected]

最新图文推荐

1 2 3

相关文章

  • Spring Cloud 整合Apache-SkyWalking实现链路跟踪的方法

    Spring Cloud 整合Apache-SkyWalking实现链路跟踪的方法

    什么是SkyWalking 查看官网https://skywalking.apache.org/ 分布式系统的应用程序性能监视工具,专为微服务、云原生架构和基于容器(Docker、K8s、Mesos)架构而设计。 安装 进入下载页面https://
    2020-06-18
  • 成功解决IDEA2020 Plugins 连不上、打不开的方法

    成功解决IDEA2020 Plugins 连不上、打不开的方法

    IntelliJ IDEA 2020.1 插件中心一直打不开,鉴于有部分同学反馈设置http proxy不能解决,所以可按以下顺序检查 一、设置 http proxy—勾上Auto-detect proxy setting,参照下图,加上地址 http://127.0.0
    2020-06-25
  • Java后台实现微信支付和微信退款

    Java后台实现微信支付和微信退款

    微信支付流程 都是我自己工作中开发的,亲测可用,不喜勿喷。 controller中我是这么写的,你们需要根据自己的业务需求改动。ResponseBean是我自己封装的,你们可以改成你们想要的形式
    2020-03-27
  • IDEA2020 1.1中Plugins加载不出来的问题及解决方法

    IDEA2020 1.1中Plugins加载不出来的问题及解决方法

    进入File-Setting 如图,取消勾选,点击确认后重启,点击了以后等一会就可以正常显示 ps:下面看下解决IDEA 2020.1.1 找不到程序包和符号 问题描述 IDEA 2020.1.1 maven项目build的时候报错,找
    2020-06-28
  • Intellij idea热部署插件JRebel的使用

    Intellij idea热部署插件JRebel的使用

    项目需求,一直用eclipse的我,也要改用IDEA了,一开始,很不习惯。经过几天的慢慢摸索和习惯之后,发现IDEA确实很好用。dark的界面是我喜欢的,智能的提示也让写代码不再枯燥。 遗
    2020-06-25
  • 详解基于IDEA2020.1的JAVA代码提示插件开发例子

    详解基于IDEA2020.1的JAVA代码提示插件开发例子

    之前因为项目组有自己的代码规范,为了约束平时的开发规范,于是基于2019.1.3版本开发了一个代码提示的插件。但是在把IDEA切换到2020.1版本的时候,却发现疯狂报错,但是网上关于
    2020-06-25
  • springboot + rabbitmq 如何实现消息确认机制(踩坑经验)

    springboot + rabbitmq 如何实现消息确认机制(踩坑经验)

    本文收录在个人博客:www.chengxy-nds.top,技术资源共享,一起进步 最近部门号召大伙多组织一些技术分享会,说是要活跃公司的技术氛围,但早就看穿一切的我知道,这 T M 就是为了刷
    2020-07-01
  • JetBrains IntelliJ IDEA 2020安装与使用教程详解

    JetBrains IntelliJ IDEA 2020安装与使用教程详解

    对于JetBrains IntelliJ IDEA 2020的认识 IntelliJ IDEA 2020是一款JAVA编程软件,捷克IntelliJ公司研发推出。该软件提供了一个非常强大的JAVA集成开发环境,不仅添加了对Records的完整代码洞察支持,
    2020-06-28