快捷導(dǎo)航

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

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

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

計(jì)數(shù)排序

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

完整代碼：

package com.keafmd.Sequence;
/**
 * Keafmd
 *
 * @ClassName: CountSort
 * @Description: 計(jì)數(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];
            }
        }
        //建立一個(gè)用于計(jì)數(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++;
            }
        }
    }
}

桶排序

簡單解釋：就是把一個(gè)數(shù)組分成幾個(gè)桶（其實(shí)是幾個(gè)區(qū)間，從小到大或從大到小的幾個(gè)區(qū)間）裝，然后讓每個(gè)桶（區(qū)間）有序，然后取出來放一起就可以了，相當(dāng)于把幾個(gè)有序的段拿出來放一起，自然還是有序的，當(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;
        }
        //計(jì)算最大值與最小值
        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);
        }
        //計(jì)算桶的數(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<>());
        }
        //將每個(gè)元素放入桶中
        for(int i=0;i<arr.length;i++){
            int num = (arr[i]-min)/ (arr.length);
            bucketArr.get(num).add(arr[i]);
        }
        //對(duì)每個(gè)桶進(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ù)，其實(shí)只要處理下就可以排序含有負(fù)數(shù)的了，就是我們排序前先把所有的數(shù)整體變大（就是減上最小的負(fù)數(shù)，也就是加了），都變成正數(shù)，然后排序好之后，在減下來（加上最小的負(fù)數(shù)，也就減了）就好了?；鶖?shù)排序就是按數(shù)位排序可分為LSD（從最低位[也就是個(gè)位]開始排序）和MSD（從最高位開始排序），下面寫的事LSD基數(shù)排序?；鶖?shù)排序就是把數(shù)按位考慮，讓后我們一位數(shù)只能是[0，9]，就是我們?cè)诳紤]某位（個(gè)位、百位· · ·）的時(shí)候就只看這個(gè)位的數(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，那么把每個(gè)數(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]; //一個(gè)二維數(shù)組，一維代表0到9，二維存放符合數(shù)
        int[] bucketElementCount = new int[10]; // 用于記錄0到9某位存在數(shù)字的個(gè)數(shù)
        for (int i = 0 ,n = 1 ; i < maxLength ; i++,n*=10) { //個(gè)位 十位 百位 這樣遍歷
            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;
                //從左到右，從下到上取出每個(gè)數(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;
                //從右到左，從下到上取出每個(gè)數(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)行對(duì)比
        //將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()的對(duì)比:");
        //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();

        //測試計(jì)數(shù)排序
        System.out.println("測試計(jì)數(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();
    }
}