【Java数据结构和算法】012-排序：快速排序*、归并排序*、基数排序(桶排序)、堆排序、排序算法比较
訾博ZiBo
发布于 2025-01-06 08:37:41
发布于 2025-01-06 08:37:41
代码可运行
运行总次数：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 删除
评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
推荐阅读
相关推荐
[数据结构与算法] 排序算法之归并排序与基数排序
更多 >目录
交个朋友
加入腾讯云官网粉丝站
蹲全网底价单品 享第一手活动信息
腾讯云开发者
