java版十大排序經(jīng)典算法:完整代碼(4)
更新時間：2021年07月27日 09:42:01 作者：牛哄哄的柯南
優(yōu)秀的文章也不少，但是Java完整版的好像不多，我把所有的寫一遍鞏固下，同時也真誠的希望閱讀到這篇文章的小伙伴們可以自己去從頭敲一遍，不要粘貼復(fù)制！希望我的文章對你有所幫助，每天進步一點點
計數(shù)排序
簡單解釋：這個排序算法看名字也很好理解，就是就是額外找個數(shù)組來計數(shù)，然后在這個數(shù)組從小到大或從大到小把數(shù)取出來即可。
完整代碼：
package com.keafmd.Sequence;
/**
* Keafmd
*
* @ClassName: CountSort
* @Description: 計數(shù)排序
* @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];
}
}
//建立一個用于計數(shù)的數(shù)組
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++;
}
}
}
}
桶排序
簡單解釋：就是把一個數(shù)組分成幾個桶（其實是幾個區(qū)間，從小到大或從大到小的幾個區(qū)間）裝，然后讓每個桶（區(qū)間）有序，然后取出來放一起就可以了，相當于把幾個有序的段拿出來放一起，自然還是有序的，當然需要是按照區(qū)間的順序拿了。
完整代碼：
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);
}
//計算桶的數(shù)量
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++) {
//用系統(tǒng)的排序，速度肯定沒話說
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--;
}
}
}
}
}
基數(shù)排序
簡單解釋：首先說一下，我發(fā)現(xiàn)好多人寫的基數(shù)排序只能排序正整數(shù)，其實只要處理下就可以排序含有負數(shù)的了，就是我們排序前先把所有的數(shù)整體變大（就是減上最小的負數(shù)，也就是加了），都變成正數(shù)，然后排序好之后，在減下來（加上最小的負數(shù)，也就減了）就好了?；鶖?shù)排序就是按數(shù)位排序可分為LSD（從最低位[也就是個位]開始排序）和MSD（從最高位開始排序），下面寫的事LSD基數(shù)排序?；鶖?shù)排序就是把數(shù)按位考慮，讓后我們一位數(shù)只能是[0，9]，就是我們在考慮某位（個位、百位· · ·）的時候就只看這個位的數(shù)，放到在[0，9]相應(yīng)的位置，然后順序取出，最后再按其它位這樣操作（上面說了要不從低位開始到高位，要不就是從高位到低位）
完整代碼：
package com.keafmd.Sequence;
/**
* Keafmd
*
* @ClassName: RadixSort
* @Description: 基數(shù)排序
* @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，那么把每個數(shù)都減去最小值，這樣可以保證最小的數(shù)是0
for (int i = 0; i < arr.length; i++) {
arr[i] -= min;
}
max -= min; //max也要處理！
}
//很巧妙求出最大的數(shù)有多少位
int maxLength = (max+"").length();
int[][] bucket = new int[10][arr.length]; //一個二維數(shù)組，一維代表0到9，二維存放符合數(shù)
int[] bucketElementCount = new int[10]; // 用于記錄0到9某位存在數(shù)字的個數(shù)
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;
//從左到右，從下到上取出每個數(shù)
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;
//從右到左，從下到上取出每個數(shù)
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;
//利用系統(tǒng)Collections.sort方法進行對比
//將int數(shù)組轉(zhuǎn)換為Integer數(shù)組
//1、先將int數(shù)組轉(zhuǎn)換為數(shù)值流
temparr = nums.clone();
IntStream stream = Arrays.stream(temparr);
//2、流中的元素全部裝箱，轉(zhuǎn)換為流 ---->int轉(zhuǎn)為Integer
Stream<Integer> integerStream = stream.boxed();
//3、將流轉(zhuǎn)換為數(shù)組
Integer[] integers = integerStream.toArray(Integer[]::new);
//把數(shù)組轉(zhuǎn)為List
List<Integer> tempList = new ArrayList<>(Arrays.asList(integers));
//使用Collections.sort()排序
System.out.println("使用系統(tǒng)的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;
}
});*/
//遍歷輸出結(jié)果
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();
//測試計數(shù)排序
System.out.println("測試計數(shù)排序:");
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();
//測試基數(shù)排序
System.out.println("測試基數(shù)排序:");
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();
}
}
總結(jié)
本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！
相關(guān)文章
這篇文章主要介紹了Java構(gòu)造函數(shù)，本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-09-09
這篇文章主要使介紹了Java8新特性重復(fù)注解與類型注解，文章還介紹了JDK5中的注解與之對比,感興趣的朋友可以參考下面具體文章內(nèi)容2021-09-09
這篇文章主要介紹了詳解Java進階知識注解，從注解的定義、元注解、自定義注解、注解實例這幾個方面，讓同學(xué)們更加深入的了解注解2021-04-04
這篇文章主要介紹了SpringBoot整合MyBatis筆記記錄，大家需要注意在整合mybatis之前我們需要相對應(yīng)的導(dǎo)入相關(guān)依賴,首先需要在java的目錄和resources下創(chuàng)建mapper文件夾，對SpringBoot整合MyBatis的詳細過程感興趣的朋友一起看看吧2022-05-05
這篇文章主要為大家介紹了Spring?@InitBinder注解使用及原理詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-03-03
這篇文章主要介紹了Java中HashMap的初始容量設(shè)置方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-06-06
這篇文章主要給大家介紹了關(guān)于Java中轉(zhuǎn)換器設(shè)計模式的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家學(xué)習(xí)或者使用Java具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04
這篇文章主要介紹了Spring Boot的Controller控制層和頁面,需要的朋友可以參考下2017-04-04
詳解spring mvc4使用及json 日期轉(zhuǎn)換解決方案
本篇文章主要介紹了spring mvc4使用及json 日期轉(zhuǎn)換解決方案，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01
mybatis-plus分頁如何接收前端參數(shù)limit和page
這篇文章主要介紹了mybatis-plus分頁如何接收前端參數(shù)limit和page,具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-01-01