经典十大排序算法(含升序降序,基数排序含负数排序)【Java版完整代码】【建议收藏系列】[通俗易懂]

经典十大排序算法(含升序降序,基数排序含负数排序)【Java版完整代码】【建议收藏系列】[通俗易懂]经典十大排序算法【Java版完整代码】写在前面的话十大排序算法对比冒泡排序快速排序直接选择排序堆排序归并排序插入排序希尔排序计数排序桶排序基数排序写在前面的话       虽然已经有很多人总结过这十大排序算法,优秀的文章也不少,但是Java完整版的好像不多,还存在某些文章代码存在错误的情况,同时也为了自己练手,决定把所有的写一遍巩固下,同时也真诚的希望阅读到这篇文章的小伙伴们可以自己去从头敲一遍,不要粘贴复制!希望我的文章对你有所帮助

大家好,又见面了,我是你们的朋友全栈君。

写在前面的话

       虽然已经有很多人总结过这十大排序算法,优秀的文章也不少,但是Java完整版的好像不多,还存在某些文章代码存在错误的情况,同时也为了自己练手,决定把所有的写一遍巩固下,同时也真诚的希望阅读到这篇文章的小伙伴们可以自己去从头敲一遍,不要粘贴复制!希望我的文章对你有所帮助,每天进步一点点!!!

       我用通俗的理解写下对算法的解释,对某个算法的运行过程不是很理解的话或者想看比较官方的解释的话,单独搜索某个算法,看几篇不同的解释,就可以有自己的理解了,这里我主要展示代码以及进行通俗的解释!整起来,再强调一次,一定要自己敲一遍,这样才能理解的更深刻!

十大排序算法对比

在这里插入图片描述

关于最后一列的稳定性,我稍微解释下,例如对序列:1 2 4 2 6 排序,序列中存在两个2,如果我们把这两个2标记上(让他俩不同),排序之后,前面的2还在前面,那么就称这种排序是稳定的,反之不稳定。

冒泡排序

简单解释:
       原理就如算法名字一样,就像水中的气泡一样,每次我都把最大的或最小的放到最后面,这样总共需要n-1趟即可完成排序,这就是第一层循环,第二次循环就是遍历未被固定的那些数(理解成数组左边的数,因为每层循环都会把最大或最小的数升到最右边固定起来,下次就不遍历这些数了),两层循环遍历结束后,所有的数就排好序了。
       两层循环所以冒泡排序算法的时间复杂度是O( n 2 n^{2} n2),是一个非常高的时间复杂度,我在下面的代码进行了优化,加了一个标志位,如果上一次循环未发生交换,就说明已经是有序的了,就不继续下去了,反之继续进行下一轮。

经典十大排序算法(含升序降序,基数排序含负数排序)【Java版完整代码】【建议收藏系列】[通俗易懂]

本文的图片来源网络,仅用于大家学习,侵权联系删除!(下同)

完整代码:

package com.keafmd.Sequence;

/** * Keafmd * * @ClassName: BubbleSort * @Description: 冒泡排序 * @author: 牛哄哄的柯南 * @date: 2021-06-24 10:31 */
public class BubbleSort { 
   

    //冒泡排序
    public static void bubbleSort(int[] arr, boolean ascending) { 
    //exchange标志表示为升序排序还是降序排序

        boolean flag = true; //加一个标志位,记录上一次是否发生了交换,如果是,我们则进行下一轮,如果没有,说明已经冒泡好了

        for (int i = 1; i < arr.length && flag; i++) { 
    //控制次数,第几趟排序,只需要n-1趟,有交换时进行,只有flag=false就说明上一次一个元素都没有进行交换

            /*System.out.print("第"+i+"次遍历:"); for (int i1 : arr) { System.out.print(i1+" "); } System.out.println();*/

            flag = false; //假定未交换

            for (int j = 0; j < arr.length - i; j++) { 
   

                if (ascending ? arr[j] > arr[j + 1] : arr[j] < arr[j + 1]) { 
    //控制升序还是降序
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }

            }
        }
    }

    //冒泡排序 -- 默认不传参升序
    public static void bubbleSort(int[] arr) { 
   
        bubbleSort(arr, true);
    }
}

测试代码:

升序排序(从小到大)

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[] temparr;

        //测试冒泡排序
        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();

    }
}

运行结果:

测试冒泡排序:
-66 -13 -1 1 4 9 12 25 25 26 34 47 58 99 162 10093 

降序排序(从大到小)

//测试冒泡排序
System.out.println("测试冒泡排序:");
temparr = nums.clone();
BubbleSort.bubbleSort(temparr,false);
for (int i = 0; i < temparr.length; i++) { 
   
    System.out.print(temparr[i] + " ");
}
System.out.println();

运行结果:

测试冒泡排序:
10093 162 99 58 47 34 26 25 25 12 9 4 1 -1 -13 -66 

下面几个算法的测试也就是换了下类名和方法名(换成相应的排序算法),如果想降序就在数组后面传个false即可。我就不一一复制了,我在最下面给出含所有算法的测试类,需要的自取即可。

快速排序

简单解释:
快速排序就是每次找一个基点(第一个元素),然后两个哨兵,一个从最前面往后走,一个从最后面往前面走,如果后面那个哨兵找到了一个比基点大的数停下来,前面那个哨兵找到比基点大的数停下来,然后交换两个哨兵找到的数,如果找不到最后两个哨兵就会碰到一起就结束,最后交换基点和哨兵相遇的地方的元素,然后就将一个序列分为比基点小的一部分和比基点大的一部分,然后递归左半部分和右半部分,最后的结果就是有序的了。

经典十大排序算法(含升序降序,基数排序含负数排序)【Java版完整代码】【建议收藏系列】[通俗易懂]

完整代码:

package com.keafmd.Sequence;

/** * Keafmd * * @ClassName: QuickSort * @Description: 快速排序 * @author: 牛哄哄的柯南 * @date: 2021-06-24 10:32 */
public class QuickSort { 
   

    //快速排序
    public static void quickSort(int[] arr) { 
   
        quickSort(arr, true);
    }

    public static void quickSort(int[] arr, boolean ascending) { 
   
        if (ascending) { 
   
            quickSort(arr, 0, arr.length - 1, true);
        } else { 
   
            quickSort(arr, 0, arr.length - 1, false);
        }
    }

    public static void quickSort(int[] arr, int begin, int end, boolean ascending) { 
   
        if (ascending)
            quickSort(arr, begin, end);
        else
            quickSortDescending(arr, begin, end);
    }

    //快排序升序 -- 默认
    public static void quickSort(int[] arr, int begin, int end) { 
   
        if (begin > end) { 
    //结束条件
            return;
        }
        int base = arr[begin];
        int i = begin, j = end;
        while (i < j) { 
    // 两个哨兵(i左边,j右边)没有相遇
            while (arr[j] >= base && i < j) { 
    //哨兵j没找到比base小的
                j--;
            }
            while (arr[i] <= base && i < j) { 
    //哨兵i没找到比base大的
                i++;
            }
            if (i < j) { 
    //如果满足条件则交换
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }

        }
        //最后将基准为与i和j相等位置的数字交换
        arr[begin] = arr[i];
        arr[i] = base;
        quickSort(arr, begin, i - 1); //递归调用左半数组
        quickSort(arr, i + 1, end); //递归调用右半数组

    }

    //快排序降序
    public static void quickSortDescending(int[] arr, int begin, int end) { 
   
        if (begin > end) { 
    //结束条件
            return;
        }
        int base = arr[begin];
        int i = begin, j = end;
        while (i < j) { 
    // 两个哨兵(i左边,j右边)没有相遇
            while (arr[j] <= base && i < j) { 
    //哨兵j没找到比base大的
                j--;
            }
            while (arr[i] >= base && i < j) { 
    //哨兵i没找到比base小的
                i++;
            }
            if (i < j) { 
    //如果满足条件则交换
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }

        }
        //最后将基准为与i和j相等位置的数字交换
        arr[begin] = arr[i];
        arr[i] = base;
        quickSortDescending(arr, begin, i - 1); //递归调用左半数组
        quickSortDescending(arr, i + 1, end); //递归调用右半数组

    }

}

直接选择排序

简单解释:
数组分为已排序部分(前面)和待排序序列(后面)
第一次肯定所有的数都是待排序的
从待排序的序列中找到最大或最小的那个元素,放到前面的已排序部分,然后一直找,不断缩小待排序的范围,直到所有的数都是已排序的了

经典十大排序算法(含升序降序,基数排序含负数排序)【Java版完整代码】【建议收藏系列】[通俗易懂]

完整代码:

package com.keafmd.Sequence;

/** * Keafmd * * @ClassName: SelectSort * @Description: 选择排序 * @author: 牛哄哄的柯南 * @date: 2021-06-24 10:33 */
public class SelectSort { 
   

    //直接选择排序
    public static void selectSort(int[] arr, boolean ascending) { 
   
        for (int i = 0; i < arr.length; i++) { 
   
            int m = i; //最小值或最小值的下标
            for (int j = i + 1; j < arr.length; j++) { 
   
                if (ascending ? arr[j] < arr[m] : arr[j] > arr[m]) { 
   
                    m = j; //找到待排序的数中最小或最大的那个数,记录下标
                }

            }
            //交换位置
            int temp = arr[i];
            arr[i] = arr[m];
            arr[m] = temp;

        }
    }

    public static void selectSort(int[] arr) { 
   
        selectSort(arr, true);
    }
}

堆排序

先理解下大顶堆和小顶堆,看图
大顶堆,双亲结点的值比每一个孩子结点的值都要大。根结点值最大
小顶堆,双亲结点的值比每一个孩子结点的值都要小。根结点值最小

经典十大排序算法(含升序降序,基数排序含负数排序)【Java版完整代码】【建议收藏系列】[通俗易懂]

简单解释:
构建好大顶堆或小顶堆结构,这样最上面的就是最大值或最小值,那么我们取出堆顶元素,然后重新构建结构,一直取,一直重新构建,那么最后达到排序的效果了。

经典十大排序算法(含升序降序,基数排序含负数排序)【Java版完整代码】【建议收藏系列】[通俗易懂]

完整代码:

package com.keafmd.Sequence;

/** * Keafmd * * @ClassName: HeapSort * @Description: 堆排序 * @author: 牛哄哄的柯南 * @date: 2021-06-24 10:34 */
public class HeapSort { 
   

    //堆排序
    public static void heapSort(int[] arr) { 
   
        //对传入的数组进行建立堆,这里默认建立大顶堆,进行升序排列
        heapSort(arr, true);
    }

    public static void heapSort(int[] arr, boolean maxheap) { 
   

        //1.构建大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) { 
   
            //从第一个非叶子结点从下至上,从右至左调整结构
            sift(arr, i, arr.length , maxheap);
        }

        //2.调整堆结构+交换堆顶元素与末尾元素
        for (int j = arr.length - 1; j > 0; j--) { 
   

            //现在的数组第一个就是根结点,最小值所在,进行交换,把它放到最右边
            int temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;

            //重新建立堆
            sift(arr, 0, j , maxheap); //重新对堆进行调整
        }
    }

    //建立堆的方法
    /** * 私有方法,只允许被堆排序调用 * * @param arr 要排序数组 * @param parent 当前的双亲节点 * @param len 数组长度 * @param maxheap 是否建立大顶堆 */
    private static void sift(int[] arr, int parent, int len, boolean maxheap) { 
   

        int value = arr[parent]; //先取出当前元素i

        for (int child = 2 * parent + 1; child < len; child = child * 2 + 1) { 
    //从parent结点的左子结点开始,也就是2*parent+1处开始

            if (child+1 < len && (maxheap ? arr[child] < arr[child + 1] : arr[child] > arr[child + 1])) { 
    //如果左子结点小于右子结点,child指向右子结点
                child++; //右孩子如果比左孩子大,我们就将现在的孩子换到右孩子
            }

            //判断是否符合大顶堆的特性, 如果右孩子大于双亲,自然左孩子也大于双亲,符合
            //如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
            if (maxheap ? value < arr[child] : value > arr[child]) { 
   
                arr[parent]=arr[child];
                parent = child;
            }
            else { 
   //如果不是,说明已经符合我们的要求了。
                break;
            }
        }
        arr[parent] =value; //将value值放到最终的位置


    }

}

归并排序

简单解释:
该算法是采用分治法,把数组不断分割,直至成为单个元素,然后比较再合并(合并的过程就是两部分分别从头开始比较,取出最小或最大元素的放到新的区域内,继续取两部分中最大或最小的元素,直到这两部分合并完,最后所有的都合并完,最后形成完整的有序序列)

经典十大排序算法(含升序降序,基数排序含负数排序)【Java版完整代码】【建议收藏系列】[通俗易懂]

完整代码:

package com.keafmd.Sequence;

/** * Keafmd * * @ClassName: MergeSort * @Description: 归并排序 * @author: 牛哄哄的柯南 * @date: 2021-06-24 10:35 */
public class MergeSort { 
   

    //归并排序
    public static void mergeSort(int []arr ,boolean ascending){ 
   
        int[] temp = new int[arr.length]; //在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
        mergeSort(arr,0,arr.length-1,temp,ascending);
    }
    public static void mergeSort(int []arr){ 
   
        mergeSort(arr,true);
    }

    /** * * @param arr 传入的数组 * @param left 当前子数组的起始下标 * @param right 当前子数组的结束下标 * @param temp 拷贝暂存数组 */
    public static void mergeSort(int []arr,int left,int right,int[] temp,boolean ascending){ 
   
        if(left<right){ 
    //这里是递归结束的条件,我们是对半分,那当left==right的时候肯定大家都是只有一个元素了。

            //对半分,比如总长度是10,left=0,right=9,mid=4确实是中间分了,0~4,5~9
            //当长度9,left=0,right=8,mid=4,0~4,5~8
            int mid = left + (right-left)/2; // 防止越界的写法
            //int mid = (left+right)/2;

            mergeSort(arr,left,mid,temp,ascending); //左边归并排序,使得左子序列有序
            mergeSort(arr,mid+1,right,temp,ascending); //右边归并排序,使得右子序列有序

            merge(arr,left,mid,right,temp,ascending); //将两个有序子数组合并操作
        }
    }

    private static void merge(int[] arr,int left,int mid,int right,int[] temp,boolean ascending){ 
   
        int i = left; //左序列起始下标
        int j = mid+1; //右序列起始下标
        int t = 0; //临时数组指针
        while(i<=mid&&j<=right){ 
   
            if(ascending?arr[i]<arr[j]:arr[i]>arr[j]){ 
    //比较两个序列第一个元素谁小,谁小先拷贝谁到temp,然后对应子序列下标加1
                temp[t++] = arr[i++];
            }else { 
   
                temp[t++] = arr[j++];
            }
        }

        while(i<=mid){ 
    //将左边剩余元素填充进temp中——左序列有一些数总是比右边的大的数
            temp[t++] = arr[i++];
        }

        while(j<=right){ 
    //将右序列剩余元素填充进temp中——右序列有一些数总是比左边的大的数
            temp[t++] = arr[j++];
        }

        t = 0;

        //将temp中的元素全部拷贝到原数组中
        while(left<=right){ 
   
            arr[left++] = temp[t++];
        }

    }

}

插入排序

简单解释:
最简单的理解就是打地主时我们拿到牌后的整理过程,从第二个牌(假设我们拿起来这个牌开始比较)开始,(说下升序)从后往前比较如果比前面的那个牌小,就把牌往后移动,直到找到一个合适的位置(这个位置的前面的那个牌不比这个要放下的牌大)就把这个牌放到这个位置,慢慢的前面的部分变得有序,直至全部有序即可。

经典十大排序算法(含升序降序,基数排序含负数排序)【Java版完整代码】【建议收藏系列】[通俗易懂]

完整代码:

package com.keafmd.Sequence;

/** * Keafmd * * @ClassName: StraghtInsertSort * @Description: 插入排序 * @author: 牛哄哄的柯南 * @date: 2021-06-24 10:36 */
public class StraghtInsertSort { 
   
    //插入排序
    public static void straghtInsertSort(int[] arr) { 
   
        straghtInsertSort(arr, true);//默认进行升序
    }

    public static void straghtInsertSort(int[] arr, boolean ascending) { 
   

        for (int i = 1; i < arr.length; i++) { 
   
            int temp = arr[i];
            int j=0; //这就是那个合适的位置
            for (j = i - 1; j >= 0 && (ascending ? temp < arr[j] : temp > arr[j]); j--) { 
   
                arr[j + 1] = arr[j];
            }
            //把牌放下,为啥是j+1,
            //是因为上面的循环遍历到不符合情况的时候 j是合适的位置的前面的那个数的位置
            //有点拗口,但是就是这个意思,看图方便理解下
            arr[j + 1] = temp;


        }

    }
}

希尔排序

简单解释:
希尔排序是插入排序的改进版,我们理解一个叫做下标差的的东西,也就是下面那个图中的增量d,初始下标差为arr.length/2,然后继续/2,对在同一下标差(相当于把这几个数单独拿出来了)的若干个数进行插入排序即可。

经典十大排序算法(含升序降序,基数排序含负数排序)【Java版完整代码】【建议收藏系列】[通俗易懂]
经典十大排序算法(含升序降序,基数排序含负数排序)【Java版完整代码】【建议收藏系列】[通俗易懂]
完整代码:

package com.keafmd.Sequence;

/** * Keafmd * * @ClassName: ShellSort * @Description: 希尔排序 * @author: 牛哄哄的柯南 * @date: 2021-06-24 10:39 */
public class ShellSort { 
   

    public static void shellSort(int[] arr) { 
   
        shellSort(arr,true);
    }

    public static void shellSort(int[] arr,boolean ascending) { 
   

        for(int d = arr.length/2;d>0;d/=2){ 
   

            for(int i=d;i< arr.length;i++){ 
   
                int temp = arr[i];
                int j=0;
                for(j=i-d;j>=0&&(ascending?temp<arr[j]:temp>arr[j]);j-=d){ 
   
                    arr[j+d]=arr[j];
                }
                arr[j+d] = temp;
            }
        }

    }
}

计数排序

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

经典十大排序算法(含升序降序,基数排序含负数排序)【Java版完整代码】【建议收藏系列】[通俗易懂]

完整代码:

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++;
            }
        }

    }
}

桶排序

简单解释:
就是把一个数组分成几个桶(其实是几个区间,从小到大或从大到小的几个区间)装,然后让每个桶(区间)有序,然后取出来放一起就可以了,相当于把几个有序的段拿出来放一起,自然还是有序的,当然需要是按照区间的顺序拿了。

经典十大排序算法(含升序降序,基数排序含负数排序)【Java版完整代码】【建议收藏系列】[通俗易懂]

完整代码:

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]相应的位置,然后顺序取出,最后再按其它位这样操作(上面说了要不从低位开始到高位,要不就是从高位到低位)

经典十大排序算法(含升序降序,基数排序含负数排序)【Java版完整代码】【建议收藏系列】[通俗易懂]

完整代码:

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

    }

}

每天进步一点点!
不进则退!

版权声明:
原创博主:牛哄哄的柯南
博主原文链接:https://keafmd.blog.csdn.net/

看完如果对你有帮助,感谢点赞支持!
如果你是电脑端,看到右下角的 “一键三连” 了吗,没错点它[哈哈]

在这里插入图片描述
加油!

共同努力!

Keafmd

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/132064.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • c#防止代码被反编译_C程序反编译

    c#防止代码被反编译_C程序反编译1.在编码过程中尽量使用private/internal关键词修饰class、方法和字段名称2.编码过程尽可能少地使用public修饰class、方法和字段名称3.避免使用反射和序列化,反序列化操作4.添加生成事件,调用Dotfuscator进行代码混淆if$(ConfigurationName)==Debug”C:/ProgramFiles(x86)/MicrosoftVisualStudio14.0/PreEmptiveSolutions/Dotfuscatora

  • 面试题集锦(一)

    #一、选择题(32分)#1、python不支持的数据类型有(A)#A、char#B、int#C、float#D、list#2.下列执行的结果是(E)#x='foo&#39

  • 基于STM32F4单片机对步进电机的控制(有代码)「建议收藏」

    基于STM32F4单片机对步进电机的控制(有代码)「建议收藏」步进电机是将电脉冲控制信号转变为角位移或线位移的一种常用的数字控制执行元件,又称为脉冲电机。在驱动电源的作用下,步进电机受到脉冲的控制,其转子的角位移量和速度严格地与输入脉冲的数量和脉冲频率成正比。步进电机每接收一个电脉冲,转子就转过一个相应的角度(步距角)。改变通电顺序可改变步进电动机的旋转方向;改变通电频率可改变步进电动机的转速。因此,通过控制输入电脉冲的数目、频率及电动机绕组的通电顺序就可以…

  • 正则表达式(.*?)惰性匹配()

    正则表达式(.*?)惰性匹配()没什么可说的看这儿就行了,,特别是最后一条。1、.匹配任意除换行符“\n”外的字符;2、*表示匹配前一个字符0次或无限次;3、+或*后跟?表示非贪婪匹配,即尽可能少的匹配,如*?重复任意次,但尽可能少重复;4、.*?表示匹配任意数量的重复,但是在能使整个匹配成功的前提下使用最少的重复。如:a.*?b匹配最短的,以a开始,以b结束的字符串。如果把它应用于aabab的话,它会匹配aab……

  • Qt 音乐播放器「建议收藏」

    Qt 音乐播放器「建议收藏」一、实现功能:1、读取歌曲文件,实现歌曲的播放;2、采用QtDesigner实现歌曲的暂停和播放,歌曲名列表和当前播放歌曲名的显示,上一曲和下一曲歌曲的更换,播放模式的设置,音量的改变,歌曲播放进度的改变;3、读取歌词文件,实现歌词的显示;4、利用QSetting增加歌曲文件和歌词文件的设置功能;5、界面汉化;6、使用CSS进

  • ribbon负载均衡策略有哪几种_负载均衡策略的是

    ribbon负载均衡策略有哪几种_负载均衡策略的是目录1.基于Ribbon方式的负载均衡,Netflix默认提供了七种负载均衡策略,2.@LoadBalanced1.基于Ribbon方式的负载均衡,Netflix默认提供了七种负载均衡策略,对于SpringCloudAlibaba解决方案中又提供了NacosRule策略,默认的负载均衡策略是轮训策略。如图所示:当系统提供的负载均衡策略不能满足我们需求时,我们还可以基于IRule接口自己定义策略.Ribbon是什么?(Netflix公司提供的负载均衡…

    2022年10月13日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号