算法设计与分析 2.8 快速排序

/**********************************************************
快速排序的运行时间与划分是否对称有关。
1.其最坏情况是在划分的过程中产生两个区域分别包含 1 个和
n - 1 个元素的时候。由于partition的计算时间为 O(n) , 所以
如果算法partition每次都出现这种不对称的划分，复杂度为O(n^2)。

2.最好和平均都是 O(nlogn) 。
**********************************************************/
import java.util.Arrays;
public class QuickSort {
 public static void quickSort(int[] a, int p, int r) {
  if (p < r) {
      int q = partition(a, p, r);
   quickSort(a, p, q - 1);    //对左半段排序
   quickSort(a, q + 1, r);    //对右半段排序
  }
 }

 private static void swap(int[] a, int i, int j) {
  int temp = a[i];
  a[i] = a[j];
  a[j] = temp;
 }

 private static int partition(int[] a, int p, int r) {
  int u = a[p];       //以第一个元素为基准
  int i = p + 1;
  int j = r;
  for (; ; ) {       //将小于u的元素交换到左边，将大于u的元素交换到右边
   while (a[i] < u) {
       i++;
   }

   while (a[j] > u) {
       j--;
   }
        
   if (i >= j) {
       break;
   }
   swap(a, i, j);
  }
  a[p] = a[j];
  a[j] = u;
  return j;
 }

 public static void main(String[] args) {
  int[] a = {3, 4, 1, 5, 9, 3, 2, 8, 10};
  quickSort(a, 0, a.length - 1);
  System.out.println(Arrays.toString(a));
 }
}