目录

一 基本思想二 例子三 复杂度分析

一 基本思想

通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

二 例子

class QuickSort { public static void Sort(int[] array) { QSort(array, 0, array.Length - 1); } private static void QSort(int[] array, int low, int high) { int middle; if (low < high) { middle = Partiton(array, low, high); QSort(array, low, middle); QSort(array, middle + 1, high); } } private static int Partiton(int[] array, int low, int high) { int temp = array[low]; //设定一个参考值 while (low < high) // 当 low =high 时， 所有比参考值小的都在左边， 比参考值大的都在右边， low就是参考值的下标 { while (low < high && array[high] >= temp) //先从后往前找， 找到第一个比参考值小的坐标 { high--; } array[low] = array[high];// 把当前找到的比参考值大的放在左边。 while (low < high && array[low] <= temp) //然后从前往后找， 找到比参考值大的 { low++; } array[high] = array[low];// 把当前找到的比参考值大的放在右边。 } array[low] = temp; return low; } }

三 复杂度分析

最优的情况（每次都是对半分），时间复杂度是 O(nlog₂n)。最坏的情况，数据是正序或者逆序， 每次划分只得到一个比上一次划分少一个记录的子序列，另一个为空， 所以需要划分 n - 1 次， 而且 第 i 次划分 需要经过 n - i 次比较才能找到第 i 个记录， 因此比较次数为 （n-1） + （n-2）+ ``````+ 1 = n(n-1)/2.。也就是时间复杂度为O(n²)。平均情况下， 时间复杂度为O(nlog₂n)。空间复杂度，主要是递归造成的栈空间的使用， 最好情况，递归树的深度是log₂n， 空间复杂度O(log₂n)， 最坏情况， 需要进行n-1次递归， 空间复杂度是O(n)。平均情况是O(log₂n)。