理解快速排序算法

快速排序在平均状况下，排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比 其他Ο(n log n)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

步骤为：

1.从数列中挑出一个元素，称为”基准”（pivot）， 2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition ）操作。 3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

效果图如下：

partition方法

partition方法是快速排序算法的核心，下面先写一个简单的原地（in-place）分区的版本。

[代码]java代码：

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

public class Test1   {     public static void main(String   args[]) {             int[]   a = {354,656,21,2342,65,657,76,12,54,778,50,31,333,45,56,86,97,121} ;             System.out.print(partition(a,2))   ;     }     static int partition(int arr[], int pivotIndex)     {         int start = 0 ;         int end = arr.length - 1 ;         int pivot = arr[pivotIndex];         swap(arr,pivotIndex,   end);         int storeIndex = start;         for(int i = start; i < end; ++i) {             if(arr[i]   < pivot) {                 swap(arr,i,   storeIndex);                 ++storeIndex;             }         }         swap(arr,storeIndex,   end);         return storeIndex;     }     public  static    void    swap ( int [] data,  int  a,  int  b) {         int  t = data [a];         data   [a] = data [b];         data   [b] = t;     } }

 

首先注意swap方法，swap方法用于交换数组中的两个元素。

partition当中调用了三次swap，我们随机选中一个位置作为”基准”（pivot）,第一次交换就是把这个pivot交换到数组最后一位。 第三次当然就是把它从最后一位交换到它应该在的位置。中间的for循环是这个方法的核心。

storeIndex就是最后pivot摆放的位置。storeIndex前面的元素都比pivot小，storeIndex之后的元素都比pivot大。 所以我们从第一个元素遍历到最后一个，目的是把全部元素分成两段，storeIndex位于两段中间，第一段全部是是小于pivot的元素， 第二段都是大于pivot的元素，完成分段之后在把pivot从最后一个位置交换到两段中间。 循环时发现元素小于pivot，就把元素移动到后半段子序列的开头，然后把后半段开头的标记位storeIndex＋1。这就是for循环里的工作。

要注意的是，一个元素在到达它的最后位置前，可能会被交换很多次。 下面对原地分区的版本进行优化如下：

[代码]java代码：

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19

static int partition(int arr[], int pivotIndex)     {         int start = 0 ;         int end = arr.length -1;         int mid = arr[pivotIndex];         int left = start, right = end - 1;         while (left < right) {             while (arr[left] < mid && left <   right)                 left++;             while (arr[right] >= mid && left   < right)                 right--;             swap(arr,left,   right);         }         if (arr[left] >= arr[end])             swap(arr,left,   end);         else             left++;         return left;     }

 

现在我们采用了两个指针，对应两个子while循环，一个从前向后遍历，一个从后向前遍历。从前向后遍历时遇到大于基准数pivot的时候停止， 从后向前遍历时遇到小于基准数pivot的时候停止，然后交换两个数。

一旦我们有了这个分区算法，要写快速排列本身就很容易。

完整的快排算法

[代码]java代码：

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

public class Test2   {     static int[] arr  ;     private static void swap(int x, int y) {         int temp = arr[x];         arr[x]   = arr[y];         arr[y]   = temp;     }     private static void quick_sort_recursive(int start, int end) {         if (start >= end)             return;         int mid = arr[end];         int left = start, right = end - 1;         while (left < right) {             while (arr[left] < mid && left <   right)                 left++;             while (arr[right] >= mid && left   < right)                 right--;             swap(left,   right);         }         if (arr[left] >= arr[end])             swap(left,   end);         else             left++;         quick_sort_recursive(start,   left - 1);         quick_sort_recursive(left   + 1, end);     }     public static void sort(int[]   arrin) {         arr   = arrin;         quick_sort_recursive(0,   arr.length - 1);     }     public static void main(String   args[]) {         int[]   a =  {354,656,21,2342,65,657,76,12,54,778,50,31,333,45,56,86,97,121} ;         sort(a);         System.out.print(Arrays.toString(arr));     } }

 

算法分析

快速排序的时间主要耗费在划分操作上，对长度为 k 的区间进行划分，共需 k-1 次关键字的比较。

最坏时间复杂度

最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)， 而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。 因此，快速排序必须做 n-1 次划分， 第i次划分开始时区间长度为 n-i+1，所需的比较次数为 n-i(1≤i≤n-1)，故总的比较次数达到最大值：Cmax = n(n-1)/2=O(n^2)

如果按上面给出的划分算法，每次取当前无序区的第 1 个记录为基准，那么当文件的记录已按递增序(或递减序)排列时， 每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录，则快速排序所需的比较次数反而最多。

最好时间复杂度

在最好情况下，每次划分所取的基准都是当前无序区的”中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。 总的关键字比较次数：O(nlgn)

注意： 用递归树来分析最好情况下的比较次数更简单。因为每次划分后左、右子区间长度大致相等，故递归树的高度为 O(lgn)， 而递归树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过n，故整个排序过程所需要的关键字比较总次数 C(n)=O(nlgn)。

因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为 O(n^2)，最好时间复杂度为 O(nlgn)。

平均时间复杂度

尽管快速排序的最坏时间为 O(n^2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。 它的平均时间复杂度为 O(nlgn)。

基准关键字的选取

在当前无序区中选取划分的基准关键字是决定算法性能的关键。

1.”三者取中”的规则

“三者取中”规则，即在当前区间里，将该区间首、尾和中间位置上的关键字比较，取三者之中值所对应的记录作为基准， 在划分开始前将该基准记录和该区伺的第1个记录进行交换，此后的划分过程与上面所给的 Partition 算法完全相同。

2.取位于 low 和 high 之间的随机数k(low≤k≤high)，用 R[k] 作为基准

选取基准最好的方法是用一个随机函数产生一个取位于 low 和 high 之间的随机数 k(low≤k≤high)，用 R[k] 作为基准， 这相当于强迫R[low..high]中的记录是随机分布的。用此方法所得到的快速排序一般称为随机的快速排序。

注意： 随机化的快速排序与一般的快速排序算法差别很小。但随机化后，算法的性能大大地提高了，尤其是对初始有序的文件， 一般不可能导致最坏情况的发生。算法的随机化不仅仅适用于快速排序，也适用于其它需要数据随机分布的算法。

空间复杂度

快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为 O(lgn)，故递归后需栈空间为 O(lgn)。 最坏情况下，递归树的高度为 O(n)，所需的栈空间为 O(n)。

原文链接：http://www.apkbus.com/blog-705730-60777.html