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

訾博ZiBo

发布于 2025-01-06 16:37:41

11900

代码可运行

文章被收录于专栏：全栈开发工程师全栈开发工程师

运行总次数：0

代码可运行

一、快速排序

1、介绍

快速排序（Quicksort）是对冒泡排序的一种改进；

2、基本思想

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

3、思路图解

4、代码演示

代码实现[不易理解，看注释解释]：

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

运行结果：

[-9, -8, -7, -5, -3, 0, 2, 9]

5、速度测试

代码实现：

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毫秒）：

排序前时间：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、代码演示

代码实现：

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

运行结果：

[1, 2, 3, 4, 5, 6, 7, 8]

4、速度测试

代码实现：

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毫秒）：

排序前时间：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、代码演示

代码实现：

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

运行结果：

[3, 14, 53, 214, 542, 748]

5、速度测试

代码实现：

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毫秒）：

排序前时间：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 条评论

热度