idea离线安装 JAVA学习 另类堆栈 mongoose canvas cron flowjs vue绑定事件 vue实现原理 郑州小程序公司 pmp视频教程 flink教程视频 python转16进制 datetimepicker赋值 linux管道符 matlab中不等于怎么表示 重置hosts range函数python python正则提取字符串 python抛出异常 python变量类型 python创建文件 javafile java使用正则表达式 java初级教程 java中的继承 java代码注释 java中string的方法 javalist数组 linux服务器登录 lanhelper unix操作系统下载 黑帮之地修改器 狮子狗出装 卡巴斯基离线升级包 服务器系统安装 生存猎人属性 3d软件下载 明解c语言 汉仪文黑
当前位置: 首页 > 学习教程  > 编程语言

Java学习-番外篇(十大经典排序方法 更新ing)

2020/10/8 20:06:13 文章标签:

十大经典排序方法目录十大经典排序算法一、冒泡排序二、选择排序三、插入排序四、希尔排序五、桶排序十大经典排序算法 一、冒泡排序 算法步骤: 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 对每一对相邻元素作同样的工作,从开始…

十大经典排序方法目录

  • 十大经典排序算法
    • 一、冒泡排序
    • 二、选择排序
    • 三、插入排序
    • 四、希尔排序
    • 五、桶排序

十大经典排序算法

一、冒泡排序

       算法步骤:

       比较相邻的元素。如果第一个比第二个大,就交换他们两个。

       对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

       针对所有的元素重复以上的步骤,除了最后一个。

       持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

       动图演示:
在这里插入图片描述
       代码演示:(在20个范围在1~100的整数里进行排序)

import java.util.Random;

public class Practice {
    public static void main(String[] args){
            Random rand = new Random();
        int[] arr = new int[20];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=1+rand.nextInt(100);
        }
        for (int i : arr) {
            System.out.print(i+"\t");
        }
        System.out.println();
        //冒泡排序
        for (int i = 0,t; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j]>arr[j+1]){
                    t=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=t;
                }
            }
        }
        for (int i : arr) {
            System.out.print(i+"\t");
        }
    }
}

       代码结果:

70	10	9	15	97	61	26	69	75	19	66	57	79	12	30	65	44	96	94	63	
9	10	12	15	19	26	30	44	57	61	63	65	66	69	70	75	79	94	96	97	

二、选择排序

       算法步骤:

       首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。

       再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

       重复第二步,直到所有元素均排序完毕。

       动图演示:

![在这里插入图片描述](https://img-blog.csdnimg.cn/20201008192945539.gif#pic_center)

       代码演示:(在20个范围在1~100的整数里进行排序)

import java.util.Random;

public class Practice {
    public static void main(String[] args){
            Random rand = new Random();
        int[] arr = new int[20];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=1+rand.nextInt(100);
        }
        for (int i : arr) {
            System.out.print(i+"\t");
        }
        System.out.println();
       //选择排序
        for (int i = 0,maxIx=0,maxVarIx=0,t,j; i < arr.length; i++) {
            maxIx=arr.length-i-1;
            maxVarIx=0;
            for ( j = 1; j <=maxIx ; j++) {
                if(arr[j]>arr[maxVarIx]){
                    maxVarIx=j;
                }
            }
            if(maxIx!=maxVarIx){
                t=arr[maxIx];
                arr[maxIx]=arr[maxVarIx];
                arr[maxVarIx]=t;
            }
        }
        for (int i : arr) {
            System.out.print(i+"\t");
        }
    }
}

       代码结果:

82	23	3	54	57	70	43	10	17	76	35	89	64	59	69	89	74	12	85	96	
3	10	12	17	23	35	43	54	57	59	64	69	70	74	76	82	85	89	89	96	

三、插入排序

       算法步骤:

       将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

       从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

       动图演示:
在这里插入图片描述
       代码演示:(在20个范围在1~100的整数里进行排序)

import java.util.Random;

public class Practice {
    public static void main(String[] args){
            Random rand = new Random();
        int[] arr = new int[20];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=1+rand.nextInt(100);
        }
        for (int i : arr) {
            System.out.print(i+"\t");
        }
        System.out.println();
        //插入排序
        for (int i = 1,t,j; i < arr.length; i++) {
            t=arr[i];
            for (j = i-1; j >=0 && arr[j]>t ; j--) {
                arr[j+1]=arr[j];
            }
            arr[j+1]=t;
        }
        for (int i : arr) {
            System.out.print(i+"\t");
        }
    }
}

       代码结果:

21	81	93	55	76	28	56	78	20	73	33	68	66	2	67	32	78	31	52	85	
2	20	21	28	31	32	33	52	55	56	66	67	68	73	76	78	78	81	85	93	

四、希尔排序

       希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本

       在进行插入排序之前,先按照不同的间隔进行两个之间的比较,间隔为数组长度的一半,比完一次按照顺序还是降序的要求交换位置,间隔再减半,直至间隔小于等于2;

       代码演示:(在20个范围在1~100的整数里进行排序)

import java.util.Random;

public class Practice {
    public static void main(String[] args){
        Random rand = new Random();
        int[] arr = new int[20];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=1+rand.nextInt(100);
        }
        for (int i : arr) {
            System.out.print(i+"\t");
        }
        System.out.println();
        //希尔排序
        int step =arr.length;
        for (step = arr.length/2; step >=2 ; step/=2) {
            for (int i = 0,t; i < arr.length/2; i++) {
                if(arr[i]>arr[i+step]){
                    t=arr[i];
                    arr[i]= arr[i+step];
                    arr[i+step]=t;
                }
            }
        }
        for (int i = 1,j,t; i < arr.length; i++) {
            t=arr[i];
            for (j = i-1; j >=0 && arr[j]>t ; j--) {
                arr[j+1]=arr[j];
            }
            arr[j+1]=t;
        }
        for (int i : arr) {
            System.out.print(i+"\t");
        }
    }
}

       代码结果:

99	19	11	1	77	39	44	16	24	92	97	56	25	69	30	72	22	53	51	82	
1	11	16	19	22	24	25	30	39	44	51	53	56	69	72	77	82	92	97	99	

五、桶排序

       演示图:

       先把元素分布在桶中:
在这里插入图片描述
       然后元素在每个桶中排序,最后再依次从桶里拿回元素
在这里插入图片描述

       代码演示:(在20个范围在1~100的整数里进行排序)

       此时用的桶排序思想为先按照每个数的个位数进行排序,取出之后再按照每个数的十位数进行排序后取出,最后达到顺序排列

import java.util.Random;

public class Practice {
    public static void main(String[] args){
        Random rand = new Random();
        int[] arr = new int[20];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=1+rand.nextInt(100);
        }
        for (int i : arr) {
            System.out.print(i+"\t");
        }
        System.out.println();
        //桶排序
        final int U=10;
        int[][] bucket= new int[U][arr.length];
        int[] ixs = new int[U];
        for (int i=1,t, count;; i*=10) {
            //每个位数放之前都要初始化计数
            count = 0;
            //把数组的元素丢入对应的桶内
            for (int j = 0; j <arr.length ; j++) {
                count=(t=arr[j]/i)>=1?++count:count;
                bucket[t%=U][ixs[t]++]=arr[j];
            }
            //判断对应位数是否存在
            if(count==0){break;}
            //把对应位数排序好之后的数依次放回数组中
            for (int j = 0,k,ix=0; j < U; j++) {
                for ( k = 0; k <ixs[j] ; k++) {
                    arr[ix++]=bucket[j][k];
                }
            }
            //计数清零
            for (int j = 0; j < ixs.length; j++) {
                ixs[j]=0;
            }
        }
        
        for (int i : arr) {
            System.out.print(i+"\t");
        }
    }
}

       代码结果:

25	48	42	68	73	35	14	96	91	43	74	94	9	6	83	83	34	11	55	77	
6	9	11	14	25	34	35	42	43	48	55	68	73	74	77	83	83	91	94	96

PS:作者是一枚刚入编程的小白,如果有写错或者写的不好的地方,欢迎各位大佬在评论区留下宝贵的意见或者建议,敬上!如果这篇博客对您有帮助,希望您可以顺手帮我点个赞!不胜感谢!


原创作者:wsjslient

作者主页:https://blog.csdn.net/wsjslient

参考文档:https://www.runoob.com/java/java-tutorial.html



本文链接: http://www.dtmao.cc/news_show_250193.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?