我们知道,方法的调用是采用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();
}
}
}
程序运行如图:
