前言：排序算法是计算机科学中的基础问题之一，它在数据处理、搜索算法以及各种优化问题中占有重要地位，本文将详细介绍几种经典的排序算法：插入排序、选择排序、堆排序和冒泡排序。

✨✨✨这里是秋刀鱼不做梦的BLOG

✨✨✨想要了解更多内容可以访问我的主页秋刀鱼不做梦-CSDN博客

先让我们看一下本文大致的讲解内容：

        对于每个排序算法，我们都会从算法简介、其原理与步骤、代码实现、时间复杂度分析、空间复杂度分析与该排序算法的应用场景这几个方面来进行讲解。

目录

1.插入排序（InsertSort）

        （1）算法简介

        （2）原理与步骤

        （3）Java代码实现

        （4）时间复杂度 + 空间复杂度分析

        （5）应用场景

2.希尔排序（Shell Sort）

        （1）算法简介

        （2）算法步骤

        （3）代码实现

        （4）时间复杂度 + 空间复杂度分析

        （5）应用场景

3.选择排序（Selection Sort）

        （1）算法简介

        （2）算法步骤

        （3）代码实现

        （4）时间复杂度 + 空间复杂度分析

        （5）应用场景

4.堆排序（Heap Sort）

        （1）算法简介

        （2）算法步骤

        （3）代码实现

        （4）时间复杂度 + 空间复杂度分析

        （5）应用场景

5.冒泡排序（Bubble Sort）

        （1）算法简介

        （2）算法步骤

        （3）代码实现

        （4）时间复杂度 + 空间复杂度分析

        （5）应用场景

1.插入排序（InsertSort）

        （1）算法简介

在开始学习插入排序算法之前，先让我们来看一下该算法的概念：

        ——插入排序是一种简单直观的排序算法，通常用于对少量元素的排序。其基本思想是构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

        （2）原理与步骤

        了解了插入排序算法的概念之后，让我们看一下实现该排序算法的几个核心步骤：

从第一个元素开始，该元素可以认为已经被排序。

取出下一个元素，在已经排序的元素序列中从后向前扫描。

如果已排序的元素大于新元素，将该元素向右移动。

重复步骤3，直到找到已排序的元素小于或等于新元素的位置。

将新元素插入到该位置中。

重复步骤2~5。

        读者可以根据上述的描述先简要的了解一些插入排序的核心思路，接下来让我们使用代码来进行对其的实现。

        （3）Java代码实现

现在我们使用代码来实现一下插入排序算法：

<code>public class InsertionSort {

public void insertSort(int[] array) {

for (int i = 1; i < array.length; i++) {

int key = array[i];

int j = i - 1;

while (j >= 0 && array[j] > key) {

array[j + 1] = array[j];

j = j - 1;

}

array[j + 1] = key;

}

}

}

注释解释：

1.外层 for 循环：

从第二个元素（索引为1）开始遍历，因为第一个元素本身已经是一个排序好的子数组。

2.保存当前元素：

使用 temp 变量保存当前要插入的元素。

3.内层 for 循环：

从当前元素的前一个位置开始向前检查，如果已排序部分的元素大于 temp，就将该元素向后移动一位。

如果找到的元素小于或等于 temp，则跳出循环，说明找到了插入位置。

4.插入元素：

在找到的位置将 temp 插入到数组中。

这样我们就大致的了解了如何去实现插入排序算法了！

        （4）时间复杂度 + 空间复杂度分析

        对于插入排序，其最坏时间复杂度为O(n^2)，当数据完全逆序时，需进行最多的比较和移动操作。平均情况下的时间复杂度也是O(n^2)，但在最好的情况下（数据已经有序），时间复杂度为O(n)。

        插入排序是一个原地排序算法，只需要常数级别的额外空间，因此空间复杂度为O(1)。

        （5）应用场景

        插入排序常常用于小规模数据集，特别是在数组几乎有序的情况下非常高效。它的稳定性也是其一个优点，在某些需要稳定排序的应用中有着广泛应用。

        ——通过上边对插入排序的简单讲解，我们就大致的了解了插入排序算法了！

2.希尔排序（Shell Sort）

        了解完了插入排序之后，让我们看一下根据其优化的算法——希尔排序。

        （1）算法简介

        ——希尔排序（Shell Sort）是插入排序的改进版，它通过分组的方式减少插入排序的移动次数，从而提高排序效率。希尔排序通过一个间隔序列（gap sequence）将数组分成若干子序列，每个子序列进行插入排序，然后逐步减小间隔，最终完成排序。

        （2）算法步骤

        了解了希尔排序的基本概念之后，让我们看一下如何去实现希尔排序：

选择初始间隔（通常为数组长度的一半）。

对每个间隔下的子序列进行插入排序。

减小间隔，重复步骤2，直到间隔为1。

        ——那么接下来让我们使用代码来进行对其的实现。

        （3）代码实现

以下为实现希尔排序算法的代码：

public void shellSort(int[] array) {

// 初始间隔设置为数组长度

int gap = array.length;

// 当间隔大于1时，继续进行希尔排序

while (gap > 1) {

// 更新间隔，通常将间隔除以2

gap /= 2;

// 使用当前间隔进行插入排序

shellInsertSort(gap, array);

}

}

private void shellInsertSort(int gap, int[] array) {

// 从间隔后的第一个元素开始遍历

for (int i = gap; i < array.length; i++) {

// 保存当前要插入的元素

int temp = array[i];

// 从当前元素的前一个间隔位置开始向前检查

int j = i - gap;

// 将当前元素与前面间隔的元素进行比较

// 如果前面间隔的元素大于当前元素，则将前面间隔的元素向后移动一位

// 否则，找到正确的位置

for (; j >= 0; j -= gap) {

if (array[j] > temp) {

array[j + gap] = array[j]; // 移动元素

} else {

break; // 找到插入位置

}

}

// 将当前元素插入到找到的位置

array[j + gap] = temp;

}

}

注释解释：

shellSort 方法：

初始化间隔：设置初始间隔为数组的长度。

更新间隔：通过将间隔除以2来逐步减小间隔，直到间隔小于等于1。

调用插入排序：使用当前的间隔值调用 shellInsertSort 方法对数组进行插入排序。

shellInsertSort 方法：

遍历数组：从当前间隔位置的第一个元素开始遍历数组。

保存当前元素：将当前元素保存到 temp 中。

检查并插入：从当前元素的前一个间隔位置开始向前检查，如果前面的元素大于当前元素，则将前面的元素向后移动一位，直到找到适合插入的位置。

插入元素：将当前元素 temp 插入到找到的位置。

        这样我们就大致的了解了如何去实现希尔排序算法了！

        （4）时间复杂度 + 空间复杂度分析

        希尔排序的时间复杂度取决于选择的间隔序列。常见的间隔序列有Shell增量（n/2, n/4, …, 1）和Hibbard增量（1, 3, 7, 15, …）。时间复杂度通常介于O(n)和O(n^2)之间，最坏情况下为O(n^2)。

        希尔排序也是一种原地排序算法，空间复杂度为O(1)。

        （5）应用场景

        希尔排序适用于中小规模的数据集，特别是在内存较为紧张且需要较高排序效率的场景下表现优异。

        ——通过上边对希尔排序的简单讲解，我们就大致的了解了希尔排序算法了！

3.选择排序（Selection Sort）

        接下来让我们学习选择排序算法。

        （1）算法简介

        ——选择排序（Selection Sort）是一种简单的排序算法。它的基本思想是每次从未排序部分中选择最小的元素，放到已排序部分的末尾。选择排序的特点是每次交换位置时，都能确定一个元素的最终位置，因此它的交换次数较少。

        （2）算法步骤

        在了解完了选择排序算法的概念之后，让我们看一下实现其算法的核心步骤：

从数组中找到最小的元素，将其与数组的第一个元素交换位置。

在剩下的未排序部分中重复上述步骤，直到所有元素都已排序。

这样，我们就了解了选择排序的核心思路了，接下来让我们使用代码对其进行实现。

        （3）代码实现

以下为实现选择排序算法的代码：

public void selectSort(int[] array) {

// 遍历数组的每一个元素

for (int i = 0; i < array.length - 1; i++) {

// 假设当前元素是最小值

int minIndex = i;

// 在未排序部分中寻找最小值的索引

for (int j = i + 1; j < array.length; j++) {

// 如果找到比当前最小值还小的元素，则更新最小值的索引

if (array[j] < array[minIndex]) {

minIndex = j;

}

}

// 将当前元素与找到的最小值交换位置

swap(array, i, minIndex);

}

}

private void swap(int[] array, int pos1, int pos2) {

// 交换数组中两个位置的元素

int temp = array[pos1];

array[pos1] = array[pos2];

array[pos2] = temp;

}

注释解释：

selectSort 方法：

遍历数组：通过外层循环遍历数组的每个元素，作为当前排序的起始位置。

寻找最小值：假设当前元素是最小值，并使用内层循环在未排序部分中寻找更小的值。

更新最小值索引：如果找到比当前最小值更小的元素，则更新 minIndex 为这个元素的位置。

交换元素：调用 swap 方法，将当前元素与找到的最小值元素交换位置，使得最小值元素放置在当前排序的位置上。

swap 方法：

交换位置：使用临时变量 temp 来交换数组中两个指定位置的元素。

        这样我们就大致的了解了如何去实现选择排序算法了！

        （4）时间复杂度 + 空间复杂度分析

时间复杂度：

最坏情况：O(n^2)最好情况：O(n^2)平均情况：O(n^2)

空间复杂度：

        选择排序也是一种原地排序算法，空间复杂度为O(1)。

        （5）应用场景

        选择排序适用于对内存写操作次数敏感的场景，因为它的交换次数较少。此外，选择排序在数据量不大且对排序效率要求不高的场合中表现良好。

        ——通过上边对选择排序的简单讲解，我们就大致的了解了选择排序算法了！

4.堆排序（Heap Sort）

        接下来让我们学习堆排序算法。

        （1）算法简介

        ——堆排序（Heap Sort）是一种基于堆这种数据结构的排序算法。堆是一种近似完全二叉树的结构，分为大顶堆和小顶堆。堆排序通过构建一个大顶堆或小顶堆，将根节点与末尾元素交换，逐步减少堆的大小，最终完成排序。

        （2）算法步骤

        在了解完了堆排序算法的概念之后，让我们看一下实现其算法的核心步骤：

构建一个最大堆。

将堆顶元素（最大值）与最后一个元素交换，将堆的大小减1。

调整堆结构，使其重新满足最大堆性质。

重复步骤2和3，直到堆的大小为1。

        接下来让我们使用代码来进行对其的实现。

        （3）代码实现

以下为实现堆排序算法的代码：

public void heapSort(int[] array) {

// 将数组转换为大根堆

// 从最后一个非叶子节点开始，向上调整堆

for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {

makeHeap(array, parent, array.length);

}

// 交换堆顶（最大值）和最后一个元素，重新调整堆

int end = array.length - 1;

while (end > 0) {

// 交换堆顶和当前堆的最后一个元素

swap(array, 0, end);

// 调整新的堆顶

makeHeap(array, 0, end);

end--;

}

}

private void makeHeap(int[] array, int parent, int length) {

// 左子节点的索引

int child = 2 * parent + 1;

while (child < length) {

// 如果右子节点存在且大于左子节点，则将子节点设置为右子节点

if (child + 1 < length && array[child] < array[child + 1]) {

child++;

}

// 如果父节点小于子节点，则交换父节点和子节点

if (array[parent] < array[child]) {

swap(array, parent, child);

// 更新父节点为刚交换过的子节点

parent = child;

// 更新子节点为新的左子节点

child = 2 * parent + 1;

} else {

break;

}

}

}

private void swap(int[] array, int pos1, int pos2) {

// 交换数组中两个位置的元素

int temp = array[pos1];

array[pos1] = array[pos2];

array[pos2] = temp;

}

注释解释：

heapSort 方法：

构建大根堆：从最后一个非叶子节点开始（计算公式 (array.length - 1 - 1) / 2），对每个节点调用 makeHeap 方法来调整堆，使整个数组成为一个大根堆。

排序过程：将堆顶（最大值）与当前堆的最后一个元素交换，并对新的堆顶进行调整。每次调整后减少堆的有效长度 end，直到 end 为0，即整个数组已经排序完毕。

makeHeap 方法：

调整堆：从父节点开始，检查并维护大根堆的性质。如果子节点存在且大于父节点，则交换父节点和子节点，更新父节点为子节点并继续调整。直到堆的性质被维护好或者没有需要调整的地方。

swap 方法：

交换位置：使用临时变量 temp 来交换数组中两个指定位置的元素

这样我们就大致的了解了如何去实现堆排序算法了！

        （4）时间复杂度 + 空间复杂度分析

堆排序的时间复杂度主要来自于构建最大堆和调整堆的过程：

最坏情况：O(n log n)最好情况：O(n log n)平均情况：O(n log n)

        由于堆的调整涉及到树的高度，而树的高度为log n，因此每次调整堆的复杂度为O(log n)，总的时间复杂度为O(n log n)。

        堆排序是原地排序算法，不需要额外的存储空间，空间复杂度为O(1)。

        （5）应用场景

        堆排序适用于需要高效且稳定的排序场景，尤其在需要排序较大数据集的情况下，堆排序表现良好，由于其时间复杂度在最坏情况下仍然保持O(n log n)，堆排序在处理大量数据时非常有用。

        ——通过上边对堆排序的简单讲解，我们就大致的了解了堆排序算法了！

5.冒泡排序（Bubble Sort）

        最后，让我们学习一下冒泡排序算法。

        （1）算法简介

        ——冒泡排序（Bubble Sort）是一种最简单的排序算法之一。它的基本思想是通过多次遍历数组，每次都将相邻的两个元素进行比较，并根据大小关系交换它们的位置。这样，较大的元素逐步“冒泡”到数组的末尾。尽管冒泡排序的效率较低，但它的概念简单，容易理解和实现。

        （2）算法步骤

        了解了冒泡排序算法的概念之后，让我们看一下实现该排序算法的几个核心步骤：

从数组的起始位置开始，逐个比较相邻的两个元素。

如果前一个元素比后一个元素大，则交换它们的位置。

对整个数组进行多次遍历，直到没有元素需要交换为止。

接下来我们使用代码对其进行实现。

        （3）代码实现

以下为实现冒泡排序算法的代码：

public void bubbleSort(int[] array) {

// 外层循环控制排序的轮数

for (int i = 0; i < array.length - 1; i++) {

// 标志位，用于检测是否有交换发生

boolean flag = true;

// 内层循环进行相邻元素的比较和交换

for (int j = 0; j < array.length - 1 - i; j++) {

// 如果当前元素大于下一个元素，则交换它们

if (array[j] > array[j + 1]) {

flag = false; // 设置标志位为 false，表示发生了交换

swap(array, j, j + 1);

}

}

// 如果在某一轮排序中没有发生交换，说明数组已经有序，提前退出循环

if (flag) {

break;

}

}

}

private void swap(int[] array, int pos1, int pos2) {

// 交换数组中两个位置的元素

int temp = array[pos1];

array[pos1] = array[pos2];

array[pos2] = temp;

}

注释解释：

bubbleSort 方法：

外层循环：控制排序的轮数，总共需要 array.length - 1 轮。在每一轮中，最大的元素会被移动到数组的末尾。

标志位 flag：在每一轮开始时，假设数组已经有序。如果在该轮中没有发生任何交换，flag 会保持为 true，表明数组已经完全排序好，可以提前结束排序。

内层循环：比较相邻的元素，如果当前元素大于下一个元素，则交换它们，并将 flag 设置为 false，表示发生了交换。每次比较和交换的范围逐渐减小，因为每轮排序都会将最大元素移到末尾。

swap 方法：

交换位置：使用临时变量 temp 来交换数组中两个指定位置的元素。

这样我们就大致的了解了如何去实现冒泡排序算法了！

        （4）时间复杂度 + 空间复杂度分析

时间复杂度：

最坏情况：O(n^2)（数组为逆序）最好情况：O(n)（数组已经有序）平均情况：O(n^2）

        在最坏和平均情况下，冒泡排序的时间复杂度都是O(n^2)，但在最佳情况下，当数组已经有序时，冒泡排序的复杂度可以降为O(n)。

空间复杂度：

        冒泡排序是原地排序算法，不需要额外的存储空间，空间复杂度为O(1)。

        （5）应用场景

        冒泡排序适用于小规模数据集或数据基本有序的情况。尽管冒泡排序的效率较低，但其实现简单，常用于教学演示或一些对效率要求不高的应用场景。

        ——通过上边对堆排序的简单讲解，我们就大致的了解了堆排序算法了！

以上就是本篇文章的全部内容了~~~