快速排序算法 介绍 步骤 代码 性能分析
快速排序是对冒泡排序的一种改进。
思想：将排序的数据分为两部分，一部分数据所有数据小于另一部分所有数据，然后在分别进行快速排序，排序过程可递归，从而得到有序序列。
它使用分治法（Divide and conquer）策略，把一个串行分为两个子串行。
步骤
1. 从数列中选一个元素，作为“基准”（pivot）；
2. 重新排序数列，比基准小的值在左边（left），大的值在右边（right），等值随意；得到两个子数列：left、right；
3. left子数列重复1和2；right子数列重复1和2；递归。
代码
/// <summary> /// 一次排序单元，左边小，右边大 /// </summary> /// <param name="array">排序数组</param> /// <param name="left">排序起始位置</param> /// <param name="right">排序结束位置</param> /// <returns></returns> private static int SortUnit(int[] array, int left, int right) { int pivot = array[left]; while (left < right) { // 从后向前搜索比 pivot 小的值 while (array[right] >= pivot && right > left) { --right; } // 比 pivot 小的放左边 array[left] = array[right]; // 从前向后搜索比 key 大的值 while (array[left] <= pivot && right > left) { ++left; } // 比 pivot 大的放右边 array[right] = array[left]; } // 左边都比 pivot 小，右边都比 pivot 大 // 将 pivot 放在游标当前位置。此时 left 等于 right array[left] = pivot; foreach (var i in array) { Console.Write("{0} ", i); } Console.WriteLine(); return right; } /// <summary> /// 左边小，右边大 /// </summary> /// <param name="array">排序数组</param> /// <param name="left">排序起始位置</param> /// <param name="high">排序结束位置</param> /// <returns></returns> public static void QuickSort(int[] array, int left, int right) { if (left >= right) return; // 完成一次单元排序 int index = SortUnit(array, left, right); // 对左边单元进行排序，递归 QuickSort(array, left, index - 1); // 对右侧单元进行排序，递归 QuickSort(array, index + 1, right); } static void Main(string[] args) { #region 快速排序算法 int[] array = { 149, 100, 112, 38, 80, 35, 615, 297, 592, 976, 143, 217 }; QuickSort(array, 0, array.Length - 1); Console.ReadLine(); #endregion }
性能分析
算法复杂度
快速排序的性能高度依赖于选择的基准值。
最糟糕的：O(n ^ 2)；
在最糟糕的情况下，栈长O(n)，在调用栈的每层都涉及O(n)个元素，完成每层所需的时间都为O(n)；O(n) * O(n) = O(n ^ 2)；
最佳的：O(n log n)；
在最佳的情况下，中间的元素作为基准值，栈长O(log n)；每一层运行时间为O(n)；O(n) * O(log n) = O(n log n)；
平均的：O(n log n)；
最佳即平均，只要每次都随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为O(n log n)。
快速排序是最快的排序算法之一。
稳定性：不稳定，如排序中有相同的值，排序也可交换亦不可交换；
注：快速排序原本是不稳定的排序方法，但若待排序记录中只有一组具有相同基准值的记录，而选择的轴值恰好是这组相同基准值中的一个，此时的快速排序就是稳定的。
稳定性判断条件：对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。