数据结构十大排序之（冒泡，快排，并归）

接上期：

数据结十大排序之（选排，希尔，插排，堆排）-CSDN博客

前言：

在计算机科学中，排序算法是最基础且最重要的算法之一。无论是大规模数据处理还是日常的小型程序开发，排序算法的效率直接影响到系统的性能表现。因此，了解和掌握常见的排序算法，对于每一个程序员来说，都具有重要的意义。

本文将对三种经典的排序算法——冒泡排序、快速排序和归并排序进行深入剖析。这三种算法在不同的应用场景下各有优势，分别代表了排序算法的不同发展阶段。从简单直观的冒泡排序到高效且复杂的快速排序，再到稳定且适用于大数据量的归并排序，我们将一一解析它们的工作原理、时间复杂度以及实际应用中的优缺点。通过本文的学习，读者不仅能够掌握这些排序算法的基本概念，还能更好地理解在特定问题中选择合适排序算法的重要性。

无论你是算法学习的初学者，还是在进行系统优化的开发者，相信本文都会为你提供有价值的参考。接下来，我们将逐一揭开这些经典排序算法的神秘面纱。

4 交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特 点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

4.1 冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复地遍历排序的元素，比较相邻的元素并交换它们的位置，直到整个数组排序。冒泡排序的核心思想是通过元素之间的交换，将较大的元素“冒泡”到磁盘的终止，较小的元素“沉淀”到磁盘的迁移，最终达到排序的目的。

原理

冒泡排序的核心思想是：

1. 从队列的开始位置，依次比较相邻的两个元素。
2. 如果这两个元素的顺序不正确（例如，前一个元素大于后一个元素），就交换它们的位置。
3. 每一个批次结束后，工厂的部分都会放置当前轮次中最大的元素。换句话说，更大的元素会“冒泡”到批次的终止。
4. 每一个遍历减少比较的元素个数，因为遍历的元素已经是排序好了。

算法步骤

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3. 针对所有的元素重复以上的步骤，除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

private static void BubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}

• 外层循环( for (int i = 0; i < arr.length - 1; i++)):

  • 这个循环的作用是控制冒泡排序的遍历次数。每次遍历结束后，最大的元素就被“冒泡”到队列的最后面。因此，随着排序的进行，内层可以循环最少遍历一些元素。arr.length - 1次次遍历足够了，因为仓库最后一个元素自然会排到正确的位置。

• 内层循环( for (int j = 0; j < arr.length - 1 - i; j++)):

  • 内层循环负责获取当前未排序部分的各个元素，进行比较和交换。每次内层循环将未排序部分的最大元素推到队列的最后（该部分会被外层循环控制，不再被内层循环控制）层循环处理）。
  • 注意：arr.length - 1 - i控制了内层循环的长度。随着外层循环的进行，内层循环每次遍历的范围逐渐减小，因为已排序的元素不再参与比较。

• 比较与交换( if (arr[j] > arr[j + 1])):

  • 如果当前元素arr[j]大于其后面的元素arr[j + 1]，则交换它们的位置。这样增加，新增的元素被“冒泡”到了队列的后面。

静态展示：

假设我们有一个仓库[5, 2, 9, 1, 5, 6]，使用冒泡排序进行排序：

1. 初始数组：[5, 2, 9, 1, 5, 6]
2. 第一轮（i = 0）：
   • 比较5和2，交换位置：[2, 5, 9, 1, 5, 6]
   • 相比之下5，9不交换
   • 比较9和1，交换位置：[2, 5, 1, 9, 5, 6]
   • 比较9和5，交换位置：[2, 5, 1, 5, 9, 6]
   • 比较9和6，交换位置：[2, 5, 1, 5, 6, 9]
   • 第一次运输结束，最大的元素9已经搬运的搬运。
3. 第二轮（i = 1）：
   • 相比之下2，5不交换
   • 比较5和1，交换位置：[2, 1, 5, 5, 6, 9]
   • 相比之下5，5不交换
   • 相比之下5，6不交换
   • 第二次运输结束，最大的元素6已经搬运货物的支架。
4. 第三轮（i = 2）：
   • 比较2和1，交换位置：[1, 2, 5, 5, 6, 9]
   • 相比之下2，5不交换
   • 相比之下5，5不交换
   • 第三次旅程结束，最大的元素5已经搬运的搬运的。
5. 第四轮（i = 3）：
   • 相比之下2，1不交换
   • 由于没有进行任何交换，提前退出循环，排序结束。

最终数组为：[1, 2, 5, 5, 6, 9]。

时间复杂度

• 最坏情况时间复杂度：O(n²)，当集群完全逆序时，冒泡排序需要进行n-1次轮巡，每轮遍历中需要进行n-1次比较和交换，因此总的时间复杂度为 O(n²)。

• 最好情况时间复杂度：O(n)，当阵列已经是集群的情况下，冒泡排序只需要进行一次遍历，不发生交换，算法会提前终止。因此，最好情况下的时间复杂度是 O(n)。

• 平均情况时间复杂度：O(n²)，大多数情况下，冒泡排序的时间复杂度为O(n²)，因为每次遍历都需要比较和交换。

空间复杂度

因此冒泡排序是原地排序算法，它只需要升级的额外空间来交换元素，空间复杂度为O(1)。

稳定性

冒泡排序是稳定的。在满足元素的情况下，冒泡排序不会改变它们的相对顺序。这是因为当两个元素一致时，冒泡排序不会进行交换操作。

优缺点

优点：

• 实现简单：冒泡排序的实现非常简单，代码量少，容易理解。
• 稳定排序：它是一个稳定的排序算法，相同元素的相对顺序不会改变。
• 空间复杂度低：冒泡排序是原地排序算法，空间复杂度为O(1)，不需要额外的内存空间。

缺点：

• 效率低：冒泡排序的时间复杂度是O(n²)，对于大规模数据，效率非常低。
• 不适用于大规模数据排序：由于其时间复杂度较高，因此大规模数据时性能不如其他排序处理算法，如排序、归并排序等。
• 改进空间有限：虽然可以通过设置标志位优化提前退出，但在实际应用中，它仍然比其他更高效的排序算法要慢。

适用场景

• 小规模数据排序：由于冒泡排序的时间复杂度较高，它适用于数据量较小的排序任务。
• 教学和演示：其算法简单易懂，冒泡排序常用于教学和排序算法的基本原理。
• 已经部分小区的情况：如果阵列接近小​​区，冒泡排序会比其他复杂的排序算法（如快速排序、归并排序等）获得优势，因为它可以通过优化提前结束。

4.2 快排

快速排序（Quick Sort）是一种非常的排序算法，由计算机科学家高效托尼·霍尔（Tony Hoare）于 1960 年提出。它采用了分治法的思想，通过将一个大问题分解为几个小问题来解决。快速排序基本思想是：通过一个“基准”元素将待排序数据分为两个部分，使得一部分数据都比基准小，另一部分数据都比基准大，然后梯度地对这两部分分别进行排序。

原理

快速排序的核心思想是分治法，即通过选择一个“基准元素”将队列分成两部分：

1. 选择基准元素：从仓库中选择一个元素作为基准元素（可以选择第一个元素、最后一个元素、中间元素或者随机选择）。
2. 分区操作：通过一个排序趟将流量分成两个部分，左边部分的元素小于基准元素，右边部分的元素大于基准元素。基准元素末端位于其正确的位置。
3. 梯度排序：梯度地对基准元素左边和右边的子队列进行快速排序。

算法步骤

4.2.1递归版

1. 选择基准元素：从集群中选择一个基准元素，常见的策略有：
   • 选择第一个元素作为基准。
   • 选择最后一个元素作为基准。
   • 选择中间元素作为基准。
   • 随机选择一个元素作为基准。
2. 操作：检索西藏，将比基准小元素移到左边，比基准大的元素移到右边，最终将基准元素移到正确的位置。
3. 梯度排序：分别对左子队列和右子队列进行快速排序。

4.2.1.1 霍尔（Tony Hoare）法

private static void QuickSort(int[] arr) {
    int left = 0;
    int right = arr.length - 1;
    MyQuickSort(arr, left, right);
}

private static void MyQuickSort(int[] arr, int left, int right) {
    if (left < right) {
        int div = partition(arr, left, right);  // 获取分区后的基准元素位置
        MyQuickSort(arr, left, div - 1);   // 对基准元素左边的子数组进行排序
        MyQuickSort(arr, div + 1, right);  // 对基准元素右边的子数组进行排序
    }
}

private static int partition(int[] arr, int left, int right) {
    int i = left;
    int j = right;
    int pivot = arr[left];  // 选择基准元素为第一个元素
    while (i < j) {
        while (arr[j] >= pivot && i < j) {  // 向左找到比基准元素小的元素
            j--;
        }
        while (arr[i] <= pivot && i < j) {  // 向右找到比基准元素大的元素
            i++;
        }
        swap(arr, i, j);  // 交换
    }
    swap(arr, i, left);  // 将基准元素放到正确的位置
    return i;  // 返回基准元素的最终位置
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

QuickSort方法 

作用：这是QuickSort的入口方法，初始化了两个指针left和right，并调用MyQuickSort方法来进行排序。left是数组的开始索引，right是数组的结束索引。

MyQuickSort方法

• 分层终止条件：if (left < right)检查了当前子队列的大小。如果left>= right，说明该部分队列只有一个元素或没有元素，结束递归。

• 分区操作：partition方法是返回基准元素的末端位置div，该位置右侧的元素都小于基准元素，右侧的元素都大于基准元素。然后分区地对左侧和右侧的子队列进行排序。

partition方法

• 选择基准元素：pivot被选择为队列的第一个元素（arr[left]）。快速排序的一个特点是每次选择一个基准元素，通常有多种选择方式：第一个元素、最后一个元素、随机元素或者三个数取中法。这里选择了第一个元素作为基准元素。

• 双指针法：i从左边开始，j从右边开始，找到一个大于基准元素的arr[i]和小于基准元素的arr[j]，并交换它们的位置，直到i和j相遇。

• 交换基准元素：当i和j相遇时，交换基准元素和当前i的位置，将基准元素放到正确的位置。

• 返回元素位置：返回值是i，即基准元素末端的位置。此时，基准元素左边的元素都比它小，右边的元素都比它大。

静态展示

假设我们有一个数组[10, 7, 8, 9, 1, 5]，使用快速排序进行排序：

1. 初始数组：[10, 7, 8, 9, 1, 5]

2. 第一轮分区操作：

   • 作为5第一个基准。
   • 将小于5的元素放置在左边，大于5的元素放置在右边，最终[1, 7, 8, 9, 10, 5]元素5放置在正确的位置。
   • 基准要素5的位置是4，此时左子副本为[1]，右子副本为[7, 8, 9, 10]。

3. 队列对左子队列[1]进行排序，由于只有一个元素，排序结束。

4. 梯度对右子队列[7, 8, 9, 10]进行排序：

   • 作为10第一个基准。
   • 分区操作后，重新安装[7, 8, 9, 10]，基准元素10被放置在正确的位置。
   • 基准要素10的位置是3，此时左子副本为[7, 8, 9]，右子副本为空。

5. 层次对子吞吐量[7, 8, 9]进行排序：

   • 作为9第一个基准。
   • 分区操作后，重新安装[7, 8, 9]，基准元素9被放置在正确的位置。
   • 基准要素9的位置是2，此时左子副本为[7, 8]，右子副本为空。

6. 层次对子吞吐量[7, 8]进行排序：

   • 作为8第一个基准。
   • 分区操作后，重新安装[7, 8]，基准元素8被放置在正确的位置。
   • 基准要素8的位置是1，此时左子副本为[7]，右子副本为空。

排序最终的后端为[1, 5, 7, 8, 9, 10]。

4.2.1.2. 挖坑法

private static void QuickSort(int[] arr) {
    int left = 0;
    int right = arr.length - 1;
    MyQuickSort(arr, left, right);
}

private static void MyQuickSort(int[] arr, int left, int right) {
    if (left < right) {
        int div = partition(arr, left, right);  // 获取分区后的基准元素位置
        MyQuickSort(arr, left, div - 1);   // 对基准元素左边的子数组进行排序
        MyQuickSort(arr, div + 1, right);  // 对基准元素右边的子数组进行排序
    }
}

private static int partion(int[] arr, int left, int right) {
    int i = left;
    int j = right;
    int pivot = arr[left];  // 选择基准元素为第一个元素
    while (i < j) {
        // 向右扫描，找到小于基准元素的元素
        while (arr[j] >= pivot && i < j) {
            j--;
        }
        arr[i] = arr[j];  // 把小于基准元素的元素移动到左侧

        // 向左扫描，找到大于基准元素的元素
        while (arr[i] <= pivot && i < j) {
            i++;
        }
        arr[j] = arr[i];  // 把大于基准元素的元素移动到右侧
    }
    arr[i] = pivot;  // 将基准元素放置到正确的位置
    return i;  // 返回基准元素的位置
}

QuickSort方法 

作用：这是QuickSort的入口方法，初始化了两个指针left和right，并调用MyQuickSort方法来进行排序。left是数组的开始索引，right是数组的结束索引。

MyQuickSort方法

• 分层终止条件：if (left < right)检查了当前子队列的大小。如果left>= right，说明该部分队列只有一个元素或没有元素，结束递归。

• 分区操作：partition方法是返回基准元素的末端位置div，该位置右侧的元素都小于基准元素，右侧的元素都大于基准元素。然后分区地对左侧和右侧的子队列进行排序。

partition方法 

• 作用：partition 方法的目标是通过选择一个基准元素（pivot）并将其放置在正确的位置，来将数组分为两部分：一部分小于基准元素，另一部分大于基准元素。
• 步骤：
  1. 初始化：选择 arr[left] 作为基准元素 pivot。
  2. 双指针扫描：
     • 使用两个指针 i 和 j，分别从数组两端向中间扫描。
     • 右扫描：指针 j 向左扫描，找到一个小于基准元素的元素。
     • 左扫描：指针 i 向右扫描，找到一个大于基准元素的元素。
     • 如果指针 i 小于指针 j，则交换 arr[i] 和 arr[j]，直到两个指针交错。
  3. 交换基准元素：当 i 和 j 相遇时，将基准元素 pivot 放置在正确的位置，即 arr[i]，这样基准元素左侧的所有元素都小于它，右侧的所有元素都大于它。
  4. 返回基准元素的位置：返回基准元素的位置 i，供递归调用进一步分区。

静态展示

初始数组：

[10, 7, 8, 9, 1, 5]

第一轮分区操作：

选择数组的第一个元素 5 作为基准元素（pivot）。

• 步骤：

  • 设置两个指针 i 和 j，i 从左边开始，j 从右边开始。
  • 首先，j 指针向左移动，找到小于 5 的元素 1。
  • 然后，i 指针向右移动，找到大于 5 的元素 10。
  • 交换 i 和 j 指针指向的元素，交换 10 和 1，得到数组：

    [1, 7, 8, 9, 10, 5]
    

  • 继续移动指针，重复上述步骤，直到 i 和 j 相遇。
  • 最终，基准元素 5 被放置在正确的位置，即索引 4。

• 数组变更：

  [1, 7, 8, 9, 10, 5]
  

• 分区结果：

  • 基准元素 5 放置在索引 4，此时数组分为两个部分：
    • 左子数组 [1]
    • 右子数组 [7, 8, 9, 10]

对左子数组 [1] 进行排序：

左子数组只有一个元素 [1]，已经是有序的，因此不需要进一步排序。

对右子数组 [7, 8, 9, 10] 进行排序：

选择 10 作为基准元素。

• 步骤：

  • 设置 i 和 j，i 从左边开始，j 从右边开始。
  • 首先，j 指针向左移动，找到小于 10 的元素 9。
  • 然后，i 指针向右移动，找到大于 10 的元素（没有）。
  • 交换 i 和 j 指针指向的元素，基准元素 10 被放置在正确位置，数组保持不变。
  • 结果：

    [7, 8, 9, 10]
    

• 数组变更：

  [7, 8, 9, 10]
  

• 分区结果：

  • 基准元素 10 放置在索引 3，此时数组分为两个部分：
    • 左子数组 [7, 8, 9]
    • 右子数组 []（为空）

对子数组 [7, 8, 9] 进行排序：

选择 9 作为基准元素。

• 步骤：

  • 设置 i 和 j，i 从左边开始，j 从右边开始。
  • 首先，j 指针向左移动，找到小于 9 的元素 8。
  • 然后，i 指针向右移动，找到大于 9 的元素（没有）。
  • 交换 i 和 j 指针指向的元素，基准元素 9 被放置在正确位置，数组保持不变。
  • 结果：

    [7, 8, 9]
    

• 数组变更：

  [7, 8, 9]
  

• 分区结果：

  • 基准元素 9 放置在索引 2，此时数组分为两个部分：
    • 左子数组 [7, 8]
    • 右子数组 []（为空）

对子数组 [7, 8] 进行排序：

选择 8 作为基准元素。

• 步骤：

  • 设置 i 和 j，i 从左边开始，j 从右边开始。
  • i 和 j 都指向元素 7 和 8，没有交换的必要。
  • 基准元素 8 放置在正确位置，数组保持不变。

• 数组变更：

  [7, 8]
  

• 分区结果：

  • 基准元素 8 放置在索引 1，此时数组分为两个部分：
    • 左子数组 [7]
    • 右子数组 []（为空）

排序完成后的数组：

最终的有序数组是：

[1, 5, 7, 8, 9, 10]

4.2.1.3.左右指针法

private static void QuickSort(int[] arr) {
    int left = 0;
    int right = arr.length - 1;
    MyQuickSort(arr, left, right);
}

private static void MyQuickSort(int[] arr, int left, int right) {
    if (left < right) {
        int div = partition(arr, left, right);  // 获取分区后的基准元素位置
        MyQuickSort(arr, left, div - 1);   // 对基准元素左边的子数组进行排序
        MyQuickSort(arr, div + 1, right);  // 对基准元素右边的子数组进行排序
    }
}

private static int partion(int[] arr, int left, int right) {
    int prev = left;
   int cur = left + 1;
   while (cur <= right) {
       if(arr[cur] < arr[prev]) {
           swap(arr,prev,cur);
       }
       cur++;
   }
   swap(arr,prev,left);
    return prev;
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

QuickSort方法 

作用：这是QuickSort的入口方法，初始化了两个指针left和right，并调用MyQuickSort方法来进行排序。left是数组的开始索引，right是数组的结束索引。

MyQuickSort方法

• 分层终止条件：if (left < right)检查了当前子队列的大小。如果left>= right，说明该部分队列只有一个元素或没有元素，结束递归。

• 分区操作：partition方法是返回基准元素的末端位置div，该位置右侧的元素都小于基准元素，右侧的元素都大于基准元素。然后分区地对左侧和右侧的子队列进行排序。

partition方法

• partition 方法是快速排序中的核心部分，用来对数组进行分区，并返回基准元素的位置。
• 这里选择了 arr[left] 作为基准元素（prev）。
• prev 指向基准元素的位置，cur 从 prev + 1 开始，扫描数组：
  • 如果 arr[cur] 小于基准元素 arr[prev]，则交换 arr[prev] 和 arr[cur]，使得比基准元素小的元素移到左边。
  • cur 继续向右扫描，直到扫描完整个数组。
• 在扫描完成后，交换 arr[prev] 和基准元素位置 arr[left]，将基准元素放置到正确的位置。
• 最后，返回 prev，即基准元素的位置。

 静态展示

假设我们有数组 [10, 7, 8, 9, 1, 5]，我们将逐步展示排序过程：

1. 初始数组：[10, 7, 8, 9, 1, 5]

2. 第一次分区：

   • 选择基准元素：pivot = 10

   • 扫描过程中，交换了元素，使得数组变为：[5, 7, 8, 9, 1, 10]

   • 基准元素 10 被放置在正确位置，基准位置返回 5

   • 左子数组：[5, 7, 8, 9, 1]，右子数组：[]

3. 左子数组排序 [5, 7, 8, 9, 1]：

   选择基准元素：pivot = 5

   • 扫描过程中，交换了元素，使得数组变为：[1, 7, 8, 9, 5]

   • 基准元素 5 被放置在正确位置，基准位置返回 0

   • 左子数组：[1]，右子数组：[7, 8, 9]

4. 左子数组 [1] 排序：

   • 只有一个元素，排序结束。

5. 右子数组 [7, 8, 9] 排序：

   选择基准元素：pivot = 7

   • 扫描过程中，交换了元素，使得数组变为：[7, 8, 9]

   • 基准元素 7 被放置在正确位置，基准位置返回 1

   • 左子数组：[]，右子数组：[8, 9]

6. 右子数组 [8, 9] 排序：

   • 选择基准元素：pivot = 8
   • 基准元素 8 被放置在正确位置，排序结束。

7. 最终结果：

   • 排序完成后，数组为：[1, 5, 7, 8, 9, 10]

4.2.2 非递归版

public static void quickNor(int[] array) {
    int start = 0;
    int end = array.length-1;
    Deque<Integer> stack = new ArrayDeque<>();
    int pivot = partion(array,start,end);
    if(pivot > start + 1) {
        stack.push(start);
        stack.push(pivot-1);
    }
    if(pivot < end-1) {
        stack.push(pivot+1);
        stack.push(end);
    }
    while (!stack.isEmpty()) {
        end = stack.pop();
        start = stack.pop();
        pivot = partion(array,start,end);
        if(pivot > start + 1) {
            stack.push(start);
            stack.push(pivot-1);
        }
        if(pivot < end-1) {  
            stack.push(pivot+1);
            stack.push(end);
        }
    }
}

private static int partion(int[] arr, int left, int right) {
    int i = left;
    int j = right;
  int pivot = arr[left];
  while (i < j) {
      while (arr[j] >= pivot && i < j) {
          j--;
      }
      while (arr[i] <= pivot && i < j) {
          i++;
      }
      swap(arr,i,j);
  }
  swap(arr,i,left);
  return i;
}

private static void swap(int[] arr, int i, int j) {

        int temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

}

该代码包含两个主要部分：

1. quickNor：快速排序的非递归实现。
2. partition：分区操作，用于将数组分成两个子数组，并返回基准元素的最终位置。

quickNor 方法分析

public static void quickNor(int[] array) {
    int start = 0;
    int end = array.length - 1;
    Deque<Integer> stack = new ArrayDeque<>();
    int pivot = partion(array, start, end);
    if (pivot > start + 1) {
        stack.push(start);
        stack.push(pivot - 1);
    }
    if (pivot < end - 1) {
        stack.push(pivot + 1);
        stack.push(end);
    }

    while (!stack.isEmpty()) {
        end = stack.pop();
        start = stack.pop();
        pivot = partion(array, start, end);
        if (pivot > start + 1) {
            stack.push(start);
            stack.push(pivot - 1);
        }
        if (pivot < end - 1) {
            stack.push(pivot + 1);
            stack.push(end);
        }
    }
}

1. 初始化

int start = 0;
int end = array.length - 1;
Deque<Integer> stack = new ArrayDeque<>();

• start 和 end 代表数组的左右边界（即待排序区间）。

• stack 是一个双端队列（Deque），用来存储子数组的左右边界，模拟递归调用栈。

2. 第一次分区操作

int pivot = partion(array, start, end);

• 在非递归实现中，首先对整个数组进行一次分区操作，通过调用 partition 方法，获取基准元素的最终位置 pivot。

3. 将左右子数组压入栈

if (pivot > start + 1) {
    stack.push(start);
    stack.push(pivot - 1);
}
if (pivot < end - 1) {
    stack.push(pivot + 1);
    stack.push(end);
}

• 分区操作后，基准元素已经被放置在它的正确位置。接着，将基准元素左右两边的子数组的边界压入栈中，准备对它们进行排序。
  • 如果左边子数组（start 到 pivot - 1）有多于一个元素，就将其压入栈中。
  • 如果右边子数组（pivot + 1 到 end）有多于一个元素，也将其压入栈中。

4. 非递归排序过程

while (!stack.isEmpty()) {
    end = stack.pop();
    start = stack.pop();
    pivot = partion(array, start, end);
    if (pivot > start + 1) {
        stack.push(start);
        stack.push(pivot - 1);
    }
    if (pivot < end - 1) {
        stack.push(pivot + 1);
        stack.push(end);
    }
}

• 使用 while 循环来模拟递归的过程。每次从栈中弹出一对 start 和 end，即一个待排序子数组的左右边界。
• 对该子数组执行分区操作，获得基准元素的最终位置 pivot。
• 如果基准元素左边有子数组（start 到 pivot - 1），并且左边子数组长度大于 1，则将其左右边界压入栈中。
• 如果基准元素右边有子数组（pivot + 1 到 end），并且右边子数组长度大于 1，则将其左右边界压入栈中。
• 继续循环，直到栈为空，排序完成。

partition 方法分析

private static int partion(int[] arr, int left, int right) {
    int i = left;
    int j = right;
    int pivot = arr[left]; // 选择基准元素为第一个元素

    while (i < j) {
        while (arr[j] >= pivot && i < j) {
            j--;
        }
        while (arr[i] <= pivot && i < j) {
            i++;
        }
        swap(arr, i, j);  // 交换
    }

    swap(arr, i, left);  // 将基准元素放置到正确的位置
    return i;
}

1. 基准元素选择

int pivot = arr[left];

• 选择数组的第一个元素作为基准元素。

2. 双指针扫描

while (i < j) {
    while (arr[j] >= pivot && i < j) {
        j--;
    }
    while (arr[i] <= pivot && i < j) {
        i++;
    }
    swap(arr, i, j);
}

• 使用两个指针 i 和 j，分别从数组的两端向中间扫描。
• i 向右移动，直到找到一个比基准元素大的元素；j 向左移动，直到找到一个比基准元素小的元素。
• 然后交换 i 和 j 指向的元素，继续扫描。

3. 基准元素放置

swap(arr, i, left);

• 当两个指针相遇时，i 和 j 就是基准元素应该放置的位置。
• 将基准元素放置到 i（或 j）的位置，并返回 i（或 j）作为新的基准元素的位置。

swap 方法

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

• 交换数组中的两个元素。

优点：

• 非递归：避免了递归调用栈的开销，适合于栈空间较小或者深度较大的情况下使用。
• 高效：时间复杂度在平均情况下为 O(n log n)，最坏情况下为 O(n^2)，但通过改进基准元素的选择可以优化到 O(n log n)。
• 原地排序：快速排序是原地排序算法，空间复杂度低。

缺点：

• 最坏时间复杂度：当基准元素选择不当时，快速排序可能会退化为 O(n^2)，例如在已排序或逆序数组上使用时。
• 不稳定：快速排序不是稳定的排序算法，可能会改变相等元素的相对顺序。

静态展示

假设我们有一个数组 [10, 7, 8, 9, 1, 5]，使用快速排序的非递归版本进行排序。接下来，我们展示分区过程和栈的变化过程。

第一次分区操作:

• 选择 10 为基准元素（pivot = arr[left]）。
• 执行 partition 方法，经过扫描和交换后，基准元素 10 被放置到正确位置。
• 基准元素的位置 pivot = 5（索引 5）。

栈操作：

• 将左子数组（start = 0, end = 4）和右子数组（start = 6, end = 5）的边界压入栈中。
• 栈内容：[0, 4, 6, 5]。

2. 第二次分区操作（左子数组 [10, 7, 8, 9, 1]）：

• 选择 10 为基准元素，经过分区操作后，基准元素 10 已经被放置在索引 4。
• 基准元素的位置 pivot = 4。

栈操作：

• 对左子数组 [10, 7, 8, 9, 1] 继续分区（start = 0, end = 3）。
• 对右子数组 [5]，由于长度为 1，不需要处理。

栈内容：[0, 3, 6, 5]。

3. 第三次分区操作（子数组 [10, 7, 8, 9]）：

• 选择 10 为基准元素，经过分区操作后，基准元素 10 已经被放置在索引 3。
• 基准元素的位置 pivot = 3。

栈操作：

• 对左子数组 [10, 7, 8] 继续分区（start = 0, end = 2）。
• 对右子数组 [9]，由于长度为 1，不需要处理。

栈内容：[0, 2, 6, 5]。

4. 第四次分区操作（子数组 [10, 7, 8]）：

• 选择 10 为基准元素，经过分区操作后，基准元素 10 已经被放置在索引 2。
• 基准元素的位置 pivot = 2。

栈操作：

• 对左子数组 [10, 7] 继续分区（start = 0, end = 1）。
• 对右子数组 [8]，由于长度为 1，不需要处理。

栈内容：[0, 1, 6, 5]。

5. 第五次分区操作（子数组 [10, 7]）：

• 选择 10 为基准元素，经过分区操作后，基准元素 10 已经被放置在索引 1。
• 基准元素的位置 pivot = 1。

栈操作：

• 对左子数组 [10]，由于长度为 1，不需要处理。
• 对右子数组 [7]，由于长度为 1，不需要处理。

栈内容：[6, 5]。

6. 结束

• 当栈为空时，排序结束，最终的数组是：[1, 5, 7, 8, 9, 10]。

时间复杂度

• 最坏时间复杂度：O(n^2)。

  • 在最坏的情况下（例如每次选择的所有pivot阵列中最大或最小的元素），快速排序的队列深度将为n，每次分区的时间复杂度为O(n)，因此总体时间复杂度为O(n^2)。
  • 这种情况通常发生在数据已经部分社区或完全逆序的情况下。

• 平均时间复杂度：O(n log n)。

  • 在平均情况下（即每次选择的pivot能够均匀地进行磁盘分区），快速排序的队列深度大致为log n，每次分区操作的时间复杂度为O(n)，总体时间复杂度为O(n log n)。

• 最好时间复杂度：O(n log n)。

  • 最好的情况发生在每次故障都将阵列均匀分割成两部分，层数的深度为log n，每次故障的时间复杂度为O(n)，因此总时间复杂度为O(n log n)。

空间复杂度

• 快速排序的空间复杂度主要来自于递归栈。每次递归调用都需要一定的栈空间，而递归的最大深度是log n。因此，空间复杂度为O(log n)。
• 注意，快速排序是原地排序算法，不需要额外的存储数据，不用使用栈或分区。

稳定性

快速排序不稳定。在分区操作中，如果有可靠的元素，它们的相对顺序可能会被改变。比如，在分区过程中，如果有两个相邻的元素位于各自基准的两边，它们的顺序可能会发生变化，因此快速排序是一个不稳定的排序算法。

优缺点

优点：

• 平均时间复杂度如下：在大多数情况下，快速排序的时间复杂度为O(n log n)，性能优于其他O(n log n)算法，如归并排序和堆排序。
• 原地排序：快速排序是原地排序算法，不需要额外的存储空间，空间复杂度低。
• 强大：对于大多数数据集，快速排序表现良好，特别是在数据量增加的情况下。

缺点：

• 不稳定排序：快速排序会改变元素的相对顺序。
• 最坏时间复杂度分数：在最坏情况下，时间复杂度为O(n²)，虽然可以通过随机选择基准元素或“三数取中”来减少最坏情况的发生，但它仍然有可能出现最坏的情况。
• 网络深度增加：在某些极端情况下，网络深度可能达到n，导致栈溢出。

适用场景

• 大数据排序：快速排序是处理大数据集合时非常的排序算法，尤其适用于内存中的排序。
• 随机访问数据结构：对于阵列快速排序（顺序存储）这种随机访问的数据结构非常高效。
• 需要高效排序的场景：当需要一个排序算法且不要求高效的稳定性时，快速排序通常是首选。

5.并归算法

归并排序（Merge Sort）是一种典型的分治法排序算法，由John von Neumann在1945年提出。归并排序将一个大问题分解成若干个小问题，逐步解决这些小问题，然后将它们合并成一个大问题的解。归并排序的核心思想是通过递归地分割数组，直到数组中每个部分只包含一个元素，然后将这些部分合并成有序的数组。

原理

归并排序的基本思想是：

1. 分割：将数组分成两半，递归地对每个子数组进行排序。
2. 合并：将排序好的子数组合并成一个有序数组。在合并的过程中，通过比较每个子数组的元素，依次将较小的元素加入到新的数组中。

算法步骤

1. 分解：将待排序数组分成两半，递归地对每一半进行归并排序，直到子数组的长度为 1。
2. 合并：对每一对已排序的子数组进行合并操作，合并成一个新的有序子数组。合并时，依次比较两个子数组的元素，选择较小的元素放入结果数组，直到一个子数组全部合并。
3. 递归：对左子数组和右子数组递归执行上述过程，直到数组完全有序。

递归版

private static void mergeSort(int[] arr) {
    mergeSortTmp(arr,0,arr.length-1);
}

private static void mergeSortTmp(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = (right + left) / 2;
    mergeSortTmp(arr, left, mid);  // 排序左半部分
    mergeSortTmp(arr, mid + 1, right);  // 排序右半部分
    merge(arr, left, mid, right);  // 合并
}

private static void merge(int[] arr, int left, int mid, int right) {
    int[] tmp = new int[right - left + 1];  // 临时数组，用来存放合并后的数据
    int k = 0;  // 临时数组的索引
    int s1 = left;  // 左子数组的起始位置
    int s2 = mid + 1;  // 右子数组的起始位置

    // 合并两个有序子数组
    while (s1 <= mid && s2 <= right) {
        if (arr[s1] < arr[s2]) {
            tmp[k++] = arr[s1++];  // 将较小的元素放入临时数组
        } else {
            tmp[k++] = arr[s2++];  // 将较小的元素放入临时数组
        }
    }

    // 如果左子数组还有剩余元素，将其加入临时数组
    while (s1 <= mid) {
        tmp[k++] = arr[s1++];
    }

    // 如果右子数组还有剩余元素，将其加入临时数组
    while (s2 <= right) {
        tmp[k++] = arr[s2++];
    }

    // 将临时数组的元素复制回原数组
    for (int i = 0; i < k; i++) {
        arr[i + left] = tmp[i];
    }
}

1. mergeSort(int[] arr)

• 作用：mergeSort 是归并排序的入口方法，它接受一个整型数组 arr 作为参数。
• 功能：调用 mergeSortTmp 方法来递归地对数组进行排序。
• 注意：arr.length - 1 是数组的右边界（即数组的最后一个索引），所以是递归排序的右边界。

2. mergeSortTmp(int[] arr, int left, int right)

• 作用：mergeSortTmp 是归并排序的递归方法，它负责递归地将数组分成两半进行排序，直到数组大小为1。
• 步骤：
  1. 递归终止条件：当 left >= right 时，表示当前数组只有一个元素，已经有序。此时不需要继续递归。
  2. 计算中间点：mid = (right + left) / 2，计算当前子数组的中间索引。
  3. 递归排序：
     • 先递归排序左半部分：mergeSortTmp(arr, left, mid)
     • 再递归排序右半部分：mergeSortTmp(arr, mid + 1, right)
  4. 合并操作：递归完成后，通过 merge 方法合并左右两个有序子数组。

3. merge(int[] arr, int left, int mid, int right)

• 作用：merge 方法负责将两个有序的子数组合并成一个有序的数组。
• 步骤：
  1. 创建临时数组：tmp 用于存放合并后的数组数据，数组的大小为 right - left + 1，即合并的两个子数组的大小之和。
  2. 合并操作：
     • 使用两个指针 s1 和 s2 分别指向左右子数组的起始位置。
     • 比较两个子数组中的元素，将较小的元素放入临时数组 tmp 中。
     • 一旦某个子数组的元素全部合并到 tmp 中，直接将另一个子数组中剩余的元素加入 tmp。
  3. 将合并后的数据复制回原数组：
     • 将临时数组 tmp 中的所有元素复制回原数组 arr 的对应位置，从 left 开始，直到合并完成。

静态展示

假设我们有一个数组 [38, 27, 43, 3, 9, 82, 10]，我们用归并排序来对其进行排序：

1. 初始数组：[38, 27, 43, 3, 9, 82, 10]

2. 第一次分割：

   • [38, 27, 43] 和 [3, 9, 82, 10]

3. 继续分割：

   • [38, 27, 43] -> [38] 和 [27, 43]，然后将 [27, 43] 继续分割成 [27] 和 [43]
   • [3, 9, 82, 10] -> [3, 9] 和 [82, 10]，然后将 [3, 9] 继续分割成 [3] 和 [9]，[82, 10] 继续分割成 [82] 和 [10]

4. 开始合并：

   • [27] 和 [43] 合并成 [27, 43]
   • [3] 和 [9] 合并成 [3, 9]
   • [82] 和 [10] 合并成 [10, 82]

5. 合并结果：

   • 合并 [38] 和 [27, 43] 成 [27, 38, 43]
   • 合并 [3, 9] 和 [10, 82] 成 [3, 9, 10, 82]

6. 最终合并：

   • 合并 [27, 38, 43] 和 [3, 9, 10, 82]，最终得到有序数组 [3, 9, 10, 27, 38, 43, 82]

非递归版

public static void mergeSortNor(int[] array) {
    int gap = 1;
    while (gap < array.length) {
        for (int i = 0; i < array.length; i = i + gap * 2) {
            int left = i;
            int mid = left + gap - 1;
            if(mid >= array.length) {
                mid = array.length-1;
            }
            int right = mid + gap;
            if(right >= array.length) {
                right = array.length-1;
            }
            merge(array,left,mid,right);
        }
        gap *= 2;
    }
}

gap 变量的作用：

• gap 是当前要合并的子数组的“间隔”或“块”的大小。初始值为 1，表示每次合并两个单独的元素（大小为1的子数组）。在每一轮合并操作后，gap 会翻倍，表示合并的范围逐渐增大，直到整个数组被完全合并。

外部 while 循环：

while (gap < array.length) {
    // 合并操作
    gap *= 2;
}

• 作用：每次增加 gap 的大小，直到 gap 大于或等于数组的大小为止。
• gap 每次翻倍，表示每一轮合并的子数组的大小逐渐增大。

内部 for 循环：

for (int i = 0; i < array.length; i = i + gap * 2) {
    int left = i;
    int mid = left + gap - 1;
    if(mid >= array.length) {
        mid = array.length - 1;
    }
    int right = mid + gap;
    if(right >= array.length) {
        right = array.length - 1;
    }
    merge(array, left, mid, right);
}

• 作用：该循环用于每次处理 gap 大小的子数组，通过分段逐步将相邻的子数组合并。
• i 是每次处理的子数组的左边界，left 是当前要合并的第一个子数组的左边界。
• mid 是当前子数组的中间点，即第一个子数组的右边界。
• right 是当前子数组的右边界，表示第二个子数组的右边界。right 可能会超出数组的边界，因此需要检查并调整为数组的最后一个索引。

merge(array, left, mid, right)：

• 作用：将两个已排序的子数组 [left, mid] 和 [mid+1, right] 合并为一个有序的数组。这个 merge 操作是归并排序的核心部分。

gap *= 2：

• 作用：在每次完成一次合并后，gap 的大小翻倍，意味着合并的范围变大。

时间复杂度

• 最坏时间复杂度：O(n log n)，在归并排序中，不管数据如何，分割过程和合并过程的时间复杂度始终是 O(n log n)。
• 最好时间复杂度：O(n log n)，即使是最好的情况，归并排序也需要执行 log n 级别的递归，并且每一层递归中会处理 n 个元素。
• 平均时间复杂度：O(n log n)，归并排序的平均时间复杂度也是 O(n log n)。

空间复杂度

归并排序需要额外的空间来存储合并后的数组，因此其空间复杂度是 O(n)，其中 n 是待排序数组的长度。每次合并时，需要创建一个临时数组来存储排序后的数据。

稳定性

归并排序是稳定的。当两个元素相等时，归并排序会保持它们在原数组中的相对顺序。因为在合并两个子数组时，相等的元素会按先出现的顺序排列。

优缺点

优点：

• 时间复杂度稳定：归并排序的时间复杂度是 O(n log n)，无论输入数据的顺序如何，时间复杂度都一样。
• 稳定排序：归并排序是一种稳定排序算法，相同的元素不会改变相对顺序。
• 适用于大数据：由于其稳定的 O(n log n) 时间复杂度，归并排序特别适合大规模数据的排序，尤其是在外部排序（例如磁盘排序）中应用广泛。

缺点：

• 空间复杂度较高：归并排序需要额外的空间，空间复杂度为 O(n)，比一些原地排序算法（如快速排序）要高。
• 实现较复杂：与简单的排序算法（如冒泡排序、选择排序）相比，归并排序的实现相对复杂，尤其是在处理合并操作时。
• 适合链表而非数组：归并排序虽然适用于数组，但在链表结构中，由于链表操作的特性（不需要额外的空间来合并），它的性能表现更好。

适用场景

• 大数据集排序：对于非常大的数据集，归并排序表现出色，尤其是在数据存储在磁盘等外部介质上时，归并排序能够进行外部排序。
• 需要稳定排序：当排序需要保持相等元素的相对顺序时，归并排序是非常理想的选择。
• 链表排序：归并排序非常适合链表排序，因为链表的合并操作不需要额外的空间，可以直接在链表中进行操作。

结语

排序算法是计算机科学中非常基础且重要的算法之一，广泛应用于各种数据处理任务中。通过对快速排序、归并排序、冒泡排序、选择排序等经典排序算法的分析，我们可以看到，每种排序算法在时间复杂度、空间复杂度、稳定性以及适用场景上都有其特点和优势。

• 冒泡排序和选择排序虽然简单易懂，但在大规模数据排序时性能较差，适合小规模或部分有序的数据。
• 快速排序通过分治法有效地将大规模数据分解为小问题，平均情况下表现非常优秀，虽然最坏情况的时间复杂度较高，但通过优化基准选择策略可以大大降低这种情况的发生几率。
• 归并排序通过递归地将数据分割并合并，确保了稳定性和 O(n log n) 的时间复杂度，尤其在外部排序和链表排序中有广泛应用，尽管其空间复杂度较高。

在实际应用中，如何选择排序算法取决于数据的规模、初始状态、稳定性要求以及对空间复杂度的考虑。例如，快速排序通常是大数据排序的首选，而在需要稳定排序的情况下，归并排序则可能更为合适。

总之，了解各种排序算法的实现原理及其适用场景，不仅能帮助我们在不同的任务中做出合理的选择，还能为后续算法的学习和优化打下坚实的基础。希望通过这篇文章的讲解，读者能对排序算法有更深刻的理解，并能根据实际需求灵活选择合适的算法，以提高程序的效率和性能。