某储备粮的“学习笔记” - quicksort 2011-04-06T08:12:26+08:00 Typecho http://blog.gregwym.info/feed/atom/tag/quicksort/ <![CDATA[CS 240复习总结之三: Sorting and Randomized Algorithms]]> http://blog.gregwym.info/cs-240-fu-xi-zong-jie-zhi-san--sorting-and-randomized-algorithms.html 2011-04-06T08:12:26+08:00 2011-04-06T08:12:26+08:00 咳嗽di小鱼 http://blog.gregwym.info 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个片段xd-1xd-2… x, 且任一片段xi满足0 <= xi < k
例如: 十进制数的每一位都是0 <= xi < 9的单位数字
思路: 以每一个xi为基准 (从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/

]]>