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

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

目录计数排序完整代码：桶排序完整代码：基数排序完整代码：完整测试类总结

计数排序

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

完整代码：

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 =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 buhttp://cketSort(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

max = Math.max(arr[i],max);

min = Math.min(arr[i],min);

}

//计算桶的数量

int bucketNUm = (max-min)/ arr.length+1;

ArrayList> bucketArr = new ArrayList<>(bucketNUm);

for(int i=0;i

bucketArr.add(new ArrayList<>());

}

//将每个元素放入桶中

for(int i=0;i

int num = (arr[i]-min)/ (arr.length);

bucketArr.get(num).add(arr[i]);

}

//对每个桶进行排序

for (int i = 0chLWWWTKF; 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

for(int j= 0;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

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 integerStream = stream.boxed();

//3、将流转换为数组

Integer[] integers = integerStream.toArray(Integer[]::new);

//把数组转为List

List tempList = new ArrayList<>(Arrays.asList(integers));

//使用Collections.sort()排序

System.out.println("使用系统的Collections.sort()的对比:");

//Collections.sort

Collections.sort(tempList, new Comparator() {

@Override

public int compare(Integer o1, Integer o2) {

return o1-o2;

//return o2-o1;

}

});

//tempList.sort 也可以排序

/* tempList.sort(new Comparator() {

@Override

public int compare(Integer o1, Integer o2) {

//return o1-o2;

return o2-o1;chLWWWTKF

}

});*/

//遍历输出结果

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();

}

}

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。