概念

分治，将较大规模的问题分解成几个较小规模的问题。
例子：猜数字游戏，从几楼扔下手机不会摔坏，查找C盘中最大的文件，黄页电话簿，翻字典。

快速排序(先找分界点再递归)

  1. // 学习目标：理解好分治的过程，讲解理论用处多，实际应用比较少
  3. void quick_sort(int q[], int l, int r)
  4. {
  5.     if (l >= r) return;
  7.     int i = l - 1, j = r + 1, x = q[l + r >> 1];
  8.     while (i < j)
  9.     {
  10.         do i ++ ; while (q[i] < x);
  11.         do j -- ; while (q[j] > x);
  12.         if (i < j) swap(q[i], q[j]);
  13.     }
  14.     quick_sort(q, l, j), quick_sort(q, j + 1, r);
  15. }

例题：输出前k大的数

归并排序(先递归再合并)

  1. // 学习目标：理解过程，实际应用会灵活多变
  3. void merge_sort(int q[], int l, int r)
  4. {
  5.     if (l >= r) return;
  7.     int mid = l + r >> 1;
  8.     merge_sort(q, l, mid);
  9.     merge_sort(q, mid + 1, r);
  11.     int k = 0, i = l, j = mid + 1;
  12.     while (i <= mid && j <= r)
  13.         if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
  14.         else tmp[k ++ ] = q[j ++ ];
  16.     while (i <= mid) tmp[k ++ ] = q[i ++ ];
  17.     while (j <= r) tmp[k ++ ] = q[j ++ ];
  19.     for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
  20. }

例题：【例7.7】光荣的梦想