对于一个游戏爱好者和游戏开发者，数据结构和算法显得极为重要，这些可以体现一个开发者的逻辑能力。而作为一个游戏开发小白，要争取每天一个算法，游戏之路漫漫而其修远兮，吾将上下而求索。
这次写个快排的递归非递归算法，小白一个，有误之处多多见谅。废话不多说直接上代码。
using System.Collections.Generic;/// <summary>/// QuickSort/// 主要思路，不停找中间数并将数组一分为二，，分治法思想，时间复杂度为n*logn/// 递归比非递归的效率高，以这个数组为例大约快6倍，原因在于递归算法只有一个pivot的变量，栈很小/// </summary>namespace test{class MainClass{public static void Main (string[] args){int [] arr = new int[] {3, 1, 5, 6, 8, 2, 4, 11, 0};long t1 = DateTime.Now.Ticks;QuickSortRecursion (0, arr.Length – 1, arr);//QuickSortWithoutRecursion (0, arr.Length – 1, arr);long t2 = DateTime.Now.Ticks;//输出foreach (int i in arr) {Console.WriteLine (i);}Console.WriteLine ("DelaTime : " + (t2 – t1));}//分治法分开的部分的算法private static int Partition (int low, int high, int [] arr) {int left = low;int right = high;int pivot = arr [low];//用于对比的关键点//实现比pivot大的数放后面，比pivot小的数放前面，复杂度为nwhile (left < right) {while (left < right && arr [right] >= pivot) {right–;}arr [left] = arr [right];//比pivot大的数扔前面while (left < right && arr [left] <= pivot) {left++;}arr [right] = arr [left];//pivot小的数扔后面}arr [left] = pivot;//对关键点移动后的索引位置赋值return left;//此时左右标志位索引一致，返回任一即可}//快速排序调用递归的方法private static void QuickSortRecursion (int low, int high, int [] arr) {int pivot;if (low < high) {pivot = Partition (low, high, arr);//获取新的关键点的索引位置QuickSortRecursion (low, pivot – 1, arr);QuickSortRecursion (pivot + 1, high, arr);}}//非递归快速排序,使用栈的思路，将每次需要private static void QuickSortWithoutRecursion (int low, int high, int [] arr) {Stack <int> stack = new Stack<int> ();stack.Push (low);//现在栈中放入数组的首尾位置stack.Push (high);while (stack.Count != 0) {//当栈为空，说明所有元素已经遍历完，数组已经排好int q = stack.Pop ();int p = stack.Pop ();int pivot = Partition (p, q, arr);//每次从栈中取出一对首尾值并获取此部分数组的关键值if (p < pivot – 1) {stack.Push (p);stack.Push (pivot – 1);}if (pivot + 1 < q) {//两个判断表示当关键值符合大于首小于尾的条件时将其stack.Push (pivot + 1);//和首尾放入栈以便下次排序stack.Push (q);}}}}}最后给下两种算法运行分别所消耗的时间：递归算法：10001，非递归算法：60003，可见递归算法效率高于非递归算法，原因应该是递归算法中只有一个pivot的变量，所占栈的内存很小。
有什么意见或者更好的代码欢迎大家与我沟通。
版权声明：本文为博主原创文章，未经博主允许不得转载。
最重要的是今天的心。
