快排和随机化算法

快速排序算法

QuickSort: Hoare 1962

• Divide and conquer
• sorts “in place”
• very pratical( with turning)

step 1: Divide: Patition array into 2 subarrays around pivot x
step 2: Recursively sort 2 subarrays
step 3: combine: trivial
key: linear-time partitioning subroutine

public int partition(int[] A, int left, int right){
    pivot = A[left];
  i = p;
  for(j=p+1; j<=q; j++){
      if(A[j]<pivot){
        i++;
      swap(A,i,j);
    }
  }
  swap(A,left, i+1);
  return i+1;
}

public void QuickSort(int[] A,int left, int right){
    if(left>right){
      int p = partition(A, left, right);
    QuickSort(A,left,p-1);
    QuickSort(A, p+1, right);
  }
}

Analysis

assume: all numbers distinct
T(n):
Worst-Case: **T(n)=T(n-1)+T(0)+Θ(n) = Θ(n^2)**

• input sorted or reversed sorted
• one side of partition has no elements

Best-Case analysis( intution only)
if we can really lucky, partition splits the array n/2, n/2, then T(n)=Θ(nlgn)
suppose: slipts is always 0.1:0.9 lucky
soppose: we alternate lucky, unlucky, lucky… lucky

随机化快速排序算法（Randomized QuickSort）

• the running time is independent of input ordering
• no assumption about the input distribution
• no specific input elicit worst-case behavior

• the worst-case is detemined only by a random-number generator

  在这种方法中，不是始终采用A[r]作为主元，而是从子数组A[p...r]中随机选择一个元素，即将A[r]与从A[p...r]中随机选出的一个元素交换。**即主元元素是随机选取的。**
  

  RANDOMIZED-PARTITION(A,p,r)
  i=random(p,r);
  swap(A,i,p);
  return partition(A,p,r);
  

  注意：关于时间复杂度证明的部分没看。