【算法】十大排序算法以及具体用例算法题

叁歲伎倆 2024-03-17 16:10 16阅读 0赞

#### 文章目录 ####

*  1:冒泡排序
 *  2:选择排序
 *  3:插入排序
 *  4:希尔排序
 *  5:堆排序
 *  6:计数排序
 *  7:基数排序
 *  8:快速排序
 *  9:归并排序
 *  10:桶排序

[源代码下载][Link 1]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAU2VyZW5kaXBpdHktLQ_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 1:冒泡排序 ##

/*
     * 冒泡排序是内部排序
     * 冒泡排序将会每一次都从头开始遍历
     * 每一次遍历都会把最大的数据放到最后一个
     * 因此每一次都可以少遍历一个元素
    */
    public static void bubbleSort(int[]arr){
        
            boolean flag = false;
            out:
            for (int i = 0; i < arr.length; i++) {
        
                flag = false;
                for (int j = 0; j < arr.length - 1 - i; j++) {
        
                    if (arr[j] > arr[j + 1]) {
         //从小到大 >改为<就是从大到小
                        arr[j] ^= arr[j + 1];
                        arr[j + 1] ^= arr[j];
                        arr[j] ^= arr[j + 1];
                        flag = true;
                    }
                }
                if (flag == false) {
         //如果内层循环一次没修改过位置说明已经有序
                    break out;
                }
            }
            System.out.println(Arrays.toString(arr));
        }
        public static void main(String[] args) {
        
            int[] arr = new int[]{
        3, 5412, 12, 3, 513, -1, 6, -324};
            bubbleSort(arr);
        }

## 2:选择排序 ##

/*
     * 选择排序也是内部排序
     * 选择排序的思路是每一次都遍历整个二维数组
     * 然后从中找出最小的数据,与当前外层循环对应的i的数据交换位置(注意是交换位置)
     * 假设i=2 然后要交换的是10这个数据 那么这时arr[2]=10 arr[10原先位置]=arr[2]
     * 每次开头的位置都是+1的也就是一开是0 之后是1 2 3...
    */
     public static void selectionSort(int[]arr){
        
            for (int i = 0; i < arr.length - 1; i++) {
        
                int min = arr[i];
                int p = i; //让p先赋值为i 这样可以防止由于没有进入if语句而导致p是之前的值
                for (int j = i + 1; j < arr.length; j++) {
        
                    if (min > arr[j]) {
         //遍历找到最小值所在位置
                        min = arr[j];
                        p = j;
                    }
                }
                if (p != i) {
         //如果p不是当前位置的数据就进行修改
                    arr[p] = arr[i];//这个标志位至关重要哦
                    arr[i] = min;
                }
                System.out.println("第"+(i+1)+"轮结果是"+ Arrays.toString(arr));
            }
        }
        public static void main(String[] args) {
        
            int[] arr = new int[]{
        3, 5412, 12, 3, 513, -1, 6, 123,123,234,5345,-324};
            selectionSort(arr);
        }

## 3:插入排序 ##

/*
     * 每次都判断当前数据与前面一个数据是否位置不对
     * 如果不对 那么将当前数据设置为哨兵节点
     * 然后再当前数据下标-1开始遍历 遍历到直到arr[0]>arr[i]为止
     * 如果当前循环arr[0]<arr[i]那么执行arr[i+1]=arr[i]
     * 也就是将这个数据后移 为插入更小的数据arr[0]做准备
     * 最后一次退出之后由于执行了i--操作才退出
     * 所以退出时的前一个位置就是arr[0]应该插入的位置
    */
    	 private static int[] arr = new int[]{
        0,3, 5412, 12, 3, 513, -1, 6, -324};
        public static void insertSort(int[]arr){
        
            int i,j;
            for(i=2;i<arr.length;i++){
        
                if(arr[i-1]>arr[i]){
        //如果前面的数据更大说明当前需要排序
                    arr[0]=arr[i]; //i是更小的数据  哨兵节点
                    for(j=i-1;arr[j]>arr[0];j--){
        //找到小数据应该插入的位置
                        arr[j+1]=arr[j]; //arr[0]此时就是待插入的数据
                        //此时需要寻找arr[0]应该插入的位置 因此把更大的数据都后移给arr[0]腾位置
                    }//退出循环说明j对应的位置比待插入数据还小 此时数据应该插在这个位置之后一个位置
                    arr[j+1]=arr[0];
                    System.out.println("第"+(i-1)+"次数据位置为"+ Arrays.toString(arr));
                }
            }
        }
    
        public static void main(String[] args) {
        
            insertSort(arr);
        }

## 4:希尔排序 ##

/*
    希尔排序是插入排序的升级 其使用了一个增量
     * 由于增量的存在,每次的遍历都是直接跳跃式比对
     * 就能将比较后面的数据直接很快的弄到前面
     * 基本写法与插入排序无二 只是内层for循环判断的时候需要增加一个j>0&&arr[0]<arr[j]*/
    private int arr[];
        public void shellSort(int[]arr){
        
            int i,j;
            int increment=arr.length;//本质与直接插入排序无二 就是增加了一个增量进行跳跃式排序
            do{
        
                increment=increment/3+1;//加1是为了最后能使得增量取到1进行最后一次排序
                for(i=increment+1;i<=arr.length-1;i++){
        
                    if(arr[i]<arr[i-increment]){
        
                        arr[0]=arr[i];//小的数据设置为哨兵结点
                        for(j=i-increment;j>0&&arr[j]>arr[0];j-=increment){
        //为这个数据找到它应该插入的位置 以increment为间隔寻找插入位置
                            arr[j+increment]=arr[j];//将不合理数据后移increment
                        }//退出for循环时已经为这个小数据留好了可插入的位置
                        arr[j+increment]=arr[0];//需要加一个increment是因为最后退出之前-increment了
                        //导致j此时位置向前偏移了increment
                    }
                }
            }while(increment>1);//最后的停止条件就是执行increment=1时的排序 这次排序将会交换
            //相邻元素,也就是进行最后一次排序
        }
        public static void main(String[] args) {
        
            ShellSort sh = new ShellSort();
            sh.arr=new int[]{
        0,8,87,7,6,54,34,123};
            sh.shellSort(sh.arr);
            System.out.println(Arrays.toString(sh.arr));
        }

## 5:堆排序 ##

/*
     * 使用堆排序需要了解二叉树
     * 其实堆排序就是大顶堆或者小顶堆 每次都将
     * 最大或者最小的数据先移动到非叶子结点位置
     * 将结点与最后一个结点进行数据交换
     * 多次循环下来就可以得到一个有序的
     * 建议用草纸模拟一下堆排序的过程*/
     public static void main(String[] args) {
        
            int[] arr = {
        7, 8, 9, 10, 4, 7, 3, 4};
            heapSort(arr);
        }
    
        public static void heapSort(int[] arr) {
        
            //将无序序列构建成一个大顶堆或者小顶堆
            for (int i = arr.length / 2 - 1; i >= 0; i--) {
        
                adjustHeap(arr, i, arr.length);
            }
            System.out.println("初始构造大顶堆" + Arrays.toString(arr));
            //将对顶元素与末尾元素进行交换 将最大数据沉到末尾
            //重新调整结构 使其满足堆定义 然后继续交换当前与末尾元素
            for (int j = arr.length - 1; j > 0; j--) {
        
                arr[j] ^= arr[0]; //交换
                arr[0] ^= arr[j];
                arr[j] ^= arr[0];
                adjustHeap(arr, 0, j);
            }
            System.out.println(Arrays.toString(arr));
        }
    
        /**
         * @param arr    待调整数组
         * @param i      当前非叶子结点再数组中的索引
         * @param length 当前可操作数据的长度 对于大顶堆最大的数据再数组最后之后就会被抛弃不在操作
         *               因此length--
         */
        public static void adjustHeap(int[] arr, int i, int length) {
        
            int temp = arr[i]; //将当前非叶子结点保存
            for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
        //k=2*i+1则k代表的是当前非叶子结点的左孩子
                if (k + 1 < length && arr[k] < arr[k + 1]) {
        //判断左孩子大还是右孩子大
                    k++;//如果是右孩子大就++获得到右孩子的索引
                }
                if (arr[k] > temp) {
        //判断孩子大还是当前结点大
                    arr[i] = arr[k]; //将更大的向上排
                    i = k; //大的元素就跑到了非叶子结点的索引去 然后让i去更小数据的索引
                } else {
        
                    break;//由于i是从下往上的 所以如果当前的非叶子结点更大直接退出就好 因为假设是一个
                    //4层8结点的完全二叉树 那么i=3一开始 然后arr[7]<arr[3]那么直接break后
                    //下一次i=2(i=3那个结点的双亲结点) 然后i=1 i=0
                }
            }
            arr[i] = temp;//大的数据被移上去了 但是其原有位置的数据还没有被修改
        }   //因此这一步操作就是为了修改那个数据

## 6:计数排序 ##

计数排序是通过对所有的数据集进行大小上下限的划分的方式来对数据进行排序。  
其主要方式是得到数据集中的最大和最小值，然后创建一个max-min+1大小的数组，然后再一次遍历所有的数组元素，将对应的下标的元素计数+1，得到计数完毕之后的数组之后，我们再将这个计数的数组遍历一次，只要数组下标数据不为0，那么我们就一直复制这个值到最后的结果数组中，当计数数组中的所有下标对应元素都为0的时候，遍历完成，得到的数组有序。

/*
     * 计数排序是稳定的 ,这个大家应该能很明显的看出来,因为计数排序本身并不是基于比较的算法.
     * 计数排序需要的额外空间比较大,这个大家很明显的看出来,并且空间浪费的情况也会比较严重,
     * 因为一旦序列中MAX与MIN的差距过大,那么需要的内存空间就会非常大.并且假如序列中的元素
     * 都是散布在一个特定的区间内,那么内存空间浪费的情况也会非常明显.
    */
    public static void countSort(int[]arr){
        
            int max=Integer.MIN_VALUE;//数组中数据最大值
            int min=Integer.MAX_VALUE;//数组中数据最小值
    //        for(int i=0;i<arr.length;i++){//取得数组中的最大与最小值
    //            if(arr[i]<min){
        
    //                min=arr[i];
    //            }
    //            if(arr[i]>max){
        
    //                max=arr[i];
    //            }
    //        }//如果是一个整数数组,那么得知了这个数组中的最大与最小数据(通过散列)
            for (int i : arr) {
        
                min=Math.min(i,min);
                max=Math.max(i,max);
            }
            int index=0;
            int elementCount[]=new int[max-min+1];//我们就可以用他们的差来得到这个数组中最多有对少个数据
            for(int i=0;i<arr.length;i++){
        //假设最小数据是3 那么数组下标0->3 1->4以此类推
                elementCount[arr[i]-min]++;//对应的数组位置的数据量+1
            }
            for(int i=0;i< elementCount.length;i++){
        
                if (elementCount[i]!=0) {
        //如果当前数组位置有数据 那么就说明这个数字存在
                    for(int j=0;j<elementCount[i];j++){
        
                        arr[index++]=i+min;//那么就把这个数据覆盖到原数组中去
                    }
                }
            }
            System.out.println(Arrays.toString(arr));
        }
        public static void main(String[] args) {
        
            countSort(new int[]{
        0, -1, 9, 3, 2, 1, 8, 6, 5, 10});
        }

计数排序的代码比较简单，使用计数排序的场景比较少，一般用于数据量上下限较小的数据，下面是一道例题。  
[明明的随机数][Link 2]

import java.util.*;
    
    /**
     * @author: 张锦标
     * @date: 2023/7/6 19:53
     * RandomOfMingMing类
     * 删除重复并且排序
     * 这道题由于数据量较小
     * 所以可以直接使用计数排序
     */
    public class Main {
        
        public static void main(String[] args) {
        
             Scanner in = new Scanner(System.in);
            // 注意 hasNext 和 hasNextLine 的区别
            int n = in.nextInt();
            int[] arr = new int[1001];
            int count = 0;
            while (in.hasNextInt()) {
         // 注意 while 处理多个 case
                int i = in.nextInt();
                if (arr[i] != 1) {
        
                    count++;
                }
                arr[i] = 1;
            }
            System.out.println(count);
            for (int i = 1; i < arr.length; i++) {
        
                if (arr[i] == 1) {
        
                    System.out.print(i+" ");
                }
            }
        }
    }

## 7:基数排序 ##

/*
     * 基数排序是效率高的稳定性排序法
     * 基数排序是桶排序的升级 其实现思路如下:
     * 跳过构造每个位数可能出现的数字的十个二维数组桶0-9
     * 用这些桶构成存放数字的容器
     * 第一次将取得数字的个位,第二次十位,以此类推,每次获取都将
     * 直接覆盖桶中原有数据而不是直接擦除桶中数据(没有必要)
    */
      public static void radixSort(int[]arr){
        
            //1:得到数组中最大数据的位数
            int max=arr[0];//最大数据
            int maxLength=0;//最大数据长度
            for(int i=1;i<arr.length;i++){
        
                if(arr[i]>max){
        
                    max=arr[i];
                }
            }
            maxLength=(max+"").length();
            //2:创建桶和创建记录桶中数据的数组
            int[][]bucket=new int[10][arr.length];//存放数据的桶
            int[]bucketCount=new int[arr.length];//记录每个桶中数据的桶
            int digitOfElement=0;//当前位数对应的值0-9
            for(int i=0,n=1;i<maxLength;n*=10,i++){
        //需要 遍历最长的数字的长度
                for(int j=0;j<arr.length;j++){
        //对每一个数据进行遍历
                    digitOfElement=arr[j]/n%10;//取得这个数据当前的个位/十位/百位的值
                    bucket[digitOfElement][bucketCount[digitOfElement]]=arr[j];//将当前数据放入对应桶中
                    bucketCount[digitOfElement]++;//对应的桶中的数据量增加
                }
                int index=0;//用于对原数组进行覆盖
                for(int k=0;k<bucketCount.length;k++){
        //对十个桶进行遍历
                    if(bucketCount[k]!=0){
        //判断当前桶中是否有数据 当前数据值是新一轮存放进去的次数而不是原先没有被覆盖的数据个数
                        for(int l=0;l<bucketCount[k];l++){
        //有数据则将数组直接覆盖到原数组
                            arr[index++]=bucket[k][l];
                        }
                    }
                    bucketCount[k]=0;//不直接擦除桶中数据而是覆盖 因为没有必要
                }//因为每次从计数桶中取得的数据个数通过bucketCount来获得的 而每次取得完毕数据后
            }//都会将bucketCount变为0
            System.out.println("排序后:"+ Arrays.toString(arr));
        }
    
        public static void main(String[] args) {
        
            int[] arr = new int[]{
        3, 5412, 12, 3, 513, 0, 6, 324};
            radixSort(arr);
        }

## 8:快速排序 ##

/*
    * 快速排序 找到一个中轴 让中轴左边小于中轴 右边大于中轴
     * 然后把左边的再次按上面的方法进行
    */
     public static void quickSort(int[]arr,int left,int right){
        
            int l=left;//左下标
            int r=right;//右下标
            //pivot中轴值
            int pivot=arr[(left+right)/2];
            //while循环是为了让左边小于pivot 右边大于pivot
            while(l<r){
        //左下标还小于右下标
                while(arr[l]<pivot){
        //在pivot左边一直找 直到找到的数据大于pivot退出
                    l++;
                }//退出时arr[l]>=pivot
                while(arr[r]>pivot){
        //在pivot右边一直找 直到找到比pivot小的退出
                    r--;
                }//退出时arr[r]>pivot
                if(l>=r){
        
                    break;//如果按照上面的寻找方法使得l>=r说明左边的已经都小于pivot
                    //右边的都大于pivot了
                }
                //如果没有成立 那么就交换此时的左值和右值 因为他们不合理
                arr[l]^=arr[r];
                arr[r]^=arr[l];
                arr[l]^=arr[r];
                //交换后l指向arr[r] r指向arr[l]
                //如果交换后arr[l]==pivot 那么r--
                if(pivot==arr[l]){
        //arr[l]==pivot说明之前是r指向了pivot 那么之后r继续左移
                    r--;
                }
                if(pivot==arr[r]){
        //反之右移
                    l++;
                }
            }
            //如果l==r 必须l++和r-- 否则栈溢出
            if(l==r){
        
                l++;
                r--;
            }
            //向左递归
            if(left<r){
        
                quickSort(arr,left,r);
            }
            //向右递归
            if(right>l){
        
                quickSort(arr,l,right);
            }
        }
        public static void main(String[] args) {
        
            int[]arr={
        1,123,5,3425,2130,-4365,-123};
            quickSort(arr,0, arr.length-1);
            System.out.println(Arrays.toString(arr));
        }

## 9:归并排序 ##

/*
     * 归并排序的思路是分治,也就是将数组分为左右两个数组
     * 对左右两个数组递归排序
    */
     public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        
            if (left < right) {
        
                int mid = (left + right) / 2;
                mergeSort(arr, left, mid, temp);//对左半部分进行排序
                mergeSort(arr, mid + 1, right, temp);//对右半部分进行排序
                merge(arr, left, mid, right, temp);//对左右两个数组进行融合
            }
        }
    
        public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        
            int i = left;
            int j = mid + 1;
            int t = 0;
            //(一)
            //先把左右两边的有序数据按照规则填充到temp数组
            //直到左右两边有一边处理完毕
            while (i <= mid && j <= right) {
        
                if (arr[i] <= arr[j]) {
         //比较当前arr数组中的数据 小的先插入到temp中去
                    temp[t++] = arr[i++];
                } else {
        
                    temp[t++] = arr[j++];
                }
            }
            //(二)
            //进行到这里之后将剩下的元素直接赋值到temp中去
            while (i <= mid) {
        
                temp[t++] = arr[i++];
            }
            while (j <= right) {
        
                temp[t++] = arr[j++];
            }
            //(三)
            //重点部分 从left开始把到right的数据覆盖到原数组
            int tempLeft=left;
            t=0;
            while(tempLeft<=right){
        
                arr[tempLeft++]=temp[t++];
            }
        }
    
        public static void main(String[] args) {
        
            int[] arr = {
        1, 123, 53, 123, 65};
            int[] temp = new int[arr.length];
            mergeSort(arr, 0, arr.length - 1, temp);
            System.out.println(Arrays.toString(arr));
        }

## 10:桶排序 ##

//我们一般不使用桶排序而是使用桶排序的升级
        //例如基数排序和计数排序 因为桶排序需要再对每个桶中的数据进行一次排序
        //并且如果使用二维数组去做桶 那么由于我们不确定每个桶中的数据会有多少
        //会造成空间上的浪费 并且数组开辟的空间是确定的 那么就导致开辟数组时候默认
        //位置的元素是0 null 0.0 这些默认值 那么这些默认值也会参与排序
        //因此我们还需要对桶中每个数组中需要排序的元素进行计数
        //也就是还需要另一个计数桶中数据的桶
        //因此如果这样时间效率反而越来越低
        //除非直接使用ArrayList 但是arraylist再扩容的时候也是需要而外的时间的
        //因此综上 我们一般不使用桶排序
        //在链表中添加元素的同时需要进行元素的排序
        public static void sort(ArrayList<Integer> list, int i) {
        
            if (list == null)
                list.add(i);
                //这里采用的排序方式为插入排序
            else {
        
                int flag = list.size() - 1;
                while (flag >= 0 && list.get(flag) > i) {
        
                    if (flag + 1 >= list.size())
                        list.add(list.get(flag));
                    else
                        list.set(flag + 1, list.get(flag));
                    flag--;
                }
                if (flag != (list.size() - 1))
                    //注意这里是flag+1,自己可以尝试将这里换成flag看看,会出现数组越界的情况
                    list.set(flag + 1, i);
                else
                    list.add(i);
            }
        }
    
        public static void bucketSort(int[] num, int bucketNum) {
        
            //遍历得到数组中的最大值与最小值
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < num.length; i++) {
        
                min = min <= num[i] ? min : num[i];
                max = max >= num[i] ? max : num[i];
            }
            //求出每个桶的长度,这里必须使用Double
            double size = (double) (max - min + 1) / bucketNum;
            ArrayList<Integer>[] list = new ArrayList[bucketNum];
            for (int i = 0; i < bucketNum; i++) {
         //由于是对象数组 因此需要对数组每个索引先初始化
                list[i] = new ArrayList<Integer>();
            }
            //将每个元素放入对应的桶之中同时进行桶内元素的排序
            for (int i = 0; i < num.length; i++) {
        
                System.out.println("元素:" + String.format("%-2s", num[i]) + ", 被分配到" + (int) ((num[i] - min) / size) + "号桶");
    //            sort(list[(int) ((num[i] - min) / size)], num[i]);
                list[(int) ((num[i] - min) / size)].add(num[i]);
            }
            for(int i=0;i<list.length;i++){
        
                list[i].sort(Integer::compare);
            }
            System.out.println();
            for (int i = 0; i < bucketNum; i++) {
        
                System.out.println(String.format("%-1s", i) + "号桶内排序:" + list[i]);
            }
            System.out.println();
            //顺序遍历各个桶,得出我们 已经排序号的序列
            for (int i = 0; i < list.length; i++) {
        
                if (list[i] != null) {
        
                    for (int j = 0; j < list[i].size(); j++) {
        
                        System.out.print(list[i].get(j) + " ");
                    }
                }
            }
            System.out.println();
            System.out.println();
        }
    
    
        public static void main(String[] args) {
        
    
            int[] num = {
        7, 4, 9, 3, 2, 1, 8, 6, 5, 10};
            long startTime = System.currentTimeMillis();
            //这里桶的数量可以你自己定义,这里我就定义成了3
            bucketSort(num, 3);
            long endTime = System.currentTimeMillis();
            System.out.println("程序运行时间： " + (endTime - startTime) + "ms");
        }

[Link 1]: https://download.csdn.net/download/Zhangsama1/79464680
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAU2VyZW5kaXBpdHktLQ_size_20_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b85155b723ed406a841bd1b017cfded0.png
[Link 2]: https://ac.nowcoder.com/acm/problem/16669