【排序】java代码实现，万字详解常见的八大排序，直接插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序，计数排序

编程入门行业动态更新时间:2024-10-05 17:27:47

【排序】java代码实现，万字详解常见的八大排序，直接插入排序，<a href=https://www.elefans.com/category/jswz/34/1767881.html style= 希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序，计数排序"/>

【排序】java代码实现，万字详解常见的八大排序，直接插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序，计数排序

前言：
大家好，我是良辰丫，今天我们来学习一下排序，排序是重中之重，大家一定要重点掌握。排序是我们日常中常见的操作，每次考完试，会有成绩的排序；幼儿园的小盆友会按照个子高低进行排序…这些都是我们经常接触的，那么在我们代码中，又有哪些常见的排序呢？我们拭目以待。💞💞💞

🧑个人主页：良辰针不戳
📖所属专栏：java数据结构
🍎励志语句：生活也许会让我们遍体鳞伤，但最终这些伤口会成为我们一辈子的财富。
💦期待大家三连，关注，点赞，收藏。
💌作者能力有限，可能也会出错，欢迎大家指正。
💞愿与君为伴，共探Java汪洋大海。

1、关于排序
- 1.1 所谓排序
- 1.2 排序的稳定性
2、插入排序
- 2.1 直接插入排序
- - 2.1.1 简述直接插入排序
  - 2.1.2 代码分析
  - 2.1.3 直接插入排序特征
- 2.2 希尔排序
- - 2.2.1 简述希尔排序
  - 2.2.2 代码分析希尔排序
  - 2.2.3 希尔排序性能
3、选择排序
- 3.1 选择排序
- - 3.1.1 简述选择排序
  - 3.1.2 选择排序代码分析
  - 3.1.3 选择排序性能分析
- 3.2 堆排序
- - 3.2.1 简述堆排序堆
  - 3.2.2 代码分析堆排序
4、交换排序
- 4.1 快速排序
- - 4.1.1 简要分析快速排序
  - 4.1.2 代码分析快速排序
  - - 4.1.2.1 Hoare版
    - 4.1.2.2 挖坑法
    - 4.1.2.3 前后指针法
  - 4.1.3 快速排序性能分析
- 4.2 冒泡排序
- - 4.2.1 简要分析冒泡排序
  - 4.2.2 代码解析冒泡排序
  - 4.2.3 冒泡排序性能
5、归并排序
- 5.1 简述归并排序
- 5.2代码分析归并排序
- 5.3 归并排序性能分析
6、计数排序(了解即可)
7、排序总结

1、关于排序

在接触各个排序之前，我们需要了解一些排序的相关知识，这样可以帮我们更深刻的学习排序。

1.1 所谓排序

排序：

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
计数机中对于排序对于排序的理解，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。排序就是把集合中的元素按照一定的次序排序在一起。

1.2 排序的稳定性

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

举例子,下面例子进行升序排序。

5，8，2，6，1，5

稳定排序：1，2，5，5，6，8
不稳定排序：1，2，5，5，6，8

简要说明:
上述排序中,有两个相同的数字5,如果排序后,两个5的先后位置不变,我们就把这种定义为稳定排序;如果两个5在排序后先后位置改变,我们就把这样的排序定义为不稳定排序

除此之外,我们还需要简单的了解一下内部排序和外部排序的概念

内部排序：数据元素全部放在内存中的排序。(归并排序为内部排序)
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

2、插入排序

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。实际中我们玩扑克牌时，就用了插入排序的思想。

2.1 直接插入排序

2.1.1 简述直接插入排序

所谓直接插入排序，通俗理解就是，一个个的取数字然后进行排序，就如上图，一张一张取扑克牌，然后在整理牌的时候进行排序，大家可以看一下下面的动图。

看了上面的解释和动图，或许大家有点懵逼，没关系的，我们举个例子更加深刻的了解直接插入排序。

排序数列：1,3,5,2,4,6
第1趟:[1,3],5,2,4,6
第2趟:[1,3,5],2,4,6
第3趟:[1,2,3,5],4,6
第4趟:[1,2,3,4,5],6
第5趟:[1,2,3,4,5,6]

简要分析:

一个数据不需要进行排序,因此我们第一趟选择两个数据进行排序
插入一个数据进行一次排序

2.1.2 代码分析

//我们来简单分析一下代码
public static void insertSort(int[] array) {
//从第二个数据开始遍历,因为两个数据才能开始排序for (int i = 1; i < array.length; i++) {//tmp记录下标为i的数据int tmp = array[i];//定义一个j,从i的前一个进行遍历(从后往前遍历)int j = i-1;//为什么要这样做呢?大家可以想一想//当插入一个元素的时候,前面的数据一定是有序的,//那么现在就需要后移一些数据,找到插入元素应该放的位置//此时的我们已经用tmp保存了下标为i的位置//就不会存在所谓的数据丢失//这里的关键是大家写代码的时候不要迷失了自己//记住i下标记录要插入的元素,j下标是要做排序处理for (; j >= 0 ; j--) {//j下标大于要插入元素的时候,数据后移//tmp记录了要插入的元素if(array[j] > tmp) {array[j+1] = array[j];}else {//走到else语句说明已经找到插入元素的位置,不需要后移了//直接跳出循环即可//注意.此时跳出的是里面的循环,//一个break只能跳出一个循环//只插入了一个数据,排序还没完呢,哈哈break;}}//最后一定要记得在找到的位置把要插入的元素放进去array[j+1] = tmp;}}

简单说明:

看到这,有的小伙伴可能会说好复杂呀,明白了思路也不一定能写出来,你不去做怎么能知道自己做不到呢?不要眼高手低,脑子里想一个简单的排序例子,写代码的时候嵌套例子.
举个简单的例子,你刚上学的时候认识班里的同学嘛,经过时间的洗礼,岁月的陪伴,慢慢不就熟悉了嘛?
只要去做,大家一般都能做好,加油.

2.1.3 直接插入排序特征

元素集合越接近有序，直接插入排序算法的时间效率越高
时间复杂度：O(N^2)
空间复杂度：O(1)，它是一种稳定的排序算法
稳定性：稳定

2.2 希尔排序

2.2.1 简述希尔排序

其实呢,希尔排序是直接插入排序的升级版本,它的效率普遍快了一些,就像iPhone14和iPhone14plus,后者是前者的升级版,既然是升级版,肯定有相似的地方,直接插入排序是一个一个挨着进行插入,希尔排序是跳着进行插入,那么到底是怎么一回事呢?我们来具体看一下

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组，
所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

其实gap应该取几,间隔几个数据进行排序最好呢?很多专家都有不同的见解,到目前为止也没有一个统一的规则,但是呢,希尔排序还是比较重要的,我们需要去掌握,接下来我们举个例子,简单过一遍希尔排序的过程.

排序数据:9,1,2,5,7,4,8,6,3,5
总共十个数据,我们选择gap为5,下图可以直观的看到希尔排序的排序过程,如果大家还是没有理解,也没有关系,那么我们从代码的角度进行分析.

2.2.2 代码分析希尔排序

看到这里,或许大家还是对gap的含义有点不理解,没关系,在这里我们解释一下,gap表示增量,在直接插入排序里面,gap等于1,也就是所有的数据为一组,直接排序即可;在希尔排序中,增量可以由自己定,也就是分为几组进行排序,但是最后一次,一定是增量变为1,因为这样才能让数据真正有序

public static void shellSort(int[] array) {
//在这里我们先指定增量int gap = array.length;while (gap > 1) {//分组进行希尔排序shell(array,gap);//增量缩小gap /= 2;}//最后一定要整体为一组进行插入排序shell(array,1);}//其实shell和直接插入排序那个方法大同小异//在这里我就不做详细说明了public static void shell(int[] array,int gap) {for (int i = gap; i < array.length; i++) {int tmp = array[i];int j = i-gap;for (; j >= 0 ; j-=gap) {if(array[j] > tmp) {array[j+gap] = array[j];}else {break;}}array[j+gap] = tmp;}}

2.2.3 希尔排序性能

希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定

3、选择排序

3.1 选择排序

3.1.1 简述选择排序

所谓选择排序,每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

看不懂没关系,例子能让大家更清楚的理解选择排序.
排序数据:1,3,5,2,4,6
第1趟:[1]3,5,2,4,6
第2趟:[1,2]3,5,4,6
第3趟:[1,2,3]5,4,6
第4趟:[1,2,3,4]5,6
第5趟:[1,2,3,4,5]6
第6趟:[1,2,3,4,5,6]

看了上面的例子,大家明白选择排序了嘛,每次总会选择最大(最小)的数据,然后呢,我们就去分析一下代码.

3.1.2 选择排序代码分析

public static void selectSort(int[] array) {
//循环遍历数组,用minIndex记录最小元素的下标for (int i = 0; i < array.length; i++) {int minIndex = i;int j = i+1;//遍历一次后找到最小元素的下标for (; j < array.length; j++) {if(array[j] < array[minIndex]) {minIndex = j;}}//最小元素的下标元素与i下标元素进行交换swap(array,i,minIndex);}}private static void swap(int[] array,int i,int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}

选择排序其实是相对比较简单的,你就想象有五张牌,你每次选择最小的,选择五次后顺序自然排好了.

3.1.3 选择排序性能分析

选择排序思考非常好理解，但是效率不是很好。实际中很少使用
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定

3.2 堆排序

3.2.1 简述堆排序堆

前面咱们讲了堆,了解了堆模型以及堆的基本概念,堆排序也是作为重要的排序,咱们有必要去学习.堆排序是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

上图描述了一趟堆排序,为了真正的理解升序要建立大根堆,我们首先要明白其中的原理.

为什么升序要建立大根堆?

首先大家需要明白,堆的底层原理是数组,升序排序后最后一个元素一定是最大的,那么我们就需要理解堆排序是如何进行的(升序排序举例).

建立大根堆
第一个元素与最后一个元素交换,此时最后一个元素已经是最大的元素了,此时我们有一个标记为,最后一个元素进行标记,这个元素将不再进行调整处理.
除了标记后的元素,其余元素向下调整,再次调整为大根堆.

有些细节大家可能听不懂,没关系,我们接下来分析代码.

3.2.2 代码分析堆排序

public static void heapSort(int[] array) {
//升序首先要创建大根堆createBigHeap(array);//end进行标记,只有end之前的元素进行向下调整int end = array.length-1;while (end > 0) {//第一个元素与未被标记的最后一个元素进行交换swap(array,0,end);//交换后进行向下调整shiftDown(array,0,end);//需要调整的元素--end--;}}
//下面的创建堆以及向下调整在堆的文章中已经详细讲解
//此处我们就不做解释,不理解的大家可以看之前的文章private static void createBigHeap(int[] array) {for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {shiftDown(array,parent,array.length);}}private static void shiftDown(int[] array,int parent,int len) {int child = 2*parent+1;while (child < len) {if(child+1 < len && array[child] < array[child+1]) {child++;}if(array[child] > array[parent]) {swap(array,child,parent);parent = child;child = 2*parent+1;}else {break;}}}

4、交换排序

4.1 快速排序

4.1.1 简要分析快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

待排序数据:6,1,2,7,9,3,4,5,10,8

1. hoare版本

随便选取一个数字作为基准值,我们就以第一个为基准值(咱们就以最左边的数为基准.咱们分析一趟.

right向左移动,寻找比基准小的数字,left向右移动,寻找比基准大的数字.

left和right指针找到相关数据后进行交换

right再次向左移动,left再次向右移动,找到相关数据

left与right进行交换数据

当left与right相遇的时候,最左边的数据(基准所在位置的数据)与下标为left(或者right)的数据进行交换

这样一趟hoare法就完成了,大家需要理解这个过程.

2. 挖坑法

选择一个基准进行挖坑,需要掌握思想,注意区分hoare与挖坑法的区别.在这里我们还是选择最左边的作为基准进行挖坑.

下面就是进行挖坑的数据.

right左移找到比基准小的数字.

此时left下标的数据填充right的数据,这个时候right的位置就变成了坑.

left向右移动,直到找到比基准大的数据.

left的数据填充到right的位置上,此时left又成为了坑.

right左移,找到比基准小的数字

right的数据填充到left位置上,此时right又成为了坑.

下面操作和上面一样,依次移动,填坑.

left与right相遇后,基准数据进行填坑.

4.1.2 代码分析快速排序

1. 基础代码:递归实现快排

public static void quickSort(int[] array) {
//数组,首尾下标传过去进行快排quick(array,0,array.length-1);}private static void quick(int[] array,int start,int end) {//为什么取大于号  ： 1 2 3 4 5 6//可能第一个数字最小,且此时已经是有序状态,right会走到-1的位置if(start >= end) {return;}//使用这个优化 主要解决 减少递归的次数//15是随便定的数,符合这种情况使用插入排序更合适if(end - start + 1 <= 15) {//插入排序insertSort(array,start,end);return;}//System.out.println("start:"+start+"  end: "+end);//三数取中法(进行优化快排)int index = midThree(array, start,end);//index找到三数中第二大的数与首元素进行交换swap(array,index,start);//此时的首元素便作为基准进行划分int pivot = partition(array,start,end);//划分//左边递归quick(array,start,pivot-1);//右边递归quick(array,pivot+1,end);}//三数取中法主要是找三个数第二大的数private static int midThree(int[] array,int left,int right) {int mid = (left+right) / 2;if(array[left] < array[right]) {if(array[mid] < array[left]) {return left;}else if(array[mid] > array[right]) {return right;}else {return mid;}}else {//array[left] > array[right]if(array[mid] < array[right]) {return right;}else if(array[mid] > array[left]) {return left;}else {return mid;}}}

2. 基础代码:非递归实现快排

//利用栈进行实现
public static void quickSort(int[] array) {Deque<Integer> stack = new LinkedList<>();//左指针指向第一个元素int left = 0;//右指针指向最后一个元素int right = array.length-1;//找基准(hoare法和挖坑法都行)int pivot = partition(array,left,right);if(pivot > left+1) {stack.push(left);stack.push(pivot-1);}if(pivot < right-1) {stack.push(pivot+1);stack.push(right);}while (!stack.isEmpty()) {right= stack.pop();left = stack.pop();pivot = partition(array,left,right);if(pivot > left+1) {stack.push(left);stack.push(pivot-1);}if(pivot < right-1) {stack.push(pivot+1);stack.push(right);}}}

4.1.2.1 Hoare版

    private static int partition(int[] array, int left, int right) {int i = left;int j = right;int pivot = array[left];while (i < j) {while (i < j && array[j] >= pivot) {j--;}while (i < j && array[i] <= pivot) {i++;}swap(array, i, j);}swap(array, i, left);return i;}

4.1.2.2 挖坑法

    private static int partition(int[] array, int left, int right) {int i = left;int j = right;int pivot = array[left];while (i < j) {while (i < j && array[j] >= pivot) {j--;}array[i] = array[j];while (i < j && array[i] <= pivot) {i++;}array[j] = array[i];}array[i] = pivot;return i;}

那么为什么把左边的数值作为基准,right先移动呢?

我们以hoare法为例子
待排序数据:6,1,2,7,9,3,4,5,10,8
下面是left先移动的过程

left和right相遇的时候,此时指向一个大于基准的数据

如果此时基准位置的数据与基准位置的数据交换,惊奇的发现,大数跑到了左边,很难进行排序了.

4.1.2.3 前后指针法

//前后指针法 【了解即可】private static int partition(int[] array,int left,int right) {int prev = left ;int cur = left+1;while (cur <= right) {if(array[cur] < array[left] && array[++prev] != array[cur]) {swap(array,cur,prev);}cur++;}swap(array,prev,left);return prev;}

4.1.3 快速排序性能分析

快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
时间复杂度：O(N*logN)
空间复杂度：O(logN)
稳定性：不稳定

4.2 冒泡排序

4.2.1 简要分析冒泡排序

冒泡排序是咱们最常见的编程语言,刚开始学习编程时,我们接触的排序就是冒泡排序(升序举例),一趟又一趟,相邻的元素进行比较交换,每一趟都会把最大的元素呈现出来.

待排序元素:5,4,3,2
第一趟:4,3,2,5
第二趟:3,2,4,5
第三趟:2,3,4,5

一般而言,4个数据需要进行3趟,那么n个数据需要进行n-1趟

4.2.2 代码解析冒泡排序

 public static void bubbleSort(int[] array) {for (int i = 0; i < array.length-1; i++) {//这个代码是对冒泡排序的优化//设计一个标志flg,初始值为falseboolean flg = false;//为什么j < array.length-1-i//for (int j = 0; j < array.length-1-i; j++) {//相邻的两个数前面比后面大,就进行交换if(array[j] > array[j+1]) {swap(array,j,j+1);//flg变为true,说明这一趟进行交换操作,可能还未排好序flg = true;}}//执行下面的if语句的时候,说明其中有一趟代码没有进行交换//此时说明排序已经完成了,接下来的趟数没有必要//于是乎,结束循环就可以了if(flg == false) {return;}}}

4.2.3 冒泡排序性能

冒泡排序是一种非常容易理解的排序
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定

5、归并排序

5.1 简述归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并.

待排序数据:10,6,7,1,3,9,4,2

第一次分解:[10,6,7,1],[3,9,4,2]
第二次分解:[10,6],[7,1],[3,9],[4,2]
第三次分解:10,6,7,1,3,9,4,2
第一次合并:[6,10],[1,7],[3,9],[2,4]
第二次合并:[1,6,7,10],[2,3,4,9]
第三次合并1,2,3,4,6,7,9,10

注意:
归并是在合并的过程中进行排序合并

5.2代码分析归并排序

第一种归并排序代码(递归)

public static void mergeSort1(int[] array) {mergeSortFunc(array,0,array.length-1);}private static void mergeSortFunc(int[] array,int left,int right) {if(left >= right) {return;}int mid = (left+right) / 2;mergeSortFunc(array,left,mid);mergeSortFunc(array,mid+1,right);merge(array,left,right,mid);}private static void merge(int[] array,int start,int end,int mid) {int s1 = start;//int e1 = mid;int s2 = mid+1;//int e2 = end;int[] tmp = new int[end-start+1];int k = 0;//tmp数组的下标while (s1 <= mid && s2 <= end) {if(array[s1] <= array[s2]) {tmp[k++] = array[s1++];}else {tmp[k++] = array[s2++];}}while (s1 <= mid) {tmp[k++] = array[s1++];}while (s2 <= end) {tmp[k++] = array[s2++];}for (int i = 0; i < tmp.length; i++) {array[i+start] = tmp[i];}}

第二种归并排序代码(非递归)

public static void mergeSort(int[] array) {int gap = 1;while (gap < array.length) {// i += gap * 2 当前gap组的时候，去排序下一组for (int i = 0; i < array.length; i += gap * 2) {int left = i;int mid = left+gap-1;//有可能会越界if(mid >= array.length) {mid = array.length-1;}int right = mid+gap;//有可能会越界if(right>= array.length) {right = array.length-1;}merge(array,left,right,mid);}//当前为2组有序  下次变成4组有序gap *= 2;}}private static void merge(int[] array,int start,int end,int mid) {int s1 = start;//int e1 = mid;int s2 = mid+1;//int e2 = end;int[] tmp = new int[end-start+1];int k = 0;//tmp数组的下标while (s1 <= mid && s2 <= end) {if(array[s1] <= array[s2]) {tmp[k++] = array[s1++];}else {tmp[k++] = array[s2++];}}while (s1 <= mid) {tmp[k++] = array[s1++];}while (s2 <= end) {tmp[k++] = array[s2++];}for (int i = 0; i < tmp.length; i++) {array[i+start] = tmp[i];}}

5.3 归并排序性能分析

归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定

6、计数排序(了解即可)

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。操作步骤：

统计相同元素出现次数
根据统计的结果将序列回收到原来的序列中

 public static void countSort(int[] array) {//1. 遍历数组 找到最大值 和 最小值int max = array[0];int min = array[0];//O(N)for (int i = 1; i < array.length; i++) {if(array[i] < min) {min = array[i];}if(array[i] > max) {max = array[i];}}//2. 根据范围 定义计数数组的长度int len = max - min + 1;int[] count = new int[len];//3.遍历数组，在计数数组当中 记录每个数字出现的次数 O(N)for (int i = 0; i < array.length; i++) {count[array[i]-min]++;}//4.遍历计数数组int index = 0;// array数组的新的下标 O(范围)for (int i = 0; i < count.length; i++) {while (count[i] > 0) {//这里要加最小值  反应真实的数据array[index] = i+min;index++;count[i]--;}}}

7、排序总结

排序方法	最好	平均	最坏	空间复杂度	稳定性
冒泡排序	O(n)	O(n^2 )	O(n^2)	O(1)	稳定
插入排序	O(n)	O(n^2 )	O(n^2)	O(1)	稳定
选择排序	O(n^2)	O(n^2 )	O(n^2)	O(1)	不稳定
希尔排序	O(n)	O(n^1.3 )	O(n^2)	O(1)	不稳定
堆排序	O(n*log(n))	O(n*log(n))	O(n*log(n))	O(1)	不稳定
快速排序	O(n*log(n))	O(n*log(n))	O(n^2)	O(log(n))-O(n)	不稳定
归并排序	O(n*log(n))	O(n*log(n))	O(n*log(n))	O(n)	稳定