数据结构-8.Java. 七大排序算法(下篇)

![排序算法图解](https://pic.it1024doc.com/csdn/202412/e7a5ab870db2dde966e37f2c83a37ae4.jpeg)

> 本文将深入探讨排序算法的核心概念，由于篇幅限制，我们将分两部分进行讨论。今日的主题是归并排序，以及快速排序的非递归实现技巧。  
>  专栏：Java-**数据结构**  
>  如有疑问，请在评论区留言讨论。  
>  欢迎点赞、评论、收藏和分享本文。  
>  如果你不知道分享给谁，那就分享给热爱技术的朋友吧。  
>  你们的支持是我持续创作的动力。

#### 尊贵的读者，请细读！

  * [快速排序的非递归实现](#快速排序的非递归实现)
    * [具体实现步骤](#具体实现步骤)
      * [区间入栈的细节](#区间入栈的细节)
    * [代码展示](#代码展示)
    * [快速排序的特性总结](#快速排序的特性总结)
  * [归并排序](#归并排序)
    * [归并排序的基本思想](#归并排序的基本思想)
    * [具体步骤](#具体步骤)
      * [分解操作](#分解操作)
      * [合并排序操作](#合并排序操作)
    * [归并排序的非递归实现](#归并排序的非递归实现)
    * [归并排序的特性总结](#归并排序的特性总结)

## 快速排序的非递归实现

在获得基准值pivot后，我们如何对左右子序列进行快速排序呢？答案是利用栈来保存左右区间。

### 具体实现步骤

1. 利用之前的partition算法获取基准值，并将左右区间存储在栈中。
2. 重复上述步骤，直到栈为空。

#### 区间入栈的细节

如下是分析图：
![快速排序区间入栈图解](https://pic.it1024doc.com/csdn/202412/d8041981cc75a0a14a46762ca5c6a7d7.png)

### 代码展示

```java
    // 挖坑法求基准值
    private static int partition2(int[] array, int left, int right) {
        int key = array[left];
        while (left < right) {
            while (left < right && array[right] >= key) {
                right--;
            }
            // 从右边开始第一个比key小的元素覆盖[left]
            array[left] = array[right];
            while (left < right && array[left] <= key) {
                left++;
            }
            // 从左边开始第一个比key大的元素覆盖空位
            array[right] = array[left];
        }
        // key填补最终的空位，此时left=right
        array[left] = key;
        return left;
    }

    // 快速排序的非递归实现
    public static void quickSortNor(int[] array) {
        Stack stack = new Stack<>();
        int left = 0;
        int right = array.length - 1;
        // 获取第一个基准
        int pivot = partition2(array, left, right);
        // 左序列区间端点入栈
        if (pivot - 1 > left) {
            stack.push(left);
            stack.push(pivot - 1);
        }
        // 右序列区间端点入栈
        if (pivot + 1 < right) {
            stack.push(pivot + 1);
            stack.push(right);
        }
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = partition2(array, left, right);
            if (pivot - 1 > left) {
                stack.push(left);
                stack.push(pivot - 1);
            }
            if (pivot + 1 < right) {
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }

快速排序的特性总结

1. 快速排序因其出色的综合性能而得名。
2. 时间复杂度：O(N*logN)。
   
3. 空间复杂度：O(logN)。
4. 稳定性：不稳定。

归并排序

归并排序的基本思想

归并排序（MERGE-SORT）是一种基于归并操作的高效排序算法，它采用分治法（Divide and Conquer