前往小程序,Get更优阅读体验!
立即前往
发布
社区首页 >专栏 >【Java数据结构和算法】012-排序:快速排序*、归并排序*、基数排序(桶排序)、堆排序、排序算法比较

【Java数据结构和算法】012-排序:快速排序*、归并排序*、基数排序(桶排序)、堆排序、排序算法比较

作者头像
訾博ZiBo
发布2025-01-06 16:37:41
发布2025-01-06 16:37:41
680
举报
文章被收录于专栏:全栈开发工程师

一、快速排序

1、介绍

快速排序(Quicksort)是对冒泡排序的一种改进;

2、基本思想

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列;

3、思路图解

4、代码演示

代码实现[不易理解,看注释解释]:
代码语言:javascript
复制
package com.zb.ds.sort;

import java.util.Arrays;

//快速排序
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {-9,-8,-7,0,-3,2,-5,9};
        sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int[] arr,int left,int right){
        int l = left;//左下标
        int r = right;//右下标
        //pivot:中轴
        int pivot = arr[(l + r)/2];
        int temp;//临时变量,交换时使用
        //while循环的目的是让比pivot小的放到左边,大的放到右边
        while (l<r){
            //一个循环从左往右,另一个循环从右往左,都好像是在“清除异己”,小于pivot就是左阵营,大于pivot就是右阵营,等于的话都可以
            //左阵营每挑出来一个右阵营的就拿去和有阵营挑出来的交换,甚至其中一个阵营没有“异己”了,就拿pivot去交换
            //这个时候,右阵营发现左阵营拿pivot跟自己交换,很不开心,要求左阵营往后走一步,这件事情对于左阵营也是这样操作的
            //依此循环,目标是pivot左边全部是小于等于pivot的,右边全部是大于等于pivot的
            //我们再思考一下满足的条件:左阵营找找找,没找到“异己”,右阵营也找找找,一直找不到“异己”,
            //知道左右阵容头碰头了(l=r),或者都找到对方阵营了(l>r),这个时候才做罢休!
            //这个时候就可以了退出了,完成任务了,但是退出的条件是l>=r,很显然此时l不一定>=r,因为pivot这个值可能不是唯一的,意思是
            //在pivot左边一直找,找到一个大于等于pivot的值才退出
            //从左往右,找一个比pivot大的值
            while (arr[l]<pivot){
                l++;
            }
            //这个时候l最大的可能是比r小
            //这个时候找到的下标可能是pivot所在的下标,因为这个时候pivot前面的数全部比pivot小,
            //只有找到了他自己才符合跳出循环的条件,所以下标l对应的值应该就是pivot
            //在pivot右边一直找,找到一个小于等于pivot的值才退出
            //从右往左,找一个比pivot小的值
            while (arr[r]>pivot){
                r--;
            }
            //这个时候r最大的可能是比l大
            //这个时候找到的下标可能是pivot所在的下标,因为这个时候pivot后面的数全部比pivot大,
            //只有找到了他自己才符合跳出循环的条件,所以下标l对应的值应该就是pivot
            //如果l>=r,说明pivot的左边的值是小于等于pivot的值,右边全部是大于等于pivot的值
            //这个地方不好理解,首先要明白pivot是一个值,无关下标,pivot也只是一个普通的arr[l]或者arr[r],会随着规则移动位置
            //
            if(l>=r){
                break;
            }
            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //如果交换之后发现arr[l]=pivot,r--,前移
            if(arr[l]==pivot){
                r--;
            }
            //如果交换之后发现arr[r]=pivot,l++,后移
            if(arr[r]==pivot){
                l++;
            }
        }
        //在这之前,我们进行了一次阵营查找,下面再将左右阵营分别再划分左右阵营进行“排除异己”操作
        //如果l=r,那么这个下标的值就不进行操作了,因为它会始终位于两大阵营中间,也选出了一个数,所有的顺序产生机制就是通过这个方法得出“中间值”
        //如果l=r,必须l++,r--,否则会出现栈溢出
        if(l==r){
            l++;
            r--;
        }
        //递归实现阵营的划分
        //向左递归
        if(left<r){
            sort(arr,left,r);
        }
        //向右递归
        if(right>l){
            sort(arr,l,right);
        }
    }
}
运行结果:
代码语言:javascript
复制
[-9, -8, -7, -5, -3, 0, 2, 9]

5、速度测试

代码实现:
代码语言:javascript
复制
package com.zb.ds.sort;

import java.util.Random;

//快速排序
public class QuickSort {
    public static void main(String[] args) {
        int[] nums = new int[80000];
        for (int i = 0; i < 80000; i++) {
            nums[i] = new Random().nextInt(8000000);
        }
        //排序前时间
        long start = System.currentTimeMillis();
        System.out.println("排序前时间:" + start);
        sort(nums,0,79999);
        //排序后时间
        long end = System.currentTimeMillis();
        System.out.println("排序后时间:" + end);
        //程序执行时间
        System.out.println("程序执行时间为:" + (end-start)/1000 + "秒!");
    }
    public static void sort(int[] arr,int left,int right){
        int l = left;//左下标
        int r = right;//右下标
        //pivot:中轴
        int pivot = arr[(l + r)/2];
        int temp;//临时变量,交换时使用
        //while循环的目的是让比pivot小的放到左边,大的放到右边
        while (l<r){
            //一个循环从左往右,另一个循环从右往左,都好像是在“清除异己”,小于pivot就是左阵营,大于pivot就是右阵营,等于的话都可以
            //左阵营每挑出来一个右阵营的就拿去和有阵营挑出来的交换,甚至其中一个阵营没有“异己”了,就拿pivot去交换
            //这个时候,右阵营发现左阵营拿pivot跟自己交换,很不开心,要求左阵营往后走一步,这件事情对于左阵营也是这样操作的
            //依此循环,目标是pivot左边全部是小于等于pivot的,右边全部是大于等于pivot的
            //我们再思考一下满足的条件:左阵营找找找,没找到“异己”,右阵营也找找找,一直找不到“异己”,
            //知道左右阵容头碰头了(l=r),或者都找到对方阵营了(l>r),这个时候才做罢休!
            //这个时候就可以了退出了,完成任务了,但是退出的条件是l>=r,很显然此时l不一定>=r,因为pivot这个值可能不是唯一的,意思是
            //在pivot左边一直找,找到一个大于等于pivot的值才退出
            //从左往右,找一个比pivot大的值
            while (arr[l]<pivot){
                l++;
            }
            //这个时候l最大的可能是比r小
            //这个时候找到的下标可能是pivot所在的下标,因为这个时候pivot前面的数全部比pivot小,
            //只有找到了他自己才符合跳出循环的条件,所以下标l对应的值应该就是pivot
            //在pivot右边一直找,找到一个小于等于pivot的值才退出
            //从右往左,找一个比pivot小的值
            while (arr[r]>pivot){
                r--;
            }
            //这个时候r最大的可能是比l大
            //这个时候找到的下标可能是pivot所在的下标,因为这个时候pivot后面的数全部比pivot大,
            //只有找到了他自己才符合跳出循环的条件,所以下标l对应的值应该就是pivot
            //如果l>=r,说明pivot的左边的值是小于等于pivot的值,右边全部是大于等于pivot的值
            //这个地方不好理解,首先要明白pivot是一个值,无关下标,pivot也只是一个普通的arr[l]或者arr[r],会随着规则移动位置
            //
            if(l>=r){
                break;
            }
            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //如果交换之后发现arr[l]=pivot,r--,前移
            if(arr[l]==pivot){
                r--;
            }
            //如果交换之后发现arr[r]=pivot,l++,后移
            if(arr[r]==pivot){
                l++;
            }
        }
        //在这之前,我们进行了一次阵营查找,下面再将左右阵营分别再划分左右阵营进行“排除异己”操作
        //如果l=r,那么这个下标的值就不进行操作了,因为它会始终位于两大阵营中间,也选出了一个数,所有的顺序产生机制就是通过这个方法得出“中间值”
        //如果l=r,必须l++,r--,否则会出现栈溢出
        if(l==r){
            l++;
            r--;
        }
        //递归实现阵营的划分
        //向左递归
        if(left<r){
            sort(arr,left,r);
        }
        //向右递归
        if(right>l){
            sort(arr,l,right);
        }
    }
}
运行结果(8万数据,19毫秒):
代码语言:javascript
复制
排序前时间:1606362043150
排序后时间:1606362043169
程序执行时间为:0秒!

80万数据,162毫秒;

800万数据,1秒425毫秒;

二、归并排序

1、介绍

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之);

2、思路图解

说明: 可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程;

再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤:

3、代码演示

代码实现:
代码语言:javascript
复制
package com.zb.ds.sort;

import java.util.Arrays;

public class MergerSort {
    public static void main(String[] args) {
        int[] arr = {8,4,5,7,1,3,6,2};
        int[] temp = new int[arr.length];
        mergerSort(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergerSort(int[] arr,int left,int right,int[] temp){
        if(left<right){
            int mid = (left + right)/2;//中建索引
            //向左递归进行分解
            mergerSort(arr,left,mid,temp);
            //向右递归进行分解
            mergerSort(arr,mid+1,right,temp);
            //合并
            sort(arr,left,mid,right,temp);
        }
    }

    /**
     * 归并排序-合并
     * @param arr 待排序数组
     * @param left 左边有序序列的初始索引
     * @param mid 中间索引
     * @param right 右边索引
     * @param temp 做中转的数组
     */
    public static void sort(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;//初始化i,左边有序序列的初始索引
        int j = mid + 1;//初始化j,右边有序序列的初始索引
        int t = 0;//指向temp数组的当前索引
        //第一步:
        //先把左右两边(有序)的数据按照规则填充到temp数组
        //直到左右两边有一边处理完毕为止
        while (i<=mid && j<=right){
            //如果发现左边序列的”当前元素“小于等于右边数列的当前元素,就把该元素放到中转数组的“当前位置”
            //然后左边序列的”当前位置“和中转数组的”当前位置“后移一位
            if(arr[i]<=arr[j]){
                temp[t] = arr[i];
                t++;
                i++;
            }else {//反之将右边序列的“当前元素”放到中转数组的“当前位置”
                temp[t] = arr[j];
                t++;
                j++;
            }
        }
        //第二步:
        //将有剩余数据的一方,依次填充到temp数组
        while (i<=mid){
            temp[t] = arr[i];
            t++;
            i++;
        }
        while (j<=right){
            temp[t] = arr[j];
            t++;
            j++;
        }
        //第三步:
        //将temp数组的元素拷贝到arr
        //注意:并不是每次都拷贝所有
        t = 0;
        int tempLeft = left;
        //第一次合并时,tempLeft=0,right=1;//第二次:tL=2,r=3//第三次:tl=0.r=3//...
        //最后一次:tempLeft=0,right=7;
        while (tempLeft<=right){
            arr[tempLeft]  = temp[t];
            t++;
            tempLeft++;
        }
    }
}
运行结果:
代码语言:javascript
复制
[1, 2, 3, 4, 5, 6, 7, 8]

4、速度测试

代码实现:
代码语言:javascript
复制
package com.zb.ds.sort;

import java.util.Random;

public class MergerSort {
    public static void main(String[] args) {
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = new Random().nextInt(8000000);
        }
        int[] temp = new int[arr.length];
        //排序前时间
        long start = System.currentTimeMillis();
        System.out.println("排序前时间:" + start);
        mergerSort(arr,0,arr.length-1,temp);
        //排序后时间
        long end = System.currentTimeMillis();
        System.out.println("排序后时间:" + end);
        //程序执行时间
        System.out.println("程序执行时间为:" + (end-start)/1000 + "秒!");
    }

    public static void mergerSort(int[] arr,int left,int right,int[] temp){
        if(left<right){
            int mid = (left + right)/2;//中建索引
            //向左递归进行分解
            mergerSort(arr,left,mid,temp);
            //向右递归进行分解
            mergerSort(arr,mid+1,right,temp);
            //合并
            sort(arr,left,mid,right,temp);
        }
    }

    /**
     * 归并排序-合并
     * @param arr 待排序数组
     * @param left 左边有序序列的初始索引
     * @param mid 中间索引
     * @param right 右边索引
     * @param temp 做中转的数组
     */
    public static void sort(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;//初始化i,左边有序序列的初始索引
        int j = mid + 1;//初始化j,右边有序序列的初始索引
        int t = 0;//指向temp数组的当前索引
        //第一步:
        //先把左右两边(有序)的数据按照规则填充到temp数组
        //直到左右两边有一边处理完毕为止
        while (i<=mid && j<=right){
            //如果发现左边序列的”当前元素“小于等于右边数列的当前元素,就把该元素放到中转数组的“当前位置”
            //然后左边序列的”当前位置“和中转数组的”当前位置“后移一位
            if(arr[i]<=arr[j]){
                temp[t] = arr[i];
                t++;
                i++;
            }else {//反之将右边序列的“当前元素”放到中转数组的“当前位置”
                temp[t] = arr[j];
                t++;
                j++;
            }
        }
        //第二步:
        //将有剩余数据的一方,依次填充到temp数组
        while (i<=mid){
            temp[t] = arr[i];
            t++;
            i++;
        }
        while (j<=right){
            temp[t] = arr[j];
            t++;
            j++;
        }
        //第三步:
        //将temp数组的元素拷贝到arr
        //注意:并不是每次都拷贝所有
        t = 0;
        int tempLeft = left;
        //第一次合并时,tempLeft=0,right=1;//第二次:tL=2,r=3//第三次:tl=0.r=3//...
        //最后一次:tempLeft=0,right=7;
        while (tempLeft<=right){
            arr[tempLeft]  = temp[t];
            t++;
            tempLeft++;
        }
    }
}
运行结果(8万数据,15毫秒):
代码语言:javascript
复制
排序前时间:1606446334005
排序后时间:1606446334020
程序执行时间为:0秒!

三、基数排序(桶排序)

1、介绍

①基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用;

②基数排序法是属于稳定性的排序,基数排序法的是效率高的稳定性排序法;

③基数排序(Radix Sort)是桶排序的扩展;

④基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字,然后按每个位数分别比较;

2、基本思想

将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列;

3、思路图解

将数组 {53,3,542,748,14,214} 使用基数排序,进行升序排序:

第1轮排序[按照个位排序]:

说明:事先准备10个数组(10个桶), 0-9 分别对应 位数的 0-9;

(1) 将各个数,按照个位大小放入到对应的各个数组中;

(2)  然后从0-9个数组/桶,依次按照加入元素的先后顺序取出;

第1轮排序后:542 53 3 14 214 748

第2轮排序[按照十位排序]:

(1) 将各个数,按照十位大小放入到对应的各个数组中;

(2)  然后从0-9个数组/桶,依次按照加入元素的先后顺序取出;

第2轮排序后: 3 14 214 542 748 53

第3轮排序[按照百位排序]:

(1) 将各个数,按照百位大小放入到对应的各个数组中;

(2)  然后从0-9个数组/桶,依次按照加入元素的先后顺序取出;

第3轮排序后:3 14 53 214 542 748

4、代码演示

代码实现:
代码语言:javascript
复制
package com.zb.ds.sort;

import java.util.Arrays;

//基数排序(桶排序)
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int[] arr){
        //拿到数组中最大的数的位数
        int max = arr[0];
        for (int value : arr) {
            if (value > max) {
                max = value;
            }
        }
        //最大的数的位数
        int maxLength = (max + "").length();
        //准备一个二维数组,表示10个桶,每一个桶就是一个一维数组
        //为了防止数据溢出,每个一维数组的长度为arr.length
        //用空间换时间的算法
        int[][] bucket = new int[10][arr.length];
        //为了记录每个桶中,实际存放了多少个数据,我们定义一个一维数组进行记录
        int[] bucketElementCounts = new int[10];
        //开始排序
        for (int x=0,n=1; x<maxLength; x++,n*=10) {
            //1、第1轮排序[按照个位排序]
            for (int value : arr) {
                //取出每个元素个位数的值
                int digitOfElement = value / n % 10;
                //放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = value;
                bucketElementCounts[digitOfElement]++;//后移一位
            }
            //此时此刻,第一轮排序完毕,我们需要从0-9个数组/桶,依次按照加入元素的先后顺序取出
            int index = 0;
            //遍历每一个桶,并将所有数据放入原数组
            for (int i = 0; i < 10; i++) {
                //如果同种有数据,我们才放入原数组
                if(bucketElementCounts[i]!=0){
                    //有数据,遍历该桶
                    for (int j = 0; j < bucketElementCounts[i]; j++) {
                        arr[index] = bucket[i][j];
                        index++;
                    }
                    bucketElementCounts[i]=0;
                }
            }
        }
    }
}
运行结果:
代码语言:javascript
复制
[3, 14, 53, 214, 542, 748]

5、速度测试

代码实现:
代码语言:javascript
复制
package com.zb.ds.sort;

import java.util.Random;

//基数排序(桶排序)
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = new Random().nextInt(8000000);
        }
        //排序前时间
        long start = System.currentTimeMillis();
        System.out.println("排序前时间:" + start);
        sort(arr);
        //排序后时间
        long end = System.currentTimeMillis();
        System.out.println("排序后时间:" + end);
        //程序执行时间
        System.out.println("程序执行时间为:" + (end-start)/1000 + "秒!");
    }
    public static void sort(int[] arr){
        //拿到数组中最大的数的位数
        int max = arr[0];
        for (int value : arr) {
            if (value > max) {
                max = value;
            }
        }
        //最大的数的位数
        int maxLength = (max + "").length();
        //准备一个二维数组,表示10个桶,每一个桶就是一个一维数组
        //为了防止数据溢出,每个一维数组的长度为arr.length
        //用空间换时间的算法
        int[][] bucket = new int[10][arr.length];
        //为了记录每个桶中,实际存放了多少个数据,我们定义一个一维数组进行记录
        int[] bucketElementCounts = new int[10];
        //开始排序
        for (int x=0,n=1; x<maxLength; x++,n*=10) {
            //1、第1轮排序[按照个位排序]
            for (int value : arr) {
                //取出每个元素个位数的值
                int digitOfElement = value / n % 10;
                //放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = value;
                bucketElementCounts[digitOfElement]++;//后移一位
            }
            //此时此刻,第一轮排序完毕,我们需要从0-9个数组/桶,依次按照加入元素的先后顺序取出
            int index = 0;
            //遍历每一个桶,并将所有数据放入原数组
            for (int i = 0; i < 10; i++) {
                //如果同种有数据,我们才放入原数组
                if(bucketElementCounts[i]!=0){
                    //有数据,遍历该桶
                    for (int j = 0; j < bucketElementCounts[i]; j++) {
                        arr[index] = bucket[i][j];
                        index++;
                    }
                    bucketElementCounts[i]=0;
                }
            }
        }
    }
}
运行结果(8万数据,20毫秒):
代码语言:javascript
复制
排序前时间:1606529012580
排序后时间:1606529012600
程序执行时间为:0秒!

800万数据,632毫秒!

8000万数据,5857毫秒!

但是基数排序比较吃内存!

四、堆排序

(学完二叉树,再学堆排序,这里暂时省略,之后补上)

五、排序算法比较

1、图示

(里面的计数排序和桶排序与基数排序思路大体一致)

2、说明

①稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;

②不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;

③内排序:所有排序操作都在内存中完成;

④外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;

⑤时间复杂度: 一个算法执行所耗费的时间;

⑥空间复杂度:运行完一个程序所需内存的大小。 n: 数据规模 k: “桶”的个数 In-place:    不占用额外内存 Out-place: 占用额外内存;

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2025-01-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、快速排序
    • 1、介绍
      • 2、基本思想
        • 3、思路图解
          • 4、代码演示
            • 代码实现[不易理解,看注释解释]:
            • 运行结果:
          • 5、速度测试
            • 代码实现:
            • 运行结果(8万数据,19毫秒):
        • 二、归并排序
          • 1、介绍
            • 2、思路图解
              • 3、代码演示
                • 代码实现:
                • 运行结果:
              • 4、速度测试
                • 代码实现:
                • 运行结果(8万数据,15毫秒):
            • 三、基数排序(桶排序)
              • 1、介绍
                • 2、基本思想
                  • 3、思路图解
                    • 第1轮排序[按照个位排序]:
                    • 第2轮排序[按照十位排序]:
                    • 第3轮排序[按照百位排序]:
                  • 4、代码演示
                    • 代码实现:
                    • 运行结果:
                  • 5、速度测试
                    • 代码实现:
                    • 运行结果(8万数据,20毫秒):
                • 四、堆排序
                • 五、排序算法比较
                  • 1、图示
                    • 2、说明
                    领券
                    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档