快捷導(dǎo)航

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

更新時間：2021年07月27日 09:42:01 作者：牛哄哄的柯南

優(yōu)秀的文章也不少，但是Java完整版的好像不多，我把所有的寫一遍鞏固下，同時也真誠的希望閱讀到這篇文章的小伙伴們可以自己去從頭敲一遍，不要粘貼復(fù)制！希望我的文章對你有所幫助，每天進(jìn)步一點點

計數(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ū)間）有序，然后取出來放一起就可以了，相當(dāng)于把幾個有序的段拿出來放一起，自然還是有序的，當(dāng)然需要是按照區(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]);
        }
        //對每個桶進(jìn)行排序
        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ù)，其實只要處理下就可以排序含有負(fù)數(shù)的了，就是我們排序前先把所有的數(shù)整體變大（就是減上最小的負(fù)數(shù)，也就是加了），都變成正數(shù)，然后排序好之后，在減下來（加上最小的負(fù)數(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方法進(jìn)行對比
        //將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();
    }
}