
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）应用场景

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

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

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/1014352