Java 【数据结构】常见排序算法实用详解（上）插入排序/希尔排序/选择排序/堆排序【贤者的庇护】

登神长阶

上古神器-常见排序算法

插入排序/选择排序/堆排序

📔 一.排序算法

📕1.排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

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

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

📗2.排序算法

在Java中，排序算法是一种对数据集合中的元素按照特定顺序进行排列的算法。排序算法通常用于将数据按照升序或者降序排列，以便于后续的查找、插入、删除等操作。排序算法在Java中是非常常见和重要的，因为数据的排序是计算机科学中的基本问题之一，几乎所有的应用场景都需要对数据进行排序。

在Java中，排序算法可以针对不同的数据结构实现，例如针对数组、链表、树等。常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。每种排序算法都有其特定的实现方式、时间复杂度和空间复杂度，不同的算法在不同的场景下有着各自的优劣势。

Java提供了丰富的API和工具类来支持排序操作。比如，可以使用 java.util.Arrays 类的 sort() 方法对数组进行排序，该方法内部使用了优化的快速排序算法或归并排序算法；另外，Java中的集合类如 ArrayList、LinkedList 等也提供了 Collections.sort() 方法来对集合进行排序，同样利用了内部的排序算法来实现。

总之，在Java中，排序算法是程序员必须掌握的基本知识之一，对排序算法的理解和掌握有助于编写出高效、可靠的Java程序。

在本次chapter1我们先对插入排序，希尔排序，选择排序，堆排序进行一个深度理解。

📘3.排序的运用

排序算法在Java项目中有着广泛的应用，主要体现在以下几个方面：

数据存储与检索：在实际项目中，经常需要对大量数据进行存储和检索，而这些数据可能需要按照某种顺序进行排列。例如，对于电子商务网站，商品列表需要按照价格、销量等指标进行排序，以便用户浏览和筛选。在这种情况下，可以利用Java提供的排序算法对数据进行排序，以便更高效地进行检索和展示。
数据分析与统计：在数据分析和统计领域，经常需要对大量数据进行排序以便进行分析和计算。例如，在金融领域，对交易数据进行排序可以帮助识别交易模式和规律；在科学研究中，对实验数据进行排序可以帮助找到数据的规律和趋势。Java中的排序算法可以帮助开发人员快速对数据进行排序，从而支持数据分析和统计的工作。
搜索与查找：在搜索和查找功能中，排序算法也发挥着重要作用。例如，在搜索引擎中，对搜索结果进行排序可以根据相关度、权重等指标进行排序，提高搜索结果的质量和用户体验；在数据库系统中，对数据库中的记录进行排序可以提高查询效率，加快数据检索的速度。Java中的排序算法可以帮助开发人员实现这些功能，从而提升系统的性能和用户体验。
任务调度与优先级管理：在任务调度和优先级管理中，排序算法可以帮助开发人员对任务进行排序和调度，以提高系统的响应速度和效率。例如，在操作系统中，可以利用排序算法对进程进行优先级调度，从而保证系统的稳定性和效率；在分布式系统中，可以利用排序算法对任务进行分配和调度，以实现负载均衡和资源优化。Java中的排序算法可以为开发人员提供实现这些功能的工具和方法。

总之，排序算法在Java项目中具有广泛的应用场景，可以帮助开发人员解决各种实际问题，提高系统的性能和效率，提升用户体验。通过灵活运用各种排序算法，开发人员可以实现更加高效、稳定和可靠的Java应用程序。

📙二.插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法，在实际应用中也是比较常见的一种。它的基本思想是将一个待排序的元素逐个插入到已经排序好的子序列中，直到所有元素都插入完毕。插入排序通常采用在原地排序的方式进行，不需要额外的存储空间，因此空间复杂度为 O(1)。

基本思想

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

基本原理

从第二个元素开始，将其视为已排序的子序列：初始时，将第一个元素视为已排序的子序列。
逐个将未排序的元素插入已排序的子序列中：从第二个元素开始，依次将每个元素与已排序的子序列中的元素比较，找到合适的位置插入。
重复直到所有元素都插入完毕：重复以上步骤，直到所有元素都插入到已排序的子序列中，排序完成。

算法步骤

从第二个元素开始遍历数组。
对于当前遍历到的元素，从后往前遍历已排序的子序列，找到合适的位置插入。
插入元素后，继续遍历下一个未排序的元素，重复以上步骤直到所有元素都插入完毕。

时间复杂度

插入排序的时间复杂度取决于待排序数组的初始状态。在最好情况下，即数组已经有序，插入排序的时间复杂度为 O(n)，每个元素只需要与前面的有序序列比较一次。在最坏情况下，即数组完全逆序，插入排序的时间复杂度为 O(n^2)，每个元素需要与前面的有序序列比较 n-1 次。平均情况下，插入排序的时间复杂度也为 O(n^2)。

稳定性

插入排序是一种稳定的排序算法，即相等元素的相对顺序在排序前后保持不变。

适用性

小规模数组：对于小规模数组，插入排序是一个不错的选择，因为它的实现简单且性能较好。
部分有序的数组：如果数组已经部分有序，插入排序的效率会更高，因为大部分元素都在正确的位置上，只需少量的比较和移动。
稳定性要求：如果需要保持相等元素的相对顺序不变，插入排序是一个合适的选择。
链表结构：插入排序在链表结构中也适用，因为它只需要在链表中移动指针，不需要像数组一样进行元素的移动。

源代码

 /**
     * 插入排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * 场景：当前有一组数据 基本上趋于有序 那么就可以使用直接插入排序
     * 优点：越有序越快
     * @param array
     */
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int temp=array[i];
            int j=i-1;
            for (;j>=0;j--){
                //if(array[j]>=temp)该排序就不稳定了
                if (array[j]>temp){
                    array[j+1]=array[j];
                }else{
                    break;
                }
            }
            array[j+1]=temp;
        }
    }

插入排序虽然简单，但在某些特定情况下仍然是一个有效且高效的排序算法。

📓三.希尔排序

希尔排序的基本思想原理都是建立在插入排序之上的可以进行对比学习

希尔排序法又称缩小增量法。

基本原理：

希尔排序是一种改进的插入排序算法，旨在解决插入排序在处理大规模数据时效率较低的问题。它的基本原理是通过将数组分成若干个子序列，并对每个子序列进行插入排序，然后逐步减小子序列的长度，最终达到对整个数组的排序。希尔排序利用了插入排序在局部有序情况下效率较高的特点，通过逐步缩小间隔，最终实现整体排序。

算法步骤：

选择增量序列： 首先选择一个增量序列，通常使用 Knuth 提出的序列（如 3x+1）。增量序列决定了子序列的划分方式。
分组： 将数组按照增量序列分成若干个子序列。
对每个子序列进行插入排序： 对每个子序列进行插入排序，即将每个子序列中的元素按照插入排序的方式进行排序。
逐步减小增量： 重复以上步骤，但每次使用较小的增量。这样做的目的是逐步使得数组中的元素趋于有序。
最终排序： 当增量减小到 1 时，整个数组被划分为一个子序列，这时再对整个数组进行一次插入排序，使得整个数组达到有序状态。

时间复杂度：

希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定

希尔排序的时间复杂度取决于增量序列的选择。最坏情况下的时间复杂度为 O(n^2)，但在实践中，希尔排序通常要优于插入排序的 O(n^2)。理想情况下，时间复杂度为 O(n log^2 n)，这是一个未解决的数学问题。

稳定性：

希尔排序是不稳定的排序算法。因为在排序过程中，相同元素的相对位置可能会改变，取决于增量序列的选择和具体的实现方式。

适用性：

希尔排序适用于中等大小的数组，特别是对于需要排序的数据量较大但内存有限的情况。
由于希尔排序是原地排序算法，不需要额外的空间开销，因此适用于内存有限的环境。
在大多数情况下，希尔排序的性能要优于简单的插入排序和冒泡排序，但可能不如快速排序、归并排序等高级排序算法。

/**
     * 希尔排序
     * 时间复杂度：O(logN)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void shellSort(int[] array){
        int gap=array.length;
        while(gap>1){
            gap=gap/3+1;
            shell(array,gap);
        }
    }

    public static void shell(int[] array,int gap){
        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;
        }
    }

希尔排序通过优化插入排序的步骤和增量序列的选择，提高了对大规模数据的排序效率，是一种常用的排序算法之一。

📒四.选择排序

选择排序相对是一种更为简单更为直接的排序算法。

基本原理：

选择排序（Selection Sort）是一种简单直观的排序算法，其基本原理是每次从待排序的数据中选择最小（或最大）的元素，放到已排序序列的末尾。通过不断重复这个过程，直到所有元素都被排序完毕。

算法步骤：

找到最小元素： 遍历未排序部分的数组，找到最小（或最大）的元素。
交换位置： 将最小的元素与未排序部分的第一个元素交换位置，将其放到已排序序列的末尾。
逐步缩小范围： 缩小未排序部分的范围，将已排序部分扩大一个元素。
重复直至完成： 重复以上步骤，直到所有元素都被排序完毕。

时间复杂度：

选择排序的时间复杂度始终为 O(n^2)，无论输入数据的情况如何，因为它每次都要遍历未排序部分的数组来找到最小元素。

稳定性：

选择排序是一种不稳定的排序算法，因为在选择的过程中，相同元素的相对位置可能会改变。例如，在排序过程中，如果有两个相同的最小元素，它们的相对位置可能会发生变化。

适用性：

选择排序适用于小型数组或者简单实现的排序场景。
它是一种原地排序算法，不需要额外的空间开销，因此适用于内存有限的环境。
尽管选择排序的时间复杂度较高，但对于简单的排序任务，或者当内存不足以容纳更复杂的算法时，选择排序仍然是一个合理的选择。

 /**
     * 选择排序
     * 时间复杂度：和数据是否有序无关。均是O(N^2)
     * 空间复杂度： O(1)
     * 稳定性：不稳定的排序
     * @param 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[minIndex]>array[j]){
                    minIndex=j;
                }
            }
            int cur=array[i];
            array[i]=array[minIndex];
            array[minIndex]=cur;
        }
    }

    public static void selectSort2(int[] array){
        int left=0;
        int right=array.length-1;
        while(left<right) {
            int minIndex=left;
            int maxIndex=left;
            for (int i = left+1; i <= right; i++) {
                if (array[i]<array[minIndex]){
                    minIndex=i;
                }
                if (array[i]>array[maxIndex]){
                    maxIndex=i;
                }
            }
            swap(array,minIndex,left);
            if (maxIndex==left){
                maxIndex=minIndex;
            }
            swap(array,maxIndex,right);
            left++;
            right--;
        }
    }

    public static void swap(int[] arr,int a,int b){
        int cur=arr[a];
        arr[a]=arr[b];
        arr[b]=cur;
    }

上述代码之中，selectSort2算是选择排序的一种优化

选择排序虽然简单，但是其效率较低，特别是在大规模数据的情况下。在实际应用中，往往会选择更高效的排序算法，如快速排序、归并排序等。

📃五.堆排序

基本原理：

堆排序（Heap Sort）是一种基于二叉树（Java 【数据结构】二叉树（Binary_Tree））数据结构的排序算法。它的基本原理是首先将待排序的数组构建成一个最大堆（或最小堆），然后逐步将堆顶元素（最大元素或最小元素）与堆的最后一个元素交换位置，并将剩余元素重新调整为一个最大堆（或最小堆），重复这个过程直至整个数组有序。

需要注意的是排升序要建大堆，排降序建小堆。

算法步骤：

构建堆： 将待排序的数组看作是一个完全二叉树，并按照从下往上、从右往左的顺序，对每个非叶子节点进行堆化操作，使得整个数组构成一个堆结构（通常是最大堆）。
堆排序： 将堆顶元素（最大元素或最小元素）与堆的最后一个元素交换位置，然后将剩余元素重新调整为一个最大堆（或最小堆）。
重复直至完成： 重复上述堆排序步骤，每次将堆的大小减少 1，并重新调整堆结构，直至整个数组有序。

时间复杂度：

堆排序的时间复杂度为 O(n log n)，其中 n 是待排序数组的大小。这是因为堆的构建需要 O(n) 的时间，而每次堆调整（包括堆化和交换操作）的时间复杂度为 O(log n)，总共需要进行 n 次调整。

稳定性：

堆排序是一种不稳定的排序算法，因为在堆的调整过程中，相同元素的相对位置可能会发生改变。

适用性：

堆排序适用于大规模数据的排序，特别是对于需要稳定性较好的排序算法。
它是一种原地排序算法，不需要额外的空间开销，因此适用于内存有限的环境。
尽管堆排序的时间复杂度较高，但由于其稳定性和原地排序的特性，仍然是一种常用的排序算法。

/**
     * 堆排序
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param arr
     */
    public static void heapSort(int[] arr){
        makebigHeap(arr);
        int end=arr.length-1;
        while(end>=0){
            swap(arr,0,end);
            siftDown(0,arr,end);
            end--;
        }
    }

    public static void makebigHeap(int[] arr){
        for (int parent = (arr.length-1-1)/2; parent >=0; parent--) {
            siftDown(parent,arr,arr.length);
        }
    }

    public static void siftDown(int parent,int[] arr,int end){
        int child=parent*2+1;
        while(child<end){
            if (child+1<end&&arr[child+1]>arr[child]){
                child++;
            }
            if (arr[child]>arr[parent]){
                swap(arr,child,parent);
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }
}

堆排序通过利用堆的特性，实现了对大规模数据的高效排序，是一种重要的排序算法之一。