C++ 迭代快速排序程序

在本文中，我们将讨论迭代快速排序的 C++ 程序。但在其实现之前，我们必须了解迭代快速排序及其算法和示例。

一种以其实际效率和有效性而闻名的流行排序算法称为“快速排序”。尽管快速排序的递归变体更常用，但也可以实现迭代版本以规避与递归函数调用相关的开销。这种迭代方法使用堆栈来管理需要排序的数组分区。

快速排序的基本原理是将数组的剩余组件根据它们是大于还是小于枢轴分为两个子数组，然后从数组中选择一个枢轴元素。之后，子数组迭代地执行此过程，从而对整个数组进行排序。

分区函数在程序开始时定义，它选择一个枢轴元素并对数组进行分区。“iterativeQuickSort”函数使用堆栈来跟踪需要排序的子数组。它在不断地从堆栈中移除子数组并用分区函数对它们进行分区后，将结果子数组推回堆栈。重复此操作，直到堆栈为空，以确保每个元素都正确排序。

该程序使用一个示例数组来展示其功能。该数组在排序过程之前和之后都显示出来，清晰地展示了元素如何使用迭代快速排序方法按升序排列。

开发人员可以通过理解和实践该算法的迭代版本来欣赏快速排序的效率，并学习如何优化实际设置中的排序算法。迭代方法使用显式堆栈揭示了算法设计中递归和迭代之间的权衡。

迭代快速排序算法

1. 开始
2. 选择任意元素作为枢轴。
3. 如果元素小于枢轴。
4. 与索引处的元素交换。
5. 增加索引。
6. 将所有小于枢轴的元素推到左侧。
7. 将所有大于枢轴的元素推到右侧。
8. 将最右边的元素与索引处的元素交换。
9. 返回索引。
10. 打印排序后的数组。
11. 停止

复杂度分析

时间复杂度

快速排序的平均和最佳时间复杂度为O(n log n)，这使其对于大型数据集非常有效。另一方面，如果枢轴选择反复导致不平衡分区，则在最坏情况下，时间复杂度可能降至O(n^2)。递归和迭代版本保持相同的时间复杂度特性。

空间复杂度

由于快速排序是一种原地排序算法，因此其内存要求与输入量不成比例。迭代版本可能比递归版本使用更少的内存，因为它使用显式堆栈。

示例

让我们举一个例子来说明 C 中的迭代快速排序

输出

Original array: 12 4 5 6 7 3 1 15 
Sorted array: 1 3 4 5 6 7 12 15

说明

1. 在此示例中，程序包括 C++ 的典型指令。包含<iostream>头文件以进行输入/输出操作，并包含<stack>以使用堆栈数据结构。
2. 这就是分区函数的工作原理。其参数是低索引(low)、高索引(high)和数组(arr)。在选择高索引处的元素作为枢轴后，该函数重新排列数组的元素，使任何小于或等于枢轴的元素位于左侧，任何大于枢轴的元素位于右侧。分区后，返回枢轴元素的索引。
3. 这就是称为iterativeQuickSort的函数。需要低索引(low)、高索引(high)和数组(arr)。使用堆栈(stk)跟踪需要排序的子数组。它使用 while 循环迭代处理子数组。它在每次迭代开始时从堆栈中移除一个子数组，使用分区函数对其进行分区，如果子数组已经排序，则将其推回堆栈。
4. 之后，我们使用printArray函数，其参数是数组(arr)和大小(size)。它将数组的元素输出到标准输出。
5. main()函数是主函数和程序的入口点。首先，初始化一个数组，然后它使用printArray函数显示原始数组，使用iterativeQuickSort方法对其进行排序，最后再次显示排序后的数组。

结论

总之，该软件通过利用堆栈实现迭代快速排序算法，有效地管理排序过程。分区函数负责围绕枢轴重新排列元素，而iterativeQuickSort函数则使用堆栈迭代进行排序。主函数使用示例数组展示了如何使用这些函数。