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

Posted on by

計數排序

簡單解釋：這個排序算法看名字也很好理解，就是就是額外找個數組來計數，然後在這個數組從小到大或從大到小把數取出來即可。

完整代碼：

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

總結

本篇文章就到這裡瞭，希望能給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容！

推薦閱讀：