转载

理解快速排序算法

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

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

步骤为：

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

效果图如下：

理解快速排序算法

partition方法

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

 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循环里的工作。

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

   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的时候停止，然后交换两个数。

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

完整的快排算法

 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 ² )

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