快速排序

快速排序是一种常用的排序算法，采用分治法（Divide and Conquer）的思想。它的基本步骤如下：

1. 从数列中挑出一个元素，称为“基准”（pivot）。
2. 将所有比基准值小的元素都放在基准前面，比基准值大的元素都放在基准的后面（相同的数可以放在任一边）。在这个分区退出之后，该基准就处于数列的中间位置。
3. 对基准的左右两个分区重复步骤1和步骤2。
   快速排序的关键步骤是基准的选取，不同的选取方法会影响排序的效率。通常有以下几种选取方法：
   • 选取第一个元素作为基准
   • 选取最后一个元素作为基准
   • 选取中间元素作为基准
   • 从数列中随机选取一个元素作为基准

快速排序的时间复杂度为O(nlogn)，但在最坏情况下时间复杂度为O(n^2)。为了避免最坏情况的发生，可以采用随机选取基准、三数中值法选取基准等优化方法。

public class QuickSort {

   /*
    * 快速排序
    *
    * 参数说明：
    *     a -- 待排序的数组
    *     l -- 数组的左边界(例如，从起始位置开始排序，则l=0)
    *     r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
    */
   public static void quickSort(int[] a, int l, int r) {

      if (l < r) {
         int i,j,x;

         i = l;
         j = r;
         x = a[i];
         while (i < j) {
            while(i < j && a[j] > x)
               j--; // 从右向左找第一个小于x的数
            if(i < j)
               a[i++] = a[j];
            while(i < j && a[i] < x)
               i++; // 从左向右找第一个大于x的数
            if(i < j)
               a[j--] = a[i];
         }
         a[i] = x;
         quickSort(a, l, i-1); /* 递归调用 */
         quickSort(a, i+1, r); /* 递归调用 */
      }
   }

   public static void main(String[] args) {
      int i;
      int a[] = {30,40,60,10,20,50};

      System.out.printf("before sort:");
      for (i=0; i<a.length; i++)
         System.out.printf("%d ", a[i]);
      System.out.printf("\n");

      quickSort(a, 0, a.length-1);

      System.out.printf("after  sort:");
      for (i=0; i<a.length; i++)
         System.out.printf("%d ", a[i]);
      System.out.printf("\n");
   }
}