【数据结构】七种常见排序算法

🥰🥰🥰来都来了，不妨点个关注叭！
👉博客主页：欢迎各位大佬!👈

欢迎来到排序算法的学习，恭喜你！本期内容主要介绍排序算法，一起来探索吧~
（ps：真的一直都想写有关排序的文章，奈何每天尊嘟好忙，终于开写啦！）

1. 排序的基本概念

1.1 排序预备知识

排序：排序的目的是使一串记录，将一组“无序”的记录序列调整为"有序"的记录序列，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

1.2 内部排序与外部排序

内部排序：数据元素全部放在内存中的排序，内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
外部排序：数据元素数量非常大，不能同时放在内存中，整个过程不可能在内存中完成。

1.3 排序的稳定性

稳定性：假定在待排序的记录序列中，存在两个或者两个以上的具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，则称为稳定，否则为不稳定

1.4 排序的分类

插入类排序：将待排序的值插入到前面已经有序的序列中
选择类排序：每次排序选出序列的最大值/最小值，放到序列的最后面
交换排序：两两比较待排序的序列，并交换不满足序列的那对数

以上为经典排序，本文主要介绍常见的 7 种排序算法，我们需要掌握~ 一起来正式进入下面的学习吧！

2. 插入类排序

2.1 直接插入排序

【基本思想】 将记录的值，插入到已经排序好的有序序列中，直到所有记录的值全部插入，则该过程完成。

【基本思路】 仅有一个数据时，则认为该数据为已经排好序的，则我们可以这样思考：

1. 第1个元素已排好序，从第2个元素开始，下标为i，取出该元素放在变量 tmp 中，从已排好序序列中从后往前使用 j 遍历比较
2. 如果下标 j 的值大于 tmp，则 j+1 的值替换为 j 下标的值，继续遍历
3. 如果下标 j 的值小于 tmp，则 break，跳出遍历
4. 最后 j+1 的值替换成临时变量 tmp 存储的值
5. 此时前两个元素已经是有序的了，再用 i 继续遍历(详细解释可以看示意图~)

有没有点像打扑克牌时候呢？拿到一张牌就在以往排好序的牌中插入~

【示意图】

【具体代码】

/*** Created with IntelliJ IDEA.* Description:* User: wlx* Date: 2025-06-01* Time: 23:58*/
public class InsertSort {public static void main(String[] args) {int[] array = {1,4,2,9,6,7};insertSort(array);System.out.println(Arrays.toString(array));}public static void insertSort(int[] array) {for(int i = 1; i < array.length; i++) {int tmp = array[i];int j = i-1;for(; j >= 0; j--) {if(array[j] > tmp) {array[j+1] = array[j];}else {//array[j+1] = tmp;break;}}array[j+1] = tmp;}}
}

【特性总结】

1. 时间复杂度：O(n²)，当数据本身就有序的时候，时间复杂度为O(n)
2. 空间复杂度：O(1)
3. 稳定性：稳定
4. 适用场景：当数据基本趋于有序时，建议使用直接插入排序

2.2 希尔排序

【基本思想】希尔排序又称为缩小增量法，其基本思想是先选定一个整数 gap，将待排序的数据分为多个组，每组距离 gap，对每一组进行排序，每一组两个元素，接着 gap/2 ，缩小每组的距离，当 gap = 1 时，所有数据就排好序了
简单理解就是按照 gap 分组，组内进行插入排序，当 gap = 1 时，则为直接插入排序

【基本思路】与直接插入排序思路一致，希尔排序是直接插入排序的优化，先用 gap 分组，让数组预有序，当 gap 为 1 时，数组也基本有序了，此时就是直接插入排序~

【示意图】

【具体代码】

/*** Created with IntelliJ IDEA.* Description:* User: wlx* Date: 2025-06-02* Time: 10:28*/
public class ShellSort {public static void main(String[] args) {int[] array = {1,4,2,9,6,7};int gap = array.length;while(gap > 1) {shellSort(array,gap);gap /= 2;}shellSort(array,1);System.out.println(Arrays.toString(array));}public static void shellSort(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 {//array[j+1] = tmp;break;}}array[j+gap] = tmp;}}

【特性总结】

1. 时间复杂度：O(n^1.3) - O(n^1.5) ，当数据本身就有序的时候，时间复杂度为O(n)，且希尔排序的时间复杂度取决于增量值 gap 的选取，即时间复杂度并不是一个定值
2. 空间复杂度：O(1)
3. 稳定性：不稳定
4. 希尔排序是直接插入排序的优化，gap >1 的排序是预排序，使数据趋于有序，gap=1 时则是直接插入排序

3. 选择类排序

3.1 直接选择排序

【基本思想】每次从待排序的序列中选出最小/最大元素，放在序列的起始位置，直到全部待排序的数据排完

【基本思路】定义一个 minIndex 下标用来存储最小值的下标，第1次 minIndex = 0 下标，遍历整个待排序序列，当有更小数据时，更新 minIndex 下标，再交换起始位置 i 与 minIndex 下标值，这样就找到第1小的元素，接着再遍历，minIndex = 1，遍历后面的待排序元素，找到第2小数据，并进行交换，以此类推…

【示意图】

【具体代码】

/*** Created with IntelliJ IDEA.* Description:* User: wlx* Date: 2025-06-02* Time: 10:53*/
public class SelectSort {public static void main(String[] args) {int[] array = {1,4,2,9,6,7};selectSort(array);System.out.println(Arrays.toString(array));}public static void selectSort(int[] array) {for(int i = 0; i < array.length; i++) {int minIndex = i;for(int j = i+1; j < array.length; j++) {if(array[j] < array[minIndex]) {minIndex = j;}}swap(array,i,minIndex);}}public static void swap(int[] array,int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}
}

【特性总结】

1. 时间复杂度：O(n²)
2. 空间复杂度：O(1)
3. 稳定性：不稳定

3.2 堆排序

【基本思想】堆排序是指利用堆这种数据结构所设计的一种算法，它是选择排序的一种，通过堆进行选择数据，排升序是建大堆，排降序建立小堆

大根堆：每个节点的值都 >= 其子节点的值，用于升序排列
小根堆：每个节点的值都 <= 其子节点的值，用于降序排列

【基本思路】堆排序就是先将我们的数组进行一次建堆，循环交换堆顶元素（最大值）与最后一个元素，即交换数组头和尾的元素，然后重新建堆，再进行交换堆顶元素与最后一个元素

【示意图】

【具体代码】

import java.util.Arrays;/*** Created with IntelliJ IDEA.* Description:* User: wlx* Date: 2025-06-22* Time: 23:52*/
public class HeapSort {public static void heapSort(int[] array) {createBigHeap(array);int end = array.length - 1;while (end > 0) {swap(array, 0, end);shiftDown(array, 0, end);end--;}}public 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;}}}public static void swap(int[] arr,int i,int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}public static void main(String[] args) {int[] array = {1,4,2,9,6,7};heapSort(array);System.out.println(Arrays.toString(array));}
}

【特性总结】

1. 时间复杂度：O(N*logN)
2. 空间复杂度：O(1)
3. 稳定性：不稳定

4. 交换类排序

4.1 冒泡排序

【基本思想】将待排序的数据两两进行比较，按比较结果来交换序列位置，将值大/值小的数据放到序列的尾部，将值小/值大的数据放到序列的首部位置，依次比较放置，最后得到有序序列

【基本思路】冒泡排序的每一次循环比较就是找出最大值(最小值)，将最大值(最小值)放在数组尾部(首部)，经过n次比较后，数据变成有序的，这里 flag 变量是优化作用，如果一轮下来没交换，则数组已经有序~

【示意图】

【具体代码】

/*** Created with IntelliJ IDEA.* Description:* User: wlx* Date: 2025-06-03* Time: 23:00*/
public class BubbleSort {public static void main(String[] args) {int[] array = {1,4,2,9,6,7};bubbleSort(array);for(int i = 0; i < array.length; i++) {System.out.print(array[i]+" ");}}private static void bubbleSort(int[] array) {for(int i = 0; i < array.length-1; i++) {boolean flag = false;for(int j = 0; j < array.length-1-i;j++) {if(array[j+1] < array[j]) {swap(array,j,j+1);flag = true;}}if(flag == false) {break;}}}public static void swap(int[] array,int i,int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}
}

【特性总结】

1. 时间复杂度：O(N^2)
2. 空间复杂度：O(1)
3. 稳定性：稳定

4.2 快速排序

【基本思想】先从数组中取一个数作为基准数，进行分区，将比这个大的数全放到它的右边，小于或等于它的数全部放到它的左边，直到所有元素在它的位置上，此时就有序了~

【主体框架】

这是快速排序的主框架，我们可以看到这和二叉树的前序遍历递归实现的方式很类似，因此，我们在写快速排序的时候，可以联想到二叉树的前序遍历是如何写的，接下来，介绍快速排序的几种方式：

public class quickSort {public void quickSort(int[] num) {int left = 0;int right = num.length-1;quick(num,left,right);}private void quick(int[] num, int left, int right) {if(left >= right) {return;}// 按照基准值对数组的[left,right]划分int pivot = partition(num,left,right);// 划分区间：[left,pivot-1] [pivot,right]// 递归排序[left,pivot-1]quick(num,left,pivot-1);// 递归排序[pivot,right]quick(num,pivot+1,right);}private int partition(int[] num, int left, int right) {// 根据一定的规则返回基准值return -1;}
}

4.2.1 三种实现方式

4.2.1.1 hoare 法

【基本思路】

hoare法就是定义两个标志位，right 从右往左找到比基准值小的值停下，left 从左往右找到比基准值大的值停下，交换 left 和 right 位置的值，循环继续，直到 left 和 right 相遇，最后再交换基准值和相遇处的值，再对左右子序列重复此过程，直到数据变成有序

1）先取最左侧即第一个元素为基准值
2）两个指针 left 和 right，left 从最左侧向右走，找到比基准大的元素停下，right 从最右侧向左走，找到比基准小的元素停下，交换 left 下标的值和 right 下标的值
3）当 left >= right 两个指针不再移动，此时 left = right 的下标即为基准值对应的下标，交换基准值初始下标和left(right)下标

【示意图】

【具体代码】

import java.util.Arrays;/*** Created with IntelliJ IDEA.* Description:* User: wlx* Date: 2025-06-22* Time: 0:05*/
public class quickSort {public static void quickSort(int[] num) {int left = 0;int right = num.length-1;quick(num,left,right);}public static void quick(int[] num, int left, int right) {if(left >= right) {return;}int pivot = partition(num,left,right);quick(num,left,pivot-1);quick(num,pivot+1,right);}// 1.hoare法public static int partition(int[] num, int left, int right) {// 根据一定的规则返回基准值int i = left+1;int j = right;int tmp = num[left];while(true) {while(i <= j && num[i] < tmp) {i++;}while(i <= j && num[j] > tmp) {j--;}if(i >= j) {break;}swap(num,i,j);}swap(num,left,j);return left;}public static void swap(int[] num,int i,int j) {int tmp = num[i];num[i]  = num[j];num[j] = tmp;}public static void main(String[] args) {int[] array = {1,4,2,9,6,7};quickSort(array);System.out.println(Arrays.toString(array));}
}

4.2.1.2 挖坑法

【基本思路】

1）先取最左侧即第一个元素为基准值
2）两个指针 left 和 right，left 从最左侧向右走，找到比基准大的元素停下，将 right 下标处的值赋值给 left 下标的值，right 从最右侧向左走，找到比基准小的元素停下，将 left 下标处的值赋值给 right 下标的值，如此循环
3）当 left >= right 两个指针不再移动，此时 left = right 的下标即为基准值对应的下标，交换基准值初始下标和left(right)下标

【示意图】

【具体代码】

import java.util.Arrays;/*** Created with IntelliJ IDEA.* Description:* User: wlx* Date: 2025-06-22* Time: 0:10*/
public class quickSort {public static void quickSort(int[] num) {int left = 0;int right = num.length-1;quick(num,left,right);}public static void quick(int[] num, int left, int right) {if(left >= right) {return;}int pivot = partition(num,left,right);quick(num,left,pivot-1);quick(num,pivot+1,right);}// 2.挖坑法public static int partition(int[] arr,int left,int right) {int tmp = arr[left];while(left < right) {// 找到比基准tmp小的while(left < right && arr[right] >= tmp) {right--;}arr[left] = arr[right];// 找到比基准tmp大的while(left < right && arr[left] <= tmp) {left++;}arr[right] = arr[left];}arr[left] = tmp;return left;}public static void main(String[] args) {int[] array = {1,4,2,9,6,7};quickSort(array);System.out.println(Arrays.toString(array));}
}

4.2.1.3 前后指针法

【基本思路】

1）先取最左侧即第一个元素为基准值
2）前后指针 prev 和 cur，prev初始为left，cur初始为right，如果 cur 下标值小于基准值并且前指针prev++后的值与cur下标值不相等，前后指针至少一个间隔，并且值不相等，则交换前后指针的值
3）最后cur走到right，循环结束，交换prev和left值，此时prev就是基准值的位置

【示意图】

【具体代码】

import java.util.Arrays;/*** Created with IntelliJ IDEA.* Description:* User: wlx* Date: 2025-06-22* Time: 0:30*/
public class quickSort {public static void quickSort(int[] num) {int left = 0;int right = num.length-1;quick(num,left,right);}public static void quick(int[] num, int left, int right) {if(left >= right) {return;}int pivot = partition(num,left,right);quick(num,left,pivot-1);quick(num,pivot+1,right);}//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;}public static void swap(int[] arr,int i,int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}public static void main(String[] args) {int[] array = {1,4,2,9,6,7};quickSort(array);System.out.println(Arrays.toString(array));}
}

4.2.1.4 快排优化

快排的基准是随机选取的，一般情况下，快排的时间复杂度为 O(nlog(n))，比如数据是有序的1,2,3,4,5… 会变成 O(n²)

时间复杂度我们可以用二叉树来理解，如下：

一般情况下，基准到达对应的位置后，序列被分为了左右子序列，基准元素为根结点，左边都比根节点的值小，右边都比根节点的值大，此时时间复杂度为 O(nlog(n))

存在特殊情况，数据是有序的1,2,3,4,5…

只有一个分支，此时树的高度就是结点的个数，时间复杂度则为O(n²)，而当数据量足够大的时候，上述代码就无法跑通了~

【优化方法】

1）基准优化：三数取中法

即基准值取 left，mid，right 三个值中间的值，而不再是单纯取下标为 left 的值

import java.util.Arrays;/*** Created with IntelliJ IDEA.* Description:* User: wlx* Date: 2025-06-22* Time: 0:40*/
public class quickSort {public static void quickSort(int[] num) {int left = 0;int right = num.length-1;quick(num,left,right);}public static void quick(int[] num, int left, int right) {if(left >= right) {return;}// 基准值优化int index = midThree(num,left,right);swap(num,index,left);int pivot = partition(num,left,right);quick(num,left,pivot-1);quick(num,pivot+1,right);}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 {if (array[mid] < array[right]) {return right;} else if (array[mid] > array[left]) {return left;} else {return mid;}}}public static int partition(int[] arr,int left,int right) {int tmp = arr[left];while(left < right) {// 找到比基准tmp小的while(left < right && arr[right] >= tmp) {right--;}arr[left] = arr[right];// 找到比基准tmp大的while(left < right && arr[left] <= tmp) {left++;}arr[right] = arr[left];}arr[left] = tmp;return left;}public static void swap(int[] arr,int i,int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}public static void main(String[] args) {int[] array = {1,4,2,9,6,7};quickSort(array);System.out.println(Arrays.toString(array));}
}

2) 递归至较小的子区间时，使用插入排序：

递归至较小区间的时间，数据渐渐趋于有序，当数据有序的时候，建议直接使用插入排序，这样效率是比较高的

4.2.2 快排非递归实现

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;/*** Created with IntelliJ IDEA.* Description:* User: wlx* Date: 2025-06-22* Time: 22:41*/// 非递归实现快排
public class quickSort {public static void quickSort(int[] array) {Deque<Integer> stack = new LinkedList<>();int left = 0;int right = array.length - 1;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);}}}public static int partition(int[] arr,int left,int right) {int tmp = arr[left];while(left < right) {// 找到比基准tmp小的while(left < right && arr[right] >= tmp) {right--;}arr[left] = arr[right];// 找到比基准tmp大的while(left < right && arr[left] <= tmp) {left++;}arr[right] = arr[left];}arr[left] = tmp;return left;}public static void main(String[] args) {int[] array = {1,4,2,9,6,7};quickSort(array);System.out.println(Arrays.toString(array));}}

5. 归并排序

【基本思想】归并排序是建立在归并操作上的一种有效算法，该算法是分治法的一种典型应用，将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，将两个有序序列合并为一个有序序列，称为二路归并

【基本思路】使用递归的方式，先分解，再进行合并

【示意图】

【具体代码】

import java.util.Arrays;/*** Created with IntelliJ IDEA.* Description:* User: wlx* Date: 2025-06-21* Time: 22:53*/
public class Mergesort {public static void mergeSort(int[] arr) {mergeFunc(arr,0,arr.length-1);}public static void mergeFunc(int[] arr,int left,int right) {if(left >= right) {return;}int mid = (left+right) / 2;mergeFunc(arr,left,mid);mergeFunc(arr,mid+1,right);merge(arr,left,right,mid);}public static void merge(int[] arr,int left,int right,int mid) {int start1 = left;int start2 = mid+1;int k = 0;int[] tmp = new int[right-left+1];while(start1 <= mid && start2 <= right) {if(arr[start1] < arr[start2]) {tmp[k++] = arr[start1++];} else {tmp[k++] = arr[start2++];}}while(start1 <= mid) {tmp[k++] = arr[start1++];}while(start2 <= right) {tmp[k++] = arr[start2++];}for(int i = 0; i < k; i++) {arr[left+i] = tmp[i];}}public static void main(String[] args) {int[] arr = {1,4,2,9,6,7};mergeSort(arr);System.out.println(Arrays.toString(arr));}
}

【特性总结】

1. 时间复杂度：O(O(N*logN))
2. 空间复杂度：O(1)
3. 稳定性：稳定
4. 应用场景：适合数据特别大的时候，当待排序数据特别大的时候，比如内存只要 10G，但是待排序的数据有 100G，此时可以将待处理的数据分为 20份，每一份 512M，利用归并排序分别对这 512M 的数据进行排序，同时进行二路归并，最后使数据变为有序，这就是文章一开头介绍的外部排序~

6. 特性总结

排序名称	平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
直接插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定
希尔排序	O(n^1.3) - O(n^1.5)	O(n log²n)	O(n log²n)	O(1)	不稳定
直接选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
堆排序	O(N*logN)	O(N*logN)	O(N*logN)	O(1)	不稳定
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	稳定
快速排序	O(N*logN)	O(N*logN)	O(N*logN)	O(logN)	不稳定
归并排序	O(N*logN)	O(N*logN)	O(N*logN)	O(1)	稳定

【注意】这里的时间复杂度为最坏时间复杂度

✨✨✨本期内容到此结束啦~