算法导论公开课笔记（二）快速排序和随机化算法

快速排序

与归并排序一样，快速排序也使用了分治的思想解决排序问题。
对一个典型的子数组A[p..r]进行快速排序的三步分治过程：

• 分解：数组A[p..r]被划分为两个（可能为空）子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每一个元素都小于等于A[q],而A[q]也小于等于A[q+1..r]中的每个元素。其中计算下标q也算划分过程的一部分。
• 解决： 通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]进行排序。
• 合并：因为子数组都是原址排序，所以不需要额外的合并操作：数组A[p..r]已经有序。

伪代码实现快速排序：

QUICKSORT(A,p,r)
  if p < r
    q=PARTITION(A,p,r)
     QUICKSORT(A,p,q-1)
     QUICKSORT(A,q+1,r)

Java实现版：

    /**
     * 
     * @param src 待排序的数组
     */
    public static void quickSort(int[] src,int left ,int right){
        if(left<right){
            int mid=partition(src, left, right);
            quickSort(src, left, mid-1);
            quickSort(src, mid+1, right);
        }
    }

数组的划分
算法的关键部分就是PARTITION过程，它实现了对子数组A[p..r]的原址重排。

PARTITION(A,p,r)
  x=A[r]
  i=p-1
  for j=p to r-1
    if A[j]<=x
      i=i+1
      exchange A[i] with A[j]
  exchange A[i+1] with A[r]
  return i+1

快速排序的划分和过程 快速排序分解过程

Java实现版：

    /**
     * 划分操作
     * 
     * @param src
     *            待排序的数组
     * @param left
     *            左边界
     * @param right
     *            右边界
     */
    public static int partition(int[] src, int left, int right) {   
    
        int key = src[left];//挖坑
        int i = left;
        int j = right;
        while (i < j) {
            while (i < j && src[j] > key) {
                j--;
            }
            
            if (i < j) {
                src[i++] = src[j];// 挖坑填数
            }

            while (i < j && src[i] < key) {
                i++;
            }
            
            if (i < j) {
                src[j--] = src[i];// 挖坑填数
            }

        }
        src[i] = key;//填空

        // 这种情况下第一趟结束 i的坐标都比他小i的右边都比他大
        return i;

    }

随机化版本的快速排序

在理解了快速排序的划分过程之后，随机化快速排序的过程就很好理解了。
首先随机化快排是为了解决出现最坏情况时 Ω（n^2）的运行时间的问题，将快速排序变成一个“稳定”的算法，随机化后，快排的期望运行时间为O(n* lg n)。
随机化快排其实做的很简单，就是在划分的时候，不是确定性的选择主元（provit），而是随机的选择主元，这要就保证了只有很小的几率下每次都出现最坏的划分情况。
随机化快排的划分过程：

    /**
     * 随机划分操作
     * 
     * @param src
     *            待排序的数组
     * @param left
     *            左边界
     * @param right
     *            右边界
     */
    public static int randomizedPartition(int[] src, int left, int right) {

        /*随机选取主元元素*/
        Random random = new Random();
        int random_index = random.nextInt(right-left+1)+left;
        System.out.println("random_index="+random_index);
        
        /**
         * 交换
         */
        int temp = src[random_index];
        src[random_index] = src[left];
        src[left]=temp;
        
        int key = src[left];//挖坑
        int i = left;
        int j = right;
        while (i < j) {
            while (i < j && src[j] > key) {
                j--;
            }
            
            if (i < j) {
                src[i++] = src[j];// 挖坑填数
            }

            while (i < j && src[i] < key) {
                i++;
            }
            
            if (i < j) {
                src[j--] = src[i];// 挖坑填数
            }

        }
        src[i] = key;//填空

        // 这种情况下一趟结束 i的坐标都比他小i的右边都比他大
        return i;

    }

以上，谢谢阅读，希望你有所收获！

算法导论公开课笔记（一）算法分析与设计
算法导论公开课笔记（二）快速排序和随机化算法
算法导论公开课笔记（三）线性时间排序
算法导论公开课笔记（四）顺序统计、中值
动态规划算法