快速排序原理 C# 递归

快速排序原理 C# 递归

快速排序是一种二分法排序方法，实际上理论上真正最快的排序方法是黄金分割法，但是这在计算机上是很难实现的，因此快速排序也算是兼顾了速度与占用内存的一种较好的排序方式：
快速排序的实现步骤大概如下：

【假设我们需要将一个数组按照从小到大的顺序排列】

1、选最左侧的数作为一个基准数，并从左–>右 和 从右–>左 分别寻找比基准数大 和 比基准数小的数，一定是先从右边先找，这是因为我们选择的是最左侧的数作为基准数，最后要将这个数放到最中间，而如果先从左边找，那么当左右相遇时候就可能出现中间数实际上比最左边的基准数大，这样就出BUG了，因此一定是先从右边寻找，然后找到一个小于基准数时就停下来，这时候，再从左边开始寻找，然后当找一个比基准数大的数就停下来，一直这样，直到左右寻找相遇。相遇时就将这个相遇点的数和第一个基准数交换。
2、经过了第一步就将数组分成了 2 份，相遇点左边一份 ，相遇点右边一份，然后在对着两部分重复第一步…
3、最后，当分到每一小份左右只有一个数的时候就完成了快速排序。

其中第二步涉及到递归过程，当然也是很好理解的，只要这个过程类似并且是具有递进关系的都可以用递归。
就像切蛋糕一样，先一分为二，再一分为二，再一分为二，切的这个过程就是一个类似的过程，而越分越小就是一个递进的关系。

快速排序的时间复杂度为：O(N*log(N))

下面贴出代码，这样理解更容易：

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace FastSort{class Program{static double[] RequireSortNum;static void Main(string[] args){NumInit();Console.WriteLine(\"初始数据：\");ShowCurrentSort();FastSort(0, 99);Console.WriteLine(\"快排序后数据：\");ShowCurrentSort();Console.Read();}static void FastSort(int LeftIndex,int RightIndex){if (LeftIndex > RightIndex)return;double BaseNum = RequireSortNum[LeftIndex];//将第一个点假设为基准点int CurrentRightIndex = RightIndex;//当前询问的右侧坐标int CurrentLeftIndex = LeftIndex;//当前询问的左侧坐标double temp;//交换的暂存值while (CurrentRightIndex != CurrentLeftIndex)//已知要询到左右两边相遇 这时候相遇点就是基准点的位置{while (RequireSortNum[CurrentRightIndex] >= BaseNum && CurrentRightIndex > CurrentLeftIndex){CurrentRightIndex--;}while (RequireSortNum[CurrentLeftIndex] < BaseNum && CurrentRightIndex > CurrentLeftIndex){CurrentLeftIndex++;}if (CurrentRightIndex > CurrentLeftIndex)//如果两边没有相遇就交换{temp = RequireSortNum[CurrentRightIndex];RequireSortNum[CurrentRightIndex] = RequireSortNum[CurrentLeftIndex];RequireSortNum[CurrentLeftIndex] = temp;}}//当两边相遇了 就将第一个基准点 放到中间位置RequireSortNum[LeftIndex] = RequireSortNum[CurrentRightIndex];RequireSortNum[CurrentRightIndex] = BaseNum;//将第一个点【这个点就是基准点】 放到中间位置//这是因为一开始是先从右边开始轮询的，最左边的被选做基准点的数并没有到正确的中间位置//这一步正是让这个点到它该去的位置FastSort(LeftIndex,CurrentLeftIndex-1);//排列中间点左侧的数据FastSort(CurrentRightIndex+1, RightIndex);//排列中间点右侧的数据}static void NumInit(){RequireSortNum = new double[100];Random rand = new Random();for(int a = 0;a < 100;a++)RequireSortNum[a] = 100 * rand.NextDouble();}static void ShowCurrentSort(){foreach (double item in RequireSortNum)Console.WriteLine(item.ToString(\"f0\"));Console.Write(\"\\n\\n\\n\");}}}