文章来源: http://thunderfyc.wordpress.com.cn/ 

I Foundations
  2 Getting Started
    Merge Sort
      Problem
        Inversion
        求逆序对数可以用 归并排序 方法 用个back[i]记录 第i个数字后面有多少比它小的 在归并排序的时候 轮到这个数字插入的话 就把这个值加上它后面那组数已经插入的个数就可以了

  3 Growth of Functions
      f(n) = Ｏ(g(n))  fn <= cgn
      f(n) = Ω(g(n))  fn >= cgn
      f(n) = Θ(g(n))  c1gn <= fn <= c2gn
      f(n) = ｏ(g(n))  fn/gn -> 0
      f(n) = ω(g(n))  fn/gn -> ∞

  4 Recurrences
    The master method
      T(n) = aT(n/b) + f(n) [a>=1 b>0]
      Case 1  [f(n) = Ｏ(n^(lga/lgb - c)) c>0] T(n) = Θ(n^(lga/lgb))
      Case 2  [f(n) = Θ(n^(lga/lgb))] T(n) = Θ(n^(lga/lgb)*lgn)
      Case 3  [f(n) = Ω(n^(lga/lgb + c)) c>0; af(n/b) <= cf(n) c<1] T(n) = Θ(f(n))

    Finding the Missing Integer
    在1-n的自然数中去掉一个数 每次可以问第i个数的第j二进制位 问O(n)算法
    把n补全到2^k-1 那么每一位的01都是等量的 那么第一次询问最后一位 就能判断失踪数的末位 然后再在末位相同的数中询问 确定失踪数的次末位 于是确定 询问次数T(n) = T(n/2)+n

  5 Probabilistic Analysis and Randomized Algorithms
    Randomly permuting arrays
       P[i] = random(1,n^3) 然后以P为关键字对A排序
       或者从第1位到第n位 随机在(i,n)中找一个与i交换

文章来源: http://thunderfyc.wordpress.com.cn/

II Sorting and Order Statistics
  6 Heapsort
    Binary Heap
      根1 左儿子 2i 右儿子 2i+1 从根往下调或者从下往根调就好了

    Priority Queue
      就是用堆来做队列用

    K Merge
      把k个排好序的序列归并
      维护容量为K的堆 每次弹最小的 弹出一个 补进一个该序列的 时间O(nlgk)

  7 Quicksort
    就是找到轴 小的放左边 大的放右边 然后把左边右边的再操作
    但是快排最糟情况是Θ(n^2) 所以 我们可以或者把输入数据重新随机声称排列 或者找轴的时候随机

  8 Sorting in Linear Time
    Lower bounds for sorting
      基于decision-tree model的排序算法都是Ω(nlgn)的

    Counting Sort
      对于整数的 在数组里面记录某个整数出现多少次 顺序输出即可

    Radix Sort
      先对个位数排序 再对十位数排序 保持稳定 依次类推

    Bucket Sort
      设置若干个桶 如果数字在桶的区间范围内 就插入

    Water Jugs
      红蓝若干瓶子 一一配成容量相同的对子 只能用灌满A瓶倒B瓶的方法来判断 要配对
      随机取一个红瓶子 红瓶子和其他红瓶子比 把小的放左边大的方右边 红瓶子和蓝瓶子比小的放左边 大的放右边 配对的输出 然后再小的和小的比 大的和大的比

    Average Sorting
      每K位的平均值单调 求排序
      a[i] <= a[i+k] 分组后排序 然后归并即可

  9 Medians and Order Statistics
      把数组分为n/5组 找到每组中位数 对每组中位数 递归找中位数

    提升Quicksort 每次Quicksort的时候 查找中位数 然后递归 T(n)<=2T(n/2)+O(n) = O(nlgn)

    Largest i numbers in sorted order
      维护一个容量为i的大根堆

    Weighted Median
      Σwi<1/2 [xi<xk]  Σwi<=1/2 [xi>xk]
      找到序列中位数作为基准 如果左边权值小就把左边的权值加到中位数上 然后查找右边 反之亦然

    post-office location problem
      平面上点 已知权重 找到最优点 距离为Manhattan距离 d(a,b) = |x1-x2|+|y1-y2|
      min(f,y) = min(h(x)+g(y)) = min(h(x)) + min(g(y))

文章来源: http://thunderfyc.wordpress.com.cn/