【数据结构】非递归实现的快速排序与归并排序算法解析

内容导航
第一部分：非递归快速排序
1.核心思想
2.代码实现
2.1 栈结构应用
2.2 分区函数解析
2.3 左区间处理
第二部分：非递归归并排序
1.基本概念
2.具体实现
2.1 步长设置
2.1.1 索引递增规则
2.1.2 步长倍增机制
2.1.3 终止条件
2.2 边界参数
2.2.1 起始位置确定
2.2.2 中间值处理
第三部分：算法性能对比

阅读建议：
在理解非递归实现的快速排序前，建议先掌握其递归版本：递归版快速排序详解，其中详细阐述了基准值选取的关键技术。
同样，递归实现的归并排序知识也很重要：递归归并排序解析

第一部分：非递归快速排序

1.核心思想

• 通过迭代方式在动态变化的排序区间内执行基准排序，逐个确定元素最终位置，当所有元素的排序区间都处理完毕时，整个序列即完成排序
  （在划分区间时，通常选取区间首元素作为基准值）
  采用基准排序处理每个元素时，由于每个元素的最终位置确定后都会将序列划分为左右两个子区间，因此后续元素的处理区间会随之动态调整

2.代码实现

public static void iterativeQuickSort(int[] arr) {
Deque stack = new ArrayDeque<>();//2.1
int start = 0;
int end = arr.length-1;
int partitionIndex = partition(arr,start,end);//2.2
if(partitionIndex - 1 > start) {//2.3
stack.push(start);
stack.push(partitionIndex-1);
}
if(partitionIndex + 1 < end) {
stack.push(partitionIndex+1);
stack.push(end);
}
while (!stack.isEmpty()) {
end = stack.pop();
start = stack.pop();
partitionIndex = partition(arr,start,end);
if(partitionIndex - 1 > start) {
stack.push(start);
stack.push(partitionIndex-1);
}
if(partitionIndex + 1 < end) {
stack.push(partitionIndex+1);
stack.push(end);
}
}
}

2.1 栈结构应用

利用栈结构存储待处理的子区间边界，实现深度优先的区间处理顺序

2.2 分区函数解析

该函数实现基准排序的核心逻辑：
- 选取区间首元素为基准值
- 通过双指针法将小于基准值的元素移到左侧
- 大于基准值的元素移到右侧
- 最终返回基准值的正确位置

2.3 左区间处理

当partitionIndex - 1 > start成立时，说明左侧子区间至少包含两个待排序元素，需要继续处理

第二部分：非递归归并排序

1.基本概念

采用自底向上的合并策略，通过逐步扩大合并区间的方式，最终实现整个序列的有序排列

2.具体实现

public static void iterativeMergeSort(int[] arr) {
int mergeSize = 1;//2.1
while (mergeSize < arr.length) {
for (int i = 0; i < arr.length; i += 2*mergeSize) {//2.1.1
int left = i;
int mid = left + mergeSize - 1;
int right = mid + mergeSize;
if(mid >= arr.length) {//2.2.2
mid = arr.length-1;
}
if(right >= arr.length) {
right = arr.length-1;
}
merge(arr,left,right,mid);
}
mergeSize <<= 1;//2.1.2
}
}

2.1 步长设置

初始步长设为1，表示最初每个元素自身就是一个有序区间

2.1.1 索引递增规则

每次处理完成后，索引增加两倍步长，确保跳过已合并的区间

2.1.2 步长倍增机制

每轮合并完成后，将合并区间大小扩大一倍

2.1.3 终止条件

当步长超过数组长度时，说明最后一次合并已完成整个序列的排序

2.2 边界参数

• left：当前合并区间的起始位置
• mid：前一个有序子区间的结束位置
• right：后一个有序子区间的结束位置

2.2.1 起始位置确定

从数组起始位置开始，逐步处理每个合并区间

2.2.2 中间值处理

当mid超过数组长度时，调整合并区间为剩余的全部元素

第三部分：算法性能对比