“从根到叶：深入理解排序数据结构“

一.排序的概念及引用

1.1排序的概念

排序是指将一组数据按照一定的规则重新排列的过程。排序的目的是为了使数据具有有序性，便于查找、插入、删除等操作，提高数据的组织和管理效率。

稳定性是指如果序列中存在相等元素，在排序完成后，相等元素之间的相对顺序是否被保持不变。

---

二.插入排序

想象一下，你手里拿着一副乱序的扑克牌，想要将它们按照从小到大的顺序排列。你会从左边开始，一张一张地拿起牌，然后将它们插入到已经有序的牌堆中的正确位置。

开始的时候，你只有一张牌，所以它已经是有序的。接着，你拿起第二张牌，将它与第一张牌进行比较。如果第二张牌比第一张牌小，你就将第二张牌插入到第一张牌的左边；否则，你将第二张牌放在第一张牌的右边。

然后，你拿起第三张牌，将它与前面的已排序牌进行比较。如果第三张牌比前面的牌都小，你就将第三张牌插入到已排序牌的最左边；否则，你从右向左依次比较，找到第三张牌应该插入的位置。

你会一直重复这个过程，每次拿起一张新的牌，找到它应该插入的位置，并将它插入到正确的位置。最终，当你拿起最后一张牌并插入到适当的位置后，所有的牌就都排好序了。

插入排序的基本思想就是通过不断地将未排序的元素插入到已排序的序列中，逐步构建有序序列。这个过程类似于整理扑克牌时的插入动作，因此称之为插入排序。

插入排序的适用场景：

插入排序在以下情况下适用：

1. 小规模数据集：插入排序对于小规模的数据集合表现良好。当待排序的数据量较小时，插入排序的时间复杂度较低，并且实现简单，适合用于排序少量元素的情况。

2. 部分有序的数据集合：如果待排序的数据集合已经部分有序，插入排序的效率会比较高。在这种情况下，插入排序的比较次数和移动次数会减少，因为只需要将较小的元素插入到已排序的部分中。

3. 数据集合基本有序，但有少量逆序对：如果待排序的数据集合基本有序，但有少量逆序对（相邻元素大小顺序相反），插入排序的效率还是较高的。因为每次插入操作只需要将一个元素移动到正确的位置，逆序对的数量较少，整体比较和移动的次数相对较少。

4. 需要稳定排序算法：插入排序是一种稳定的排序算法，即相等元素的相对顺序不会改变。在某些应用场景中，需要保持相等元素的相对顺序，这时插入排序是一个合适的选择。

注意：对于大规模无序的数据集合，插入排序的效率相对较低，性能不如快速排序、归并排序等具有较好平均时间复杂度的算法。在这种情况下，可以选择其他更高效的排序算法来处理大规模数据集合。 

2.1直接插入排序

它的基本思想是将待排序的序列分为已排序部分和未排序部分，每次从未排序部分选择一个元素，插入到已排序部分的适当位置，直到所有元素都被插入到已排序部分并完成排序。

以下是直接插入排序的具体步骤：

1. 假设待排序序列为arr，长度为n。
2. 从索引为1的位置开始，将arr[1]作为已排序部分。
3. 从索引为2的位置开始迭代，将arr[i]与已排序部分中的元素比较。
4. 如果arr[i]小于已排序部分的某个元素arr[j]，则将arr[i]插入到arr[j]之前，并将arr[j]及其后面的元素后移一位。
5. 重复步骤4，直到找到arr[i]的正确位置或者已经比较完已排序部分的所有元素。
6. 重复步骤2~5，直到所有元素都被插入到已排序部分并完成排序。

该图来源：1.3 插入排序 | 菜鸟教程 (runoob.com)

举例子如下:

假设现在你有一组待排序的arr数组

第一次插入

第二次插入:

第三次插入:

第四次插入:

 完成排序

相关代码如下:

private 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 (tmp < array[j]) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
 
        }
 
    }
 
 
 public static void main(String[] args) {
        int[] array = {27,15,9,18,28};
        System.out.println("原数组 "+Arrays.toString(array));
        sort.countSort(array);
        System.out.println("直接插入排序后 "+Arrays.toString(array));
 
    }

运行截图如下:

直接插入排序的优点:

直接插入排序虽然在大规模无序数据集合上的效率相对较低，但它也有一些优点，特别适用于特定的场景和数据集合，包括：

1. 简单易实现：直接插入排序是一种非常简单直观的排序算法，易于理解和实现。它的算法思想直接反映在代码中，不需要复杂的逻辑或额外的数据结构。
2. 原地排序：直接插入排序是一种原地排序算法，即它只需要使用原始数据集合所占用的内存空间，不需要额外的存储空间。
3.  稳定性：直接插入排序是一种稳定的排序算法，即相等元素的相对顺序不会改变。这在某些应用场景中很重要，需要保持相等元素的相对位置关系。
4. 部分有序数据集合：对于部分有序的数据集合，直接插入排序的效率较高。它的比较次数和移动次数较少，适合处理已经接近有序的数据。
5. 小规模数据集合：对于小规模的数据集合，直接插入排序表现良好。它的时间复杂度为O(n^2)，但在数据量较小的情况下，这个复杂度仍然是可接受的。

 直接插入的时间和空间复杂度

1. 时间复杂度：直接插入排序的平均时间复杂度为O(n^2)，其中n是待排序序列的长度。在最坏情况下，即待排序序列完全逆序时，时间复杂度为O(n^2)。在最好情况下，即待排序序列已经有序时，时间复杂度可以降低到O(n)。平均情况下，直接插入排序的比较次数和移动次数都是n(n-1)/4，因此时间复杂度为O(n^2)。

2. 空间复杂度：直接插入排序是一种原地排序算法，它只需要使用原始数据集合所占用的内存空间，不需要额外的存储空间。因此，它的空间复杂度为O(1)，即常数级别的空间复杂度。

1. 元素集合越接近有序，直接插入排序
2. 算法的时间效率越高
3. 时间复杂度：O(N^2)
4. 空间复杂度：O(1)，它是一种稳定的排序算法
5. 稳定性：稳定

2.2希尔排序

基本思想:希尔排序法又称缩小增量法,希尔排序（Shell Sort）是一种排序算法，它是插入排序的一种改进版本。希尔排序的基本思想是将待排序的数组元素按照一定的间隔进行分组，对每组进行插入排序，随着间隔的逐渐缩小，每组包含的元素越来越多，当间隔缩小到1时，整个数组就被分成一组，此时进行最后一次插入排序后，排序完成.

希尔排序的步骤如下：

1. 选择一个间隔序列（通常是按照一定规则确定的），将待排序的数组按照间隔分成多个子序列。
2. 对每个子序列进行插入排序，即从第二个元素开始，与前面的元素进行比较并插入到正确的位置。
3. 逐步缩小间隔，重复进行第2步操作，直到间隔缩小到1。
4. 进行最后一次插入排序，此时整个数组已经基本有序，只需进行少量的比较和移动操作即可完成排序。

该图从网上搜寻,如有侵权,请联系作者调整!

举例子解释:

假设有一组未排序的数组:

其中gap 作为元素间隔的个数

 相关代码如下:

public static void shellSort(int[] arr){
    int gap = arr.length; // 初始化间隔为数组长度
    while (gap > 1){ // 当间隔大于1时继续循环
        gap = gap/2; // 缩小间隔
        shell(arr, gap); // 调用shell方法进行分组插入排序
    }
}
 
public static void shell(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 {
                break; // 如果前一个元素小于等于当前元素，则结束循环
            }
        }
        array[j + gap] = tmp; // 插入当前元素到正确的位置
    }
}
 
 
//主函数测试
 
  public static void main(String[] args) {
        int[] array = {9,1,2,5,7,4,8,6,3,5};
        System.out.println("原数组 "+Arrays.toString(array));
        sort.shellSort(array);//调用希尔排序方法
        System.out.println("希尔排序后 "+Arrays.toString(array));
 
    }

 运行截图如下:

希尔排序的优点:

1. 改进的插入排序：希尔排序是插入排序的改进版本。通过分组插入排序的方式，可以在每一轮排序中将较远距离的元素移动到正确的位置，从而减少了元素的比较和交换次数。

2. 不稳定排序：希尔排序是一种不稳定的排序算法，即相同值的元素在排序后的相对位置可能发生变化。这是因为希尔排序是通过间隔分组进行排序，相同值的元素可能被分到不同的组中，导致它们之间的相对顺序发生改变。

3. 适用于大规模数据：希尔排序相对于简单的插入排序在大规模数据排序方面具有一定的优势。由于它可以通过缩小间隔的方式进行预排序，可以减少后续排序所需的比较和交换次数，从而提高排序效率。

4. 不需要额外的存储空间：希尔排序是一种原地排序算法，不需要额外的存储空间来存储临时数据。它通过在原始数组上进行元素的比较和交换来实现排序。

希尔排序的时间复杂度和空间复杂度

1. 时间复杂度：希尔排序的时间复杂度取决于间隔序列的选择。在最坏的情况下，希尔排序的时间复杂度为O(n^2)，其中n是待排序数组的长度。这种情况发生在间隔序列不好的情况下，例如使用常规的希尔序列（例如，gap = n/2, gap = gap/2）。。

2. 空间复杂度：希尔排序是一种原地排序算法，因此它的空间复杂度是O(1)，即不需要额外的存储空间来存储临时数据。希尔排序通过在原始数组上进行元素的比较和交换来实现排序，不会使用额外的内存空间。

参考代码如下:

public static void swap(int[] array, int i, int j) {
    // 交换数组中索引为i和j的两个元素的位置
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}
 
public static void selectSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int min = i; // 当前最小值的索引
 
        for (int j = i + 1; j < array.length; j++) {
            // 在未排序区中找到比当前最小值更小的元素，更新最小值的索引
            if (array[j] < array[min]) {
                min= j;
            }
        }
        
        swap(array, i, min); // 将最小值与待排序数组的第一个元素交换位置，将最小值放到已排序区的末尾
    }
}
 
 
 
public static void main(String[] args) {
        int[] array = {84,83,88,87,61};
        System.out.println("原数组 "+Arrays.toString(array));
        selectSort(array);//调用直接选择排序方法
        System.out.println("直接选择排序后 "+Arrays.toString(array));
 
    }

运行截图如下: 

3.2直接选择排序优化

基本思路如下：

1. 初始化左指针 left 为数组的起始位置，右指针 right 为数组的末尾位置。

2. 在每一轮循环中，首先找到当前未排序区的最小值和最大值的索引，分别用 minIndex 和 maxIndex 记录。

3. 将最小值与未排序区的第一个元素进行交换，将最小值放到已排序区的末尾。

4. 检查最大值的索引是否等于 left，如果是，则更新 maxIndex 为 minIndex，以防止最大值被交换到已排序区的末尾。

5. 将最大值与未排序区的最后一个元素进行交换，将最大值放到已排序区的起始位置。

6. 左指针 left 向右移动一位，右指针 right 向左移动一位，缩小未排序区的范围。

7. 重复步骤2到步骤6，直到未排序区为空，所有元素都被放入已排序区。

举例子解释:

你有一组未排序的数组:84,83,88,87,61

第一次排序:

第二次排序:

完成排序

参考代码如下:

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[maxIndex]) {
                maxIndex = i;
            }
            if (array[i] < array[minIndex]) {
                minIndex = i;
            }
        }
 
        swap(array, minIndex, left); // 将最小值与未排序区的第一个元素交换位置
        if (maxIndex == left) {
            maxIndex = minIndex;
        }
        swap(array, maxIndex, right); // 将最大值与未排序区的最后一个元素交换位置
 
        left++;
        right--;
    }
}
 
 
    public static void main(String[] args) {
        int[] array = {84,83,88,87,61};
        System.out.println("原数组 "+Arrays.toString(array));
        selectSort2(array);//调用方法
        System.out.println("直接选择排序后 "+Arrays.toString(array));
 
    }

运行如下:

z

注意:

优化后的选择排序算法在时间复杂度上与常规的选择排序算法相同，都是O(n^2)，其中n是待排序数组的长度。

无论是常规选择排序还是优化后的选择排序，都包含两层嵌套循环。外层循环用于遍历未排序区域，内层循环用于找到未排序区域的最小值和最大值。在每一次循环中，需要进行一次比较和可能的一次交换操作。

因此，选择排序的时间复杂度始终为O(n^2)，无论是否进行了优化。优化后的选择排序算法只是通过减少交换次数来提高了实际执行的时间，但并没有改变其基本的时间复杂度。

---

3.3堆排序

堆排序特性总结:

1. 不稳定性：堆排序是一种不稳定的排序算法。在构建最大堆和进行堆调整的过程中，元素的相对顺序可能会发生变化。例如，对于具有相同值的元素，它们在最大堆中的相对顺序可能会被调整，导致排序后的结果不稳定。

2. 时间复杂度：堆排序的时间复杂度为O(n log n)，其中n是待排序数组的长度。构建最大堆的过程需要O(n)的时间复杂度，而进行堆调整的过程需要进行n-1次下沉操作，每次下沉的时间复杂度为O(log n)。因此，总体时间复杂度为O(n log n)。

3. 空间复杂度:堆排序算法只需要常数级别的额外空间来存储一些临时变量和指针，如循环索引和临时交换变量。这些额外空间的使用量不随输入规模的增长而增加，因此堆排序的空间复杂度为O(1)。

四.交换排序

4.1冒泡排序

基本思想:通过比较相邻元素的大小并交换它们的位置，使得较大的元素逐渐“冒泡”到数组的末尾。

该图来源:1.1 冒泡排序 | 菜鸟教程 (runoob.com) 

举例子解释:

假设你现在有未排序的代码:5, 3, 8, 2, 1

首先,我们进行第一次排序:

第二次排序:

同理,由此类推可排序完成

参考代码:

public static void bubbleSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        boolean flag = false; // 进行优化，每一趟判断上一趟是否交换
 
        // 比如给的 1 2 3 4 5，走了一遍发现有序，最好的情况下为时间复杂度O(N)
        // 因为在每一趟排序中，最大的元素都会冒泡到末尾，所以下一趟排序可以减少一次遍历
        for (int j = 0; j < array.length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1); // 交换相邻元素的位置
                flag = true; // 标记本趟排序有交换操作
            }
        }
 
        if (!flag) {
            // 如果本趟排序没有交换操作，说明数组已经有序，提前结束排序
            break;
        }
    }
}
 
public static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
 
 
  public static void main(String[] args) {
        int[] array = {5, 3, 8, 2, 1};
        System.out.println("原数组 "+Arrays.toString(array));
        bubbleSort(array);
        System.out.println("冒泡排序后 "+Arrays.toString(array));
 
    }

 运行如下:

 冒泡排序特点:

冒泡排序具有以下特点：

1. 时间复杂度：冒泡排序的平均和最坏情况下的时间复杂度都为 O(n^2)，其中 n 是待排序数组的长度。这是因为每一趟排序需要比较 n-1 个相邻元素，并且需要进行 n-1-i 次遍历，共需要进行 (n-1) + (n-2) + ... + 2 + 1 = n*(n-1)/2 次比较和交换操作。

2. 空间复杂度: 冒泡排序的空间复杂度为 O(1)，即不需要额外的空间来存储数据。因为只需要使用常数级别的额外空间来存储一些临时变量，例如用于交换元素的临时变量。无论待排序数组的规模如何增大，所需的额外空间都保持不变。

3. 稳定性：冒泡排序是一种稳定的排序算法，即相同的元素在排序后的相对顺序保持不变。只有相邻元素的比较和交换操作，不会改变相同元素的相对位置。

4. 最好情况下的时间复杂度：当待排序数组已经有序时，冒泡排序只需进行一趟遍历，没有发生元素交换，时间复杂度为 O(n)，这是冒泡排序的最好情况。

4.2快速排序

4.2.1快递排序Hoare

基本思想:

1. 选择一个基准元素：从待排序的数组中选择一个基准元素。通常情况下，可以选择数组的第一个元素、最后一个元素或者中间元素作为基准。

2. 分区操作：将数组中的其他元素按照与基准元素的大小关系，划分为两个子数组，一个小于基准元素的子数组，一个大于基准元素的子数组。这个过程称为分区操作。

3. 递归排序：对划分得到的两个子数组，分别进行递归调用快速排序算法。即对小于基准元素的子数组和大于基准元素的子数组进行快速排序。

4. 合并结果：将经过排序的子数组合并，得到最终的有序数组。

具体步骤如下:

1. 选择基准元素。
2. 将数组中小于基准元素的元素移到基准元素的左边，大于基准元素的元素移到基准元素的右边。
3. 对基准元素左边的子数组和右边的子数组分别递归调用快速排序算法。
4. 合并排序后的左子数组、基准元素和右子数组。

参考动图:

图片来源:1.6 快速排序 | 菜鸟教程 (runoob.com) 

举例子解释:

初始数组：[5, 2, 9, 1, 7, 6, 3]

第一步：选择基准元素5

第二步：进行分区操作，将小于基准元素的数放在左边，大于基准元素的数放在右边。

 第三步,交换基准元素下标后,基准元素左边和右边分别进行递归操作,重新选择基准元素

第四步:合并排序后的子数组以及基准元素即可

参考代码如下:

public static void quickSort(int[] array) {
    quick(array, 0, array.length - 1);
}
 
private static void quick(int[] array, int start, int end) {
    if (start >= end) {
        return; // 基准条件，如果起始索引大于等于结束索引，则表示数组已经有序，直接返回
    }
 
    int pivot = partitionHoare(array, start, end); // 获取基准元素的位置
 
    quick(array, start, pivot - 1); // 对基准元素左边的子数组进行快速排序
    quick(array, pivot + 1, end); // 对基准元素右边的子数组进行快速排序
}
 
public static int partitionHoare(int[] array, int left, int right) {
    int tmp = array[left]; // 将左边第一个元素作为基准元素
    int i = left;
 
    while (left < right) {
        // 从右边开始找到第一个小于基准元素的元素
        while (left < right && array[right] >= tmp) {
            right--;
        }
 
        // 从左边开始找到第一个大于基准元素的元素
        while (left < right && array[left] <= tmp) {
            left++;
        }
 
        swap(array, left, right); // 交换找到的两个元素的位置
        // 交换之后又符合上面循环的条件了，就又继续执行上面的while循环，直到左右指针相遇
    }
 
    swap(array, i, left); // 将基准元素放到相遇位置，即左指针所在位置
    return left; // 返回基准元素的位置
}
 
private static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
 
 
   public static void main(String[] args) {
        int[] array = {5, 3, 8, 2, 1};
        System.out.println("原数组 "+Arrays.toString(array));
        quickSort(array);//调用快速排序方法
        System.out.println("快速排序后 "+Arrays.toString(array));
 
    }

 运行截图如下:

-

4.2.2快速排序挖坑法

基本思路:通过分治法（Divide and Conquer）来进行排序。其中，挖坑法（Partition）是快速排序的一种常见实现方式。

快速排序挖坑法的步骤：

1. 选择一个基准元素（pivot）。通常情况下，可以选择数组的第一个元素作为基准元素。

2. 定义两个指针，一个指向数组的起始位置（一般为左指针，记为left），一个指向数组的末尾位置（一般为右指针，记为right）。

3. 通过移动指针，将数组中小于基准元素的值放在左侧，大于基准元素的值放在右侧，形成一个“坑”。

4. 交换左指针和右指针所指向的元素，直到左指针和右指针相遇。

5. 将基准元素放入最后一个形成的“坑”中。

6. 通过递归的方式，对左右两个子数组（基准元素左侧和右侧的子数组）进行快速排序。

7. 重复以上步骤，直到所有子数组都有序。

注意:实际上被 '挖' 走的元素不是真的没了,只是把原来的值给覆盖了

第一趟排序:

第二趟排序:

 

往下同理,就不一一展开了

参考代码:

public static void quickSort(int[] array){
    quick(array,0,array.length-1);
}
 
private static void quick(int[] array, int start, int end) {
    // 如果开始索引大于等于结束索引，表示已经完成排序
    if(start >= end) {
        return;
    }
 
    // 找到基准值的位置
    int pivot = partitionHole(array,start,end);
 
    // 对基准值左边的子数组进行快速排序
    quick(array,start,pivot-1);
 
    // 对基准值右边的子数组进行快速排序
    quick(array,pivot+1,end);
}
 
public static int partitionHole(int[] array,int left,int right){
    // 将最左边的元素作为基准值
    int tmp = array[left];
    int i = left;
 
    // 循环直到左指针和右指针相遇
    while (left < right){
        // 移动右指针，找到第一个小于基准值的元素
        while (left < right && array[right]>=tmp){
            right--;
        }
        // 将找到的小于基准值的元素放到左指针所在位置
        array[left] = array[right];
 
        // 移动左指针，找到第一个大于基准值的元素
        while (left < right && array[left]<=tmp){
            left++;
        }
        // 将找到的大于基准值的元素放到右指针所在位置
        array[right] = array[left];
    }
    // 将基准值放到最终的位置
    array[left] = tmp;
    return left;
}
 
  public static void main(String[] args) {
        int[] array = {7,32,1,6,8,5,3,14,4,21};
        System.out.println("原数组 "+Arrays.toString(array));
        quickSort(array);调用方法
        System.out.println("快速(挖坑法)排序后 "+Arrays.toString(array));
 
    }
 

运行截图:

---

4.2.3前后指针法

实现步骤如下:

1. 首先，选择数组的左边第一个元素作为基准值key，并设定两个指针：prev指向左边第一个元素的位置，cur指向prev的后一个位置。

2. 从cur位置开始，逐个将当前元素与基准值key进行比较。如果当前元素arr[cur]小于key，就将prev向后移动一位（prev++），然后交换arr[cur]和arr[prev]的值，确保小于基准值的元素都位于prev的左侧。

3. 当cur指针遍历完整个数组（cur > right）时，结束一趟快速排序。此时，将基准值key与arr[prev]进行交换，将基准值放置到最终位置上。

4. 接着，对基准值左边和右边的子数组分别递归执行上述步骤，直到完成整个数组的排序。

参考动图如下:

代码如下:

import java.util.Arrays;
 
public class QuickSort {
    public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }
 
    private static void quick(int[] array, int start, int end) {
        // 终止条件：子数组长度为0或1时直接返回
        if (start >= end) {
            return;
        }
        
 
        // 使用前后指针法进行划分，获取基准元素的位置
        int pivot = partition(array, start, end);
 
        // 递归地对基准元素左边的子数组进行排序
        quick(array, start, pivot - 1);
        
        // 递归地对基准元素右边的子数组进行排序
        quick(array, pivot + 1, end);
    }
 
    // 前后指针法进行划分
    public static int partition(int[] array, int left, int right) {
        int prev = left;
        int cur = left + 1;
        
        while (cur <= right) {
            // 如果当前元素小于基准值，并且prev指针后移后的元素不等于当前元素，则交换prev指针和cur指针的元素
            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[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
 
 
    public static void main(String[] args) {
        int[] array = {7, 32, 1, 6, 8, 5, 3, 14, 4, 21};
        System.out.println("原数组 " + Arrays.toString(array));
        quickSort(array);
        System.out.println("快速(前后指针法)排序后 " + Arrays.toString(array));
    }
}

运行截图如下:

4.2.4快速排序的两个优化

优化一:三数取中法选key

三数取中法（Median of Three）是快速排序算法中一种用于选择基准元素的方法。在快速排序中，选择合适的基准元素对算法的性能起着重要的作用。

三数取中法的思想是从待排序数组的开始、中间和末尾位置选择三个元素，然后取这三个元素的中间值作为基准元素。通过选择中间值作为基准元素，可以尽量保证基准元素接近数组的中间值，从而更好地平衡划分,能够解有效决树的高度的问题，但是无法解决栈溢出的问题。

使用三数取中法的步骤如下：

1. 找到待排序数组的开始、中间和末尾位置的索引：start、mid、end。
2. 比较数组中这三个位置的元素大小，并将它们排序，确保 array[start] <= array[mid] <= array[end]。
3. 返回中间位置的元素作为基准元素。

参考代码如下:

public  static int middleNum(int[] array,int left,int right){
        int mid = (left + right) / 2;
        if(array[left] < array[right]){//比如 array[left] = 3, array[right] =9
            if(array[mid] < array[left]){//已知两数的大小关系，中位数有三种情况
                return left;
            }else if(array[mid] > array[right]){
                return  right;
            }else{
 
                return  mid;
            }
        }
        else{//比如 array[left] = 9, array[right] = 3
            if(array[mid] < array[right]){
                return right;
            }else if(array[mid] > array[left]){
                return left;
            }else {
                return mid;
            }
 
        }
 
    }

优化二:递归到小的子区间时，可以考虑使用插入排序

当一组数组经过几趟排序后，后面的数据越来越趋于有序，后面的数据可以使用插入法，加快速度,省下递归的次数。
而对于一颗二叉树而言，往往最后面两层的结点数是最多的，所以能省下下很多的递归次数。

参考代码:2.1直接插入排序

---

运用两个以上优化的代码
 

 public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
 
    private static void quick(int[] array, int start, int end) {
        if(start >= end) {
            return;
        }
 
        //-----------------------------------------------------------
        //优化二
        //经过几趟排序后，后面的数据越来越趋于有序，后面的数据可以使用插入法，加快速度,省下递归的次数
        //对于一颗二叉树而言，往往最后面两层的结点数是最多的，所以能省下下很多的递归次数
        if(end - start+1<=15){
            quickInsertSort(array,start,end);//后面直接使用插入
            return;//返回，后面的不用在执行了
        }
 
        //-----------------------------------------------------------
 
 
        //-----------------------------------------------------------
        //优化一 -> 三数选中法
        int index = middleNum(array,start,end);//获得中位数下标
        swap(array,index,start);//和基数值交换
        //-----------------------------------------------------------
 
        int pivot = partition(array,start,end);//该方法使用前后指针法
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
 
 
 
//直接插入法:
 public static void quickInsertSort(int[] array,int left,int right){
        for(int i = left+1;i<=right;i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= left; j--) {
                if (tmp < array[j]) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
 
        }
    }
 
 
 
//三数取中法:
public  static int middleNum(int[] array,int left,int right){
        int mid = (left + right) / 2;
        if(array[left] < array[right]){//比如 array[left] = 3, array[right] =9
            if(array[mid] < array[left]){//已知两数的大小关系，中位数有三种情况
                return left;
            }else if(array[mid] > array[right]){
                return  right;
            }else{
 
                return  mid;
            }
        }
        else{//比如 array[left] = 9, array[right] = 3
            if(array[mid] < array[right]){
                return right;
            }else if(array[mid] > array[left]){
                return left;
            }else {
                return mid;
            }
 
        }
 
    }
 
//前后指针法
    public 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 main(String[] args) {
        int[] array = {7,32,1,6,8,5,3,14,4,21};
        System.out.println("原数组 "+Arrays.toString(array));
        quickSort(array);//调用方法
        System.out.println("快速(前后指针法)＋优化排序后 "+Arrays.toString(array));
 
    }

运行截图如下:

---

4.2.5快速排序非递归

基本原理:使用栈模拟快速排序时，我们可以把栈看作是一个待处理的任务列表。每个任务表示一个待排序的子数组范围。

1. 我们首先将整个数组的起始索引和结束索引作为第一个任务入栈。

2.进入循环，直到栈为空为止：

•     从栈中弹出一个任务，表示要处理的子数组范围。
•     在这个范围内选择一个基准元素，并将数组进行分区，将小于等于基准的元素放在左边，大于基准的元素放在右边。
•     如果基准的左侧还有未排序的元素，我们将左侧子数组的起始索引和结束索引作为一个新任务入栈。
•    如果基准的右侧还有未排序的元素，我们将右侧子数组的起始索引和结束索引作为一个新任务入栈。

3.循环结束后，整个数组就完成了排序。

通过使用栈来存储待处理的任务，我们可以模拟递归的过程，但是避免了函数调用的开销。这样，我们就能以非递归的方式实现快速排序算法。

下面举出视频解释

• start作为数组首位置,end作为数组末位置
• 按照使用快速排序挖坑法,先去left下标的元素作为privot的基准值
• left寻找比privot的较大值,right寻找比privot的较小值,找到后交换,直至相遇.
• 相遇之后,分别左子组和右子组的首尾元素的下标放到栈上
• 判断栈是否为空,不为空,出栈两个下标,第一个的出栈作为right的新下标,第二个出栈的作为left的新下标
• 之后按如上步骤进行

注意:子组的长度要大于1,否则索引不用放入到栈中

1.

2.

参考代码如下:

public static void quickSortNor(int[] array){
    int start = 0;
    int end = array.length - 1;
    Stack<Integer> stack = new Stack<>();
    int pivot = partitionHole(array, start, end);  // 使用挖坑法进行分区，得到基准位置
 
    // 将初始任务入栈，即整个数组的起始索引和结束索引
    if (pivot > start + 1) {
        stack.push(start);
        stack.push(pivot - 1);
    }
    if (pivot + 1 < end) {
        stack.push(pivot + 1);
        stack.push(end);
    }
 
    // 循环处理栈中的任务，直到栈为空
    while (!stack.isEmpty()) {
        end = stack.pop();
        start = stack.pop();
        pivot = partitionHole(array, start, end);  // 使用挖坑法进行分区，得到基准位置
 
        // 将子数组的起始索引和结束索引入栈，以便后续处理
        if (pivot > start + 1) {
            stack.push(start);
            stack.push(pivot - 1);
        }
        if (pivot + 1 < end) {
            stack.push(pivot + 1);
            stack.push(end);
        }
    }
}
 
/**
 * 使用挖坑法进行分区
 */
public static int partitionHole(int[] array, int left, int right) {
    int tmp = array[left];
    int i = left;
 
    while (left < right) {
        // 从右侧开始，找到第一个小于基准的元素
        while (left < right && array[right] >= tmp) {
            right--;
        }
        array[left] = array[right];  // 将找到的元素填入左侧的坑位
 
        // 从左侧开始，找到第一个大于基准的元素
        while (left < right && array[left] <= tmp) {
            left++;
        }
        array[right] = array[left];  // 将找到的元素填入右侧的坑位
    }
 
    array[left] = tmp;  // 将基准元素放入最终的坑位
    return left;  // 返回基准位置
}
 
public static void main(String[] args) {
    int[] array = {6,1,2,7,9,3,4,5,10,8}};
    System.out.println("原数组 " + Arrays.toString(array));
    quickSortNor(array);
    System.out.println("快速(非递归)＋优化排序后 " + Arrays.toString(array));
}

运行截图如下:

快速排序是一种常用的排序算法，具有以下特性：

• 时间复杂度：平均情况下，快速排序的时间复杂度为O(nlogn)，其中n是待排序数组的长度。最坏情况下，当选择的基准元素不平衡时（例如已有序数组作为输入），时间复杂度可达到O(n^2)。但通过优化算法和随机选择基准元素，可以大大降低最坏情况出现的概率。
• 不稳定排序：快速排序是一种不稳定的排序算法，意味着相等元素的相对顺序在排序后可能会发生改变。

• 分治算法：快速排序使用分治算法的思想，将原始数组分割为较小的子数组，然后分别对子数组进行排序，最后将排序好的子数组进行合并，以达到整个数组有序的目的。

• 递归实现：通常情况下，快速排序使用递归来实现，通过不断地递归调用自身来处理子数组。每次递归调用将数组分为两部分，直到子数组的长度为1或0时停止递归。
• 优化方法：为了提高快速排序的性能，可以采取一些优化方法，如随机选择基准元素、三数取中法选择基准元素、使用插入排序优化小规模子数组等。

快速排序的空间复杂度主要取决于递归调用的栈空间和额外的辅助空间

• 栈空间：在递归实现的快速排序中，每次递归调用都会将一部分数组分割为子数组，并将子数组的起始索引和结束索引入栈。这些递归调用需要使用栈来保存函数调用的上下文信息，包括参数、局部变量和返回地址等。因此，快速排序的空间复杂度取决于递归调用的深度，即递归树的高度。在最坏情况下，递归树的高度可以达到O(n)，因此快速排序的最坏空间复杂度为O(n)。
• 辅助空间：快速排序通常需要一些额外的辅助空间来进行分区操作。常见的方法是选择一个基准元素，并将小于等于基准的元素放在左侧，大于基准的元素放在右侧。这个过程需要使用额外的空间来存储临时变量、交换元素等操作。因此，快速排序的辅助空间复杂度为O(logn)，取决于递归调用的深度。

总结起来，快速排序是一种高效的排序算法，具有原地排序、分治算法、平均时间复杂度为O(nlogn)等特性。然而，最坏情况下的时间复杂度为O(n^2)，且为不稳定排序算法。通过优化方法可以提高快速排序的效率和稳定性。

4.3归并排序

归并排序（Merge Sort）是一种常用的排序算法，它基于分治（Divide and Conquer）的思想，将一个大问题分解为若干个小问题，然后将小问题的解合并起来得到整体的解。归并排序的主要步骤包括分解、合并和排序。

以下是归并排序的一般实现步骤：

1. 分解：将待排序的数组递归地分解为两个子数组，直到子数组的长度为1或0时停止递归。

2. 合并：将两个有序的子数组合并成一个有序的数组。合并过程中需要创建一个临时数组来存储合并结果。

3. 排序：通过不断地递归调用分解和合并步骤，将子数组排序并合并，直到最终得到完整的有序数组。

参考动图:1.5 归并排序 | 菜鸟教程 (runoob.com)

参考图:

参考代码:

public static void mergeSort(int[] array) {
    mergeSortFun(array, 0, array.length - 1);
}
 
private static void mergeSortFun(int[] array, int start, int end) {
    if (start >= end) {
        return; // 如果起始索引大于等于结束索引，表示子数组长度为1或0，不需要排序，直接返回
    }
    int mid = (start + end) / 2; // 计算中间索引，将数组分为两部分
    mergeSortFun(array, start, mid); // 对左半部分进行归并排序
    mergeSortFun(array, mid + 1, end); // 对右半部分进行归并排序
    merge(array, start, mid, end); // 合并左右两部分
}
 
private static void merge(int[] array, int left, int mid, int right) {
    int s1 = left; // 左半部分的起始索引
    int e1 = mid; // 左半部分的结束索引
    int s2 = mid + 1; // 右半部分的起始索引
    int e2 = right; // 右半部分的结束索引
 
    // 定义一个新数组来存储合并结果
    int[] tmpArr = new int[right - left + 1];
    int k = 0; // tmpArr的下标
 
    // 同时满足条件时，证明两个归并段都还有数据
    while (s1 <= e1 && s2 <= e2) {
        if (array[s1] <= array[s2]) {
            tmpArr[k++] = array[s1++]; // 将左半部分的元素放入tmpArr，并移动相应索引
        } else {
            tmpArr[k++] = array[s2++]; // 将右半部分的元素放入tmpArr，并移动相应索引
        }
    }
 
    // 处理剩余的元素，若左半部分还有剩余，则将剩余元素放入tmpArr
    while (s1 <= e1) {
        tmpArr[k++] = array[s1++];
    }
 
    // 处理剩余的元素，若右半部分还有剩余，则将剩余元素放入tmpArr
    while (s2 <= e2) {
        tmpArr[k++] = array[s2++];
    }
 
    // 将排好序的tmpArr中的元素拷贝回原始数组array中
    for (int i = 0; i < tmpArr.length; i++) {
        array[i + left] = tmpArr[i]; // 注意需要加上偏移量left
    }
}
 
//该段代码用非递归的方式,了解即可.
   //非递归归并
    public static void mergeSortNor(int[] array){
        int gap = 1;
        while (gap < array.length){
            //循环一个,两个,四个,八个...开始
            for (int i = 0; i < array.length; i+=gap*2) {
                int left = i;
                int mid = left + gap - 1; // 有可能会越界
                //比如有五个元素 ，最后一个元素下标为4，即left = 4,mid = 4+2-1 = 5
                int right = mid+gap;// 有可能会越界,同理
                if(mid >= array.length){//如果越界，就把元素归还最后一个下标
                    mid = array.length-1;
                }
                if(right >= array.length){
                    right = array.length-1;
                }
                merge(array,left,mid,right);
 
            }
            gap*=2;
        }
    }
 
public static void main(String[] args) {
        int[] array = {6,1,2,7,9,3,4,5,10,8};
        System.out.println("原数组 "+Arrays.toString(array));
        mergeSort(array);
        System.out.println("快速(前后指针法)＋优化排序后 "+Arrays.toString(array));
 
    }
 

运行截图如下:

归并排序的特点可以总结如下：

• 稳定性：归并排序是一种稳定的排序算法，即相等元素的相对顺序在排序后保持不变。
• 分治思想：归并排序使用分治策略，将原始数组分解为较小的子数组，然后分别对子数组进行排序，最后将排序好的子数组合并成一个有序数组。
• 时间复杂度：归并排序的时间复杂度是O(n log n)，其中n是数组的长度。这是一种较为高效的排序算法，尤其适用于大规模数据的排序。
• 空间复杂度：归并排序需要额外的空间来存储临时数组，其空间复杂度为O(n)，其中n是数组的长度。这使得归并排序在对大规模数据进行排序时可能需要较多的内存空间。
•  适用性：归并排序对各种数据类型都适用，并且对于链式存储结构也可以进行排序。由于归并排序的稳定性和可预测的性能，它在实际应用中被广泛使用。
• 缺点：归并排序需要额外的空间来存储临时数组，这增加了空间复杂度。此外，在实现时需要涉及到递归操作，可能会导致函数调用的开销。

总之，归并排序是一种高效且稳定的排序算法，适用于各种数据类型。它的主要思想是分治，通过将数组分解为较小的子数组并递归地排序和合并，最终得到完整的有序数组。

1.  先把文件切分成 200 份，每个 512 M
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了

五.其他排序

除了上面提到的排序,还可以了解其他的排序.

计数排序:计数排序 - 知乎 (zhihu.com)

基数排序:1.10 基数排序 | 菜鸟教程 (runoob.com)

桶排序:【排序】图解桶排序_桶排序图解-CSDN博客

结语:

总的来说，选择合适的排序算法取决于待排序数据的规模、特性以及排序的要求。在实际应用中，我们需要根据具体情况选择合适的算法，以获得最佳的排序性能。

通过了解和掌握不同的排序算法，我们可以更好地理解数据结构的基础原理，并在实际开发中选择最合适的排序方法。希望本文对您在数据结构排序方面的学习和实践有所帮助。

感谢您阅读本文，如果您有任何问题或意见，请随时在评论区分享。