服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - Java教程 - java版十大排序经典算法:完整代码(4)

java版十大排序经典算法:完整代码(4)

2021-10-24 14:52牛哄哄的柯南 Java教程

优秀的文章也不少,但是Java完整版的好像不多,我把所有的写一遍巩固下,同时也真诚的希望阅读到这篇文章的小伙伴们可以自己去从头敲一遍,不要粘贴复制!希望我的文章对你有所帮助,每天进步一点点

计数排序

简单解释:这个排序算法看名字也很好理解,就是就是额外找个数组来计数,然后在这个数组从小到大或从大到小把数取出来即可。

java版十大排序经典算法:完整代码(4)

完整代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package com.keafmd.Sequence;
/**
 * Keafmd
 *
 * @ClassName: CountSort
 * @Description: 计数排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 11:31
 */
public class CountSort {
    public static void countSort(int[]arr){
        countSort(arr,true);
    }
    public static void countSort(int[]arr,boolean ascending){
        int d,min=arr[0],max=arr[0];
        //找出最大、最小值
        for(int i=0;i< arr.length;i++){
            if(arr[i]<min){
                min =arr[i];
            }
            if(arr[i]>max){
                max = arr[i];
            }
        }
        //建立一个用于计数的数组
        d = min;
        int[] count_map = new int[max-min+1];
        for(int i=0;i< arr.length;i++){
            count_map[arr[i]-d]++;
        }
        int k =0;
        if(ascending){
            for(int i=0;i< arr.length;){
                if(count_map[k]>0){
                    arr[i] = k+d;
                    i++;
                    count_map[k]--;
                }else
                    k++;
            }
        }else {
            for(int i=arr.length-1;i>=0;){
                if(count_map[k]>0){
                    arr[i] = k+d;
                    i--;
                    count_map[k]--;
                }else
                    k++;
            }
        }
    }
}

桶排序

简单解释:就是把一个数组分成几个桶(其实是几个区间,从小到大或从大到小的几个区间)装,然后让每个桶(区间)有序,然后取出来放一起就可以了,相当于把几个有序的段拿出来放一起,自然还是有序的,当然需要是按照区间的顺序拿了。

java版十大排序经典算法:完整代码(4)

完整代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package com.keafmd.Sequence;
import java.util.ArrayList;
import java.util.Collections;
/**
 * Keafmd
 *
 * @ClassName: BucketSort
 * @Description: 桶排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 13:32
 */
public class BucketSort {
    public static void bucketSort(int[] arr){
        bucketSort(arr,true);
    }
    public static void bucketSort(int[] arr,boolean ascending){
        if(arr==null||arr.length==0){
            return;
        }
        //计算最大值与最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i=0;i<arr.length;i++){
            max = Math.max(arr[i],max);
            min = Math.min(arr[i],min);
        }
        //计算桶的数量
        int bucketNUm = (max-min)/ arr.length+1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNUm);
        for(int i=0;i<bucketNUm;i++){
            bucketArr.add(new ArrayList<>());
        }
        //将每个元素放入桶中
        for(int i=0;i<arr.length;i++){
            int num = (arr[i]-min)/ (arr.length);
            bucketArr.get(num).add(arr[i]);
        }
        //对每个桶进行排序
        for (int i = 0; i < bucketArr.size(); i++) {
            //用系统的排序,速度肯定没话说
            Collections.sort(bucketArr.get(i));
        }
        //将桶中元素赋值到原序列
        int index;
        if(ascending){
            index=0;
        }else{
            index=arr.length-1;
        }
        for(int i=0;i<bucketArr.size();i++){
            for(int j= 0;j<bucketArr.get(i).size();j++){
                arr[index] = bucketArr.get(i).get(j);
                if(ascending){
                    index++;
                }else{
                    index--;
                }
            }
        }
    }
}

基数排序

简单解释:首先说一下,我发现好多人写的基数排序只能排序正整数,其实只要处理下就可以排序含有负数的了,就是我们排序前先把所有的数整体变大(就是减上最小的负数,也就是加了),都变成正数,然后排序好之后,在减下来(加上最小的负数,也就减了)就好了。基数排序就是按数位排序可分为LSD(从最低位[也就是个位]开始排序)和MSD(从最高位开始排序),下面写的事LSD基数排序。基数排序就是把数按位考虑,让后我们一位数只能是[0,9],就是我们在考虑某位(个位、百位· · ·)的时候就只看这个位的数,放到在[0,9]相应的位置,然后顺序取出,最后再按其它位这样操作(上面说了要不从低位开始到高位,要不就是从高位到低位)

java版十大排序经典算法:完整代码(4)

完整代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package com.keafmd.Sequence;
/**
 * Keafmd
 *
 * @ClassName: RadixSort
 * @Description: 基数排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 14:32
 */
public class RadixSort {
    public static void radixSort(int[] arr){
        radixSort(arr,true);
    }
    public static void radixSort(int[]arr,boolean ascending){
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        //求出最大值、最小值
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        if (min<0) { //如果最小值小于0,那么把每个数都减去最小值,这样可以保证最小的数是0
            for (int i = 0; i < arr.length; i++) {
                arr[i] -= min;
            }
            max -= min; //max也要处理!
        }
        //很巧妙求出最大的数有多少位
        int maxLength = (max+"").length();
        int[][] bucket = new int[10][arr.length]; //一个二维数组,一维代表0到9,二维存放符合数
        int[] bucketElementCount = new int[10]; // 用于记录0到9某位存在数字的个数
        for (int i = 0 ,n = 1 ; i < maxLength ; i++,n*=10) { //个位 十位 百位 这样遍历
            for (int j = 0; j < arr.length ; j++) {
                int value = arr[j]/n % 10;
                bucket[value][bucketElementCount[value]] = arr[j];
                bucketElementCount[value]++;
            }
            //升序
            if(ascending) {
                int index = 0;
                //从左到右,从下到上取出每个数
                for (int j = 0; j < bucketElementCount.length; j++) {
                    if (bucketElementCount[j] != 0) {
                        for (int k = 0; k < bucketElementCount[j]; k++) {
                            arr[index] = bucket[j][k];
                            index++;
                        }
                    }
                    bucketElementCount[j] = 0;
                }
            }else { // 降序
                int index=0;
                //从右到左,从下到上取出每个数
                for (int j = bucketElementCount.length-1; j >=0; j--) {
                    if (bucketElementCount[j] != 0) {
                        for (int k = 0; k <bucketElementCount[j]; k++) {
                            arr[index] = bucket[j][k];
                            index++;
                        }
                    }
                    bucketElementCount[j] = 0;
                }
            }
 
            /*for (int i1 = 0; i1 < arr.length; i1++) {
                System.out.print(arr[i1]+" ");
            }
            System.out.println();*/
 
        }
        if (min<0){
            for (int i = 0; i < arr.length ; i++) {
                arr[i] += min;
            }
        }
    }
}

完整测试类

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
package com.keafmd.Sequence;
import java.util.*;
import java.util.stream.IntStream;
import java.util.stream.Stream;
/**
 * Keafmd
 *
 * @ClassName: Sort
 * @Description: 十大排序算法测试类
 * @author: 牛哄哄的柯南
 * @date: 2021-06-16 21:27
 */
public class Sort {
 
    public static void main(String[] args) {
        int[] nums = {12, 4, 25, 47, 58, 34, 25, 9, 99, 26, 1, -13, 162, 10093, -66, -1};
//        int[] nums = {12, 43,56,42,26,11};
        int[] temparr;
        //利用系统Collections.sort方法进行对比
        //将int数组转换为Integer数组
        //1、先将int数组转换为数值流
        temparr = nums.clone();
        IntStream stream = Arrays.stream(temparr);
        //2、流中的元素全部装箱,转换为流 ---->int转为Integer
        Stream<Integer> integerStream = stream.boxed();
        //3、将流转换为数组
        Integer[] integers = integerStream.toArray(Integer[]::new);
        //把数组转为List
        List<Integer> tempList = new ArrayList<>(Arrays.asList(integers));
        //使用Collections.sort()排序
        System.out.println("使用系统的Collections.sort()的对比:");
        //Collections.sort
        Collections.sort(tempList, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
                //return o2-o1;
            }
        });
        //tempList.sort 也可以排序
       /* tempList.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //return o1-o2;
                return o2-o1;
            }
        });*/
        //遍历输出结果
        for (Integer integer : tempList) {
            System.out.print(integer+" ");
        }
        System.out.println();
        //测试冒泡排序
        System.out.println("测试冒泡排序:");
        temparr = nums.clone();
        BubbleSort.bubbleSort(temparr);
        //降序
        //BubbleSort.bubbleSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();
        //测试快速排序
        System.out.println("测试快速排序:");
        temparr = nums.clone();
        QuickSort.quickSort(temparr);
        //QuickSort.quickSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();
        //测试直接选择排序
        System.out.println("测试直接选择排序:");
        temparr = nums.clone();
        SelectSort.selectSort(temparr);
        //SelectSort.selectSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();
        //测试堆排序
        System.out.println("测试堆排序:");
        temparr = nums.clone();
        HeapSort.heapSort(temparr);
        //HeapSort.heapSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();
        //测试归并排序
        System.out.println("测试归并排序:");
        temparr = nums.clone();
        MergeSort.mergeSort(temparr);
        //MergeSort.mergeSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();
        //测试插入排序
        System.out.println("测试插入排序:");
        temparr = nums.clone();
        StraghtInsertSort.straghtInsertSort(temparr);
        //StraghtInsertSort.straghtInsertSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();
 
        //测试希尔排序
        System.out.println("测试希尔排序:");
        temparr = nums.clone();
        ShellSort.shellSort(temparr);
        //ShellSort.shellSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();
 
        //测试计数排序
        System.out.println("测试计数排序:");
        temparr = nums.clone();
        CountSort.countSort(temparr);
        //CountSort.countSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();
 
        //测试桶排序
        System.out.println("测试桶排序:");
        temparr = nums.clone();
        BucketSort.bucketSort(temparr);
        //BucketSort.bucketSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();
        //测试基数排序
        System.out.println("测试基数排序:");
        temparr = nums.clone();
        RadixSort.radixSort(temparr);
        //RadixSort.radixSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();
    }
}

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注服务器之家的更多内容!

原文链接:https://blog.csdn.net/weixin_43883917/article/details/118193663

延伸 · 阅读

精彩推荐
  • Java教程eclipse创建springboot项目的三种方式总结

    eclipse创建springboot项目的三种方式总结

    这篇文章主要介绍了eclipse创建springboot项目的三种方式,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...

    无敌mouse5032021-09-24
  • Java教程Spring Boot2.0实现静态资源版本控制详解

    Spring Boot2.0实现静态资源版本控制详解

    这篇文章主要给大家介绍了关于Spring Boot2.0实现静态资源版本控制的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考...

    小卖铺的老爷爷8842021-06-18
  • Java教程完美解决Eclipse 项目有红感叹号的问题

    完美解决Eclipse 项目有红感叹号的问题

    下面小编就为大家带来一篇完美解决Eclipse 项目有红感叹号的问题。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...

    jingxian3222020-07-27
  • Java教程Json字符串与Object、List、Map的互转工具类

    Json字符串与Object、List、Map的互转工具类

    今天小编就为大家分享一篇关于Json字符串与Object、List、Map的互转工具类,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一...

    执笔记忆的空白4292021-06-21
  • Java教程实例讲解Java并发编程之闭锁

    实例讲解Java并发编程之闭锁

    这篇文章主要介绍了实例讲解Java并发编程之闭锁,闭锁相当于一扇门,在闭锁到达结束状态之前,这扇门一直是关闭着的,没有任何线程可以通过,当到达结束状...

    junjie3122019-12-16
  • Java教程java异常级别与捕获的示例代码

    java异常级别与捕获的示例代码

    本次模拟一个异常实例,验证一下异常的捕获,通过实例代码给大家解析java异常级别与捕获的操作方法,感兴趣的朋友跟随小编一起看看吧...

    G_whang7472021-10-06
  • Java教程Java 关键字 速查表介绍

    Java 关键字 速查表介绍

    下面小编就为大家带来一篇Java 关键字 速查表介绍。小编觉得听不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...

    Java教程网5042020-09-21
  • Java教程浅谈java中replace()和replaceAll()的区别

    浅谈java中replace()和replaceAll()的区别

    这篇文章主要介绍了java中replace()和replaceAll()的区别,两者都是常用的替换字符的方法,感兴趣的小伙伴们可以参考一下 ...

    lijiao1872020-01-16