Java中的经典排序算法：插入排序、希尔排序、选择排序、堆排序与冒泡排序（如果想知道Java中有关插入排序、希尔排序、选择排序、堆排序与冒泡排序的知识点，那么只看这一篇就足够了！）

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

---

✨✨✨这里是秋刀鱼不做梦的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）原理与步骤

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

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

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

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

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

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

6. 重复步骤2~5。

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

        （3）Java代码实现

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

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）算法步骤

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

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

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

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

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

        （3）代码实现

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

public void shellSort(int[] array) {// 初始间隔设置为数组长度int gap = array.length;// 当间隔大于1时，继续进行希尔排序while (gap > 1) {// 更新间隔，通常将间隔除以2gap /= 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;}
}

注释解释：

1. shellSort 方法：

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

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

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

2. 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）算法步骤

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

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

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

注释解释：

1. selectSort 方法：

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

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

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

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

2. swap 方法：

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

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

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

时间复杂度：

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

空间复杂度：

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

        （5）应用场景

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

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

4.堆排序（Heap Sort）

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

        （1）算法简介

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

        （2）算法步骤

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

1. 构建一个最大堆。

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

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

4. 重复步骤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;
}

注释解释：

1. heapSort 方法：

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

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

2. makeHeap 方法：

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

3. 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）算法步骤

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

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

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

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

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

        （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;
}

注释解释：

1. bubbleSort 方法：

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

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

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

2. swap 方法：

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

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

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

时间复杂度：

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

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

空间复杂度：

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

        （5）应用场景

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

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

---

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