Comparison-based sorting

最优Runtime为Ω(n log n)

QuickSelect

用QuickSort algorithm快速查找第k大的数 (avg rumtime: Θ(n))

组成函数

• choose-pivot(A) 在数据中选择其中一个作为pivot
• partition(A, p) 使用A[p]作为pivot, 将A中的数据分为
  
  
  • 所有小于等于pivot的数据
  • pivot本身
  • 所有大于pivot的数据

Implementation

下载: quickselect.cc

void swap(int *A, int i, int j){ 
    int temp; 
    temp = A[i]; 
    A[i] = A[j]; 
    A[j] = temp; 
    return; 
}

• partition(A, p)
  思路: 逐次将最外侧的一对不符合partition规则的item对调

  
  
  

   int partition(int *A, int p, int n){ 
       swap(A, 0, p); 
       int i = 1, j = n - 1; 
       while(i <= j){ 
           while(A[i] <= A[0] && i < n) i++; 
           while(A[j] > A[0] && j > 0) j--; 
           if(i <= j) swap(A, i, j); 
       } 
       swap(A, 0, j); 
       return j; 
   } 
  

• quick-select(A, k)
  思路: 以partition分组数据以后, 判断第k大的数所在的分组, 然后recall其本身, 达到持续缩小搜索范围的目的

  
  
  

  int quickSelect(int *A, int k, int n){ 
      int p = 0; 
      int i = partition(A, p, n); 
      if(i == k) return A[i]; 
      else if(i > k) return quickSelect(A, k, i); 
      else if(i < k) return quickSelect(A+i+1, k-i-1, n-i-1); 
      return -1; 
  }
  

• choose-pivot(A)
  思路1: 永远取第一个item为pivot
  思路2: 取从0到n-1之间的随机数为pivot

QuickSort

快速排序(分治法)
avg rumtime: Θ(n log n)

• 结构与QuickSelect基本相同

• 区别: 需要对partition分出的两组数据都进行排序

  
  
  

   void quickSort(int *A, int n){ 
       if(n <= 1) return; 
       int p = 0; 
       int i = partition(A, p, n); 
       quickSort(A, i); 
       quickSort(A + i + 1, n - i - 1);
   } 
  

Non-comparison-based sorting

最优Runtime为O(n)

Counting Sort

前提: Array A包含n个数据, 数据的最大值小于k

思路:

• 建立一个大小为k的空白Array C, 填零.
• 将从0到k, 每一个数字在 A 出现的次数, 填到 C 对应的index中
• 从1到k, 将 C 中的数字逐次累加 C[i] = C[i] + C[i - 1]
• 则C[i]为任意A[x] == i, 在排序后应该在的index

Runtime: O(n)
Space: Θ(k)

下载: countingsort.cc

void countingSort(int *A, int k, int n){ 
    int i, B[n], C[k]; 
    for(i = 0; i < n; i++){ 
        C[A[i]]++; 
        B[i] = A[i]; 
    } 
    for(i = 1; i < k; i++) C[i] = C[i] + C[i-1]; 
    for(i = n-1; i >= 0; i--){ 
        C[B[i]]--; 
        A[C[B[i]]] = B[i]; 
    } 
    return; 
}

Radix sort

前提: Array A包含的数据均可拆分成d个片段x_d-1x_d-2… x, 且任一片段x_i满足0 <= x_i < k
例如: 十进制数的每一位都是0 <= x_i < 9的单位数字
思路: 以每一个x_i为基准 (从0到d - 1), 运行counting sort.

Runtime: Θ(d(n+k))
Space: Θ(n+k)

注: 如果以从d-1到0的顺序执行, 则是以最低位为基准(LSD). 正常是以最高位为基准(MSD).

更新1: 各种Sorting Algorithm的动画演示http://jsdo.it/norahiko/oxIy/fullscreen
更新2: 修正了partition中的bug

更多CS 240总结请看: http://blog.gregwym.info/tag/cs240/