C#快速排序QuickSort将递归算法修改为堆栈Stack非递归方式

我们知道,方法的调用是采用Stack的方式[后进先出:LIFO],

在DeepSeek中快速搜索C#快速排序,

搜索结果如图:

我们会发现是采用递归的方式 .

递归的优点:

简单粗暴,类似于直接写数学公式,因代码量较少,易于理解.递归与循环迭代的运行次数都是一致的

递归的缺点:

占用大量的内存空间,每一次的递归都需要保存[案发现场]出栈和进栈数据,因操作系统为每个线程分配的内存空间是有限的,当递归超过内存空间限度时,会引发堆栈溢出异常:StackOverflowException

我们这里,使用Stack来将快速排序算法进行改造,改造为非递归的快速排序算法

先复制DeepSeek快速排序示例代码,如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;namespace QuickSortDemo
{class Program{static void Main(string[] args){int[] arr = { 10, 7, 8, 9, 1, 5, 18, 15, 4, 32, 25 };Console.WriteLine("原始数组:");PrintArray(arr);Sort(arr);Console.WriteLine("排序后的数组:");PrintArray(arr);Console.ReadLine();}// 快速排序的主函数public static void Sort(int[] arr){if (arr == null || arr.Length == 0)return;QuickSortRecursive(arr, 0, arr.Length - 1);}// 递归实现快速排序private static void QuickSortRecursive(int[] arr, int left, int right){if (left < right){int pivotIndex = Partition(arr, left, right);// 递归排序左半部分QuickSortRecursive(arr, left, pivotIndex - 1);// 递归排序右半部分QuickSortRecursive(arr, pivotIndex + 1, right);}}// 分区函数，返回基准元素的最终位置private static int Partition(int[] arr, int left, int right){int pivot = arr[right];  // 选择最后一个元素作为基准int i = left - 1;  // i是小于基准的元素的最后一个位置for (int j = left; j < right; j++){if (arr[j] < pivot){i++;Swap(arr, i, j);}}// 将基准元素放到正确的位置Swap(arr, i + 1, right);return i + 1;  // 返回基准元素的索引}// 交换数组中两个元素的位置private static void Swap(int[] arr, int i, int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}// 打印数组public static void PrintArray(int[] arr){foreach (var item in arr){Console.Write(item + " ");}Console.WriteLine();}}
}

实现方法:

我们可以发现:对于递归Recursive代码更新为堆栈Stack循环代码,仅需三个步骤即可实现:

①将所有参数封装为元组Tuple或者一个自定义类

如递归方法void QuickSortRecursive(int[] arr, int left, int right)

就定义一个元组 Tuple<int[], int, int> 作为整体元素[参数集合]传递

②定义一个泛型Stack,每个元素都是一个元组

如Stack<Tuple<int[], int, int>> stack ,并将入口参数推入到堆栈stack中

stack.Push(Tuple.Create(arr, left, right));

然后一直死循环判断堆栈stack集合是否不为空,循环体第一步就去抓取并删除一个元素[Pop]

while (stack.Count > 0)

{

    Tuple<int[], int, int> tuple = stack.Pop();

     //.......

}

③将原来的使用递归方法调用自身的使用修改为推入堆栈中[Push]

stack.Push(Tuple.Create(arr, left, pivotIndex - 1));

至此更新完毕.这三个步骤同样适用于队列Queue,仅仅将方法更新为Enqueue()和Dequeue()

 更新后的代码如下:

同时增加另一种代码改造:Queue队列

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;namespace QuickSortDemo
{class Program{static void Main(string[] args){int[] arr = { 10, 7, 8, 9, 1, 5, 18, 15, 4, 32, 25, 11 };int[] arrStack = new int[arr.Length];int[] arrQueue = new int[arr.Length];Array.Copy(arr, arrStack, arr.Length);Array.Copy(arr, arrQueue, arr.Length);ShowSort("Recursive", arr, QuickSortRecursive);ShowSort("Stack", arrStack, QuickSortStack);ShowSort("Queue", arrQueue, QuickSortQueue);Console.ReadLine();}/// <summary>/// 显示快速排序的耗时/// </summary>/// <param name="sortMethodName"></param>/// <param name="arr"></param>/// <param name="actionQuickSort"></param>private static void ShowSort(string sortMethodName, int[] arr, Action<int[], int, int> actionQuickSort) {Console.WriteLine($"【{sortMethodName}】原始数组:");PrintArray(arr);Stopwatch stopwatch = new Stopwatch();stopwatch.Start();Sort(arr, actionQuickSort);stopwatch.Stop();Console.WriteLine($"【{sortMethodName}】排序后的数组（耗时:{stopwatch.Elapsed.TotalMilliseconds}ms）:");PrintArray(arr);}// 快速排序的主函数public static void Sort(int[] arr, Action<int[], int, int> actionQuickSort){if (arr == null || arr.Length == 0)return;//QuickSortRecursive(arr, 0, arr.Length - 1);actionQuickSort(arr, 0, arr.Length - 1);}// 递归实现快速排序private static void QuickSortRecursive(int[] arr, int left, int right){if (left < right){int pivotIndex = Partition(arr, left, right);// 递归排序左半部分QuickSortRecursive(arr, left, pivotIndex - 1);// 递归排序右半部分QuickSortRecursive(arr, pivotIndex + 1, right);}}/// <summary>/// 使用堆栈Stack实现快速排序/// </summary>/// <param name="arr"></param>/// <param name="left"></param>/// <param name="right"></param>private static void QuickSortStack(int[] arr, int left, int right){Stack<Tuple<int[], int, int>> stack = new Stack<Tuple<int[], int, int>>();stack.Push(Tuple.Create(arr, left, right));while (stack.Count > 0){Tuple<int[], int, int> tuple = stack.Pop();arr = tuple.Item1;left = tuple.Item2;right = tuple.Item3;if (left < right){int pivotIndex = Partition(arr, left, right);// 排序左半部分 放入堆栈中stack.Push(Tuple.Create(arr, left, pivotIndex - 1));// 排序右半部分 放入堆栈中stack.Push(Tuple.Create(arr, pivotIndex + 1, right));}}            }/// <summary>/// 使用队列Queue实现快速排序/// </summary>/// <param name="arr"></param>/// <param name="left"></param>/// <param name="right"></param>private static void QuickSortQueue(int[] arr, int left, int right){Queue<Tuple<int[], int, int>> queue = new Queue<Tuple<int[], int, int>>();queue.Enqueue(Tuple.Create(arr, left, right));while (queue.Count > 0){Tuple<int[], int, int> tuple = queue.Dequeue();arr = tuple.Item1;left = tuple.Item2;right = tuple.Item3;if (left < right){int pivotIndex = Partition(arr, left, right);// 排序左半部分 放入堆栈中queue.Enqueue(Tuple.Create(arr, left, pivotIndex - 1));// 排序右半部分 放入堆栈中queue.Enqueue(Tuple.Create(arr, pivotIndex + 1, right));}}}// 分区函数，返回基准元素的最终位置private static int Partition(int[] arr, int left, int right){int pivot = arr[right];  // 选择最后一个元素作为基准int i = left - 1;  // i是小于基准的元素的最后一个位置for (int j = left; j < right; j++){if (arr[j] < pivot){i++;Swap(arr, i, j);}}// 将基准元素放到正确的位置Swap(arr, i + 1, right);return i + 1;  // 返回基准元素的索引}// 交换数组中两个元素的位置private static void Swap(int[] arr, int i, int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}// 打印数组public static void PrintArray(int[] arr){foreach (var item in arr){Console.Write(item + " ");}Console.WriteLine();}}
}

程序运行如图: