写在前面的话

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

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

十大排序算法对比

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

冒泡排序

本文的图片来源网络，仅用于大家学习，侵权联系删除！（下同）

完整代码：

package com.keafmd.Sequence;

public class BubbleSort {

//冒泡排序

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

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

for (int i = 1; i

flag = false; //假定未交换

for (int j = 0; j

if (ascending ? arr[j] > arr[j + 1] : arr[j]

int temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

flag = true;

}

//冒泡排序 -- 默认不传参升序

public static void bubbleSort(int[] arr) {

bubbleSort(arr, true);

}

测试代码：

升序排序（从小到大）

运行结果：

降序排序（从大到小）

运行结果：

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

快速排序

简单解释：

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

完整代码：

package com.keafmd.Sequence;

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

while (arr[j] >= base && i

j--;

}

while (arr[i]

i++;

}

if (i

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

while (arr[j]

j--;

}

while (arr[i] >= base && i

i++;

}

if (i

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); //递归调用右半数组

}

直接选择排序

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

完整代码：

package com.keafmd.Sequence;

public class SelectSort {

//直接选择排序

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

for (int i = 0; i

int m = i; //最小值或最小值的下标

for (int j = i + 1; j

if (ascending ? 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);

}

堆排序

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

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

完整代码：

package com.keafmd.Sequence;

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); //重新对堆进行调整

}

//建立堆的方法

private static void sift(int[] arr, int parent, int len, boolean maxheap) {

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

for (int child = 2 * parent + 1; child

if (child+1 arr[child + 1])) { //如果左子结点小于右子结点，child指向右子结点

child++; //右孩子如果比左孩子大，我们就将现在的孩子换到右孩子

}

//判断是否符合大顶堆的特性，如果右孩子大于双亲，自然左孩子也大于双亲，符合

//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换)

if (maxheap ? value arr[child]) {

arr[parent]=arr[child];

parent = child;

}

else {//如果不是，说明已经符合我们的要求了。

break;

}

arr[parent] =value; //将value值放到最终的位置

}

归并排序

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

完整代码：

package com.keafmd.Sequence;

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

}

public static void mergeSort(int []arr,int left,int right,int[] temp,boolean ascending){

if(left

//对半分，比如总长度是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

if(ascending?arr[i]arr[j]){ //比较两个序列第一个元素谁小，谁小先拷贝谁到temp，然后对应子序列下标加1

temp[t++] = arr[i++];

}else {

temp[t++] = arr[j++];

}

while(i

temp[t++] = arr[i++];

}

while(j

temp[t++] = arr[j++];

}

t = 0;

//将temp中的元素全部拷贝到原数组中

while(left

arr[left++] = temp[t++];

}

插入排序

简单解释：

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

完整代码：

package com.keafmd.Sequence;

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

int temp = arr[i];

int j=0; //这就是那个合适的位置

for (j = i - 1; j >= 0 && (ascending ? temp arr[j]); j--) {

arr[j + 1] = arr[j];

}

//把牌放下，为啥是j+1，

//是因为上面的循环遍历到不符合情况的时候 j是合适的位置的前面的那个数的位置

//有点拗口，但是就是这个意思，看图方便理解下

arr[j + 1] = temp;

}

希尔排序

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

完整代码：

package com.keafmd.Sequence;

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

int temp = arr[i];

int j=0;

for(j=i-d;j>=0&&(ascending?temparr[j]);j-=d){

arr[j+d]=arr[j];

}

arr[j+d] = temp;

}

计数排序

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

完整代码：

package com.keafmd.Sequence;

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

if(arr[i]

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

count_map[arr[i]-d]++;

}

int k =0;

if(ascending){

for(int i=0;i

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

}

桶排序

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

完整代码：

package com.keafmd.Sequence;

import java.util.ArrayList;

import java.util.Collections;

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

max = Math.max(arr[i],max);

min = Math.min(arr[i],min);

}

//计算桶的数量

int bucketNUm = (max-min)/ arr.length+1;

ArrayList> bucketArr = new ArrayList(bucketNUm);

for(int i=0;i

bucketArr.add(new ArrayList());

}

//将每个元素放入桶中

for(int i=0;i

int num = (arr[i]-min)/ (arr.length);

bucketArr.get(num).add(arr[i]);

}

//对每个桶进行排序

for (int i = 0; i

//用系统的排序，速度肯定没话说

Collections.sort(bucketArr.get(i));

}

//将桶中元素赋值到原序列

int index;

if(ascending){

index=0;

}else{

index=arr.length-1;

}

for(int i=0;i

for(int j= 0;j

arr[index] = bucketArr.get(i).get(j);

if(ascending){

index++;

}else{

index--;

}

基数排序

简单解释：

首先说一下，我发现好多人写的基数排序只能排序正整数，其实只要处理下就可以排序含有负数的了，就是我们排序前先把所有的数整体变大（就是减上最小的负数，也就是加了），都变成正数，然后排序好之后，在减下来（加上最小的负数，也就减了）就好了。

基数排序就是按数位排序可分为LSD（从最低位[也就是个位]开始排序）和MSD（从最高位开始排序），下面写的事LSD基数排序。

基数排序就是把数按位考虑，让后我们一位数只能是[0，9]，就是我们在考虑某位（个位、百位· · ·）的时候就只看这个位的数，放到在[0，9]相应的位置，然后顺序取出，最后再按其它位这样操作（上面说了要不从低位开始到高位，要不就是从高位到低位）

完整代码：

package com.keafmd.Sequence;

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

max = Math.max(max, arr[i]);

min = Math.min(min, arr[i]);

}

if (min

for (int i = 0; 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

for (int j = 0; 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

if (bucketElementCount[j] != 0) {

for (int k = 0; 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

arr[index] = bucket[j][k];

index++;

}

bucketElementCount[j] = 0;

}

if (min

for (int i = 0; i

arr[i] += min;

}

完整测试类

package com.keafmd.Sequence;

import java.util.*;

import java.util.stream.IntStream;

import java.util.stream.Stream;

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 integerStream = stream.boxed();

//3、将流转换为数组

Integer[] integers = integerStream.toArray(Integer[]::new);

//把数组转为List

List tempList = new ArrayList(Arrays.asList(integers));

//使用Collections.sort()排序

System.out.println("使用系统的Collections.sort()的对比:");

//Collections.sort

Collections.sort(tempList, new Comparator() {

@Override

public int compare(Integer o1, Integer o2) {

return o1-o2;

//return o2-o1;

}

});

//tempList.sort 也可以排序

//遍历输出结果

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

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

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

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

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

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

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

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

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

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

System.out.print(temparr[i] + " ");

}

System.out.println();

}

————————————————

原文链接：https://blog.csdn.net/weixin_43883917/article/details/118193663?spm=1001.2014.3001.5501

ITPub博客

经典十大排序算法（含升序降序，基数排序含负数排序）

十大排序算法对比

冒泡排序

直接选择排序

堆排序

归并排序

希尔排序

计数排序

桶排序

最新文章