目录计数排序完整代码：桶排序完整代码：基数排序完整代码：完整测试类总结
计数排序
简单解释：这个排序算法看名字也很好理解，就是就是额外找个数组来计数，然后在这个数组从小到大或从大到小把数取出来即可。
完整代码：
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++; } } }}
桶排序
简单解释：就是把一个数组分成几个桶（其实是几个区间，从小到大或从大到小的几个区间）装，然后让每个桶（区间）有序，然后取出来放一起就可以了，相当于把几个有序的段拿出来放一起，自然还是有序的，当然需要是按照区间的顺序拿了。
完整代码：
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]相应的位置，然后顺序取出，最后再按其它位这样操作（上面说了要不从低位开始到高位，要不就是从高位到低位）
完整代码：
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; } } }}
完整测试类
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(); }}
总结
本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注的更多内容！
不要识途去改变他人，同样，也不要被他人所改变。改了，就不是自己了。
