#import "../template.typ": *
#import "@preview/tablex:0.0.7": tablex, colspanx, rowspanx
#import "@preview/tablem:0.1.0": tablem

#show: project.with(
  title: "5",
  authors: (
    "absolutex",
  )
)

= 排序
== 课本2.3-1 使用图2-4作为模型，说明归并排序在数组A=\<3，41，52，26，38，57，9，49\>上的操作。

（不好画图）

#tablex(
  columns: 8,
  align: center + horizon,
  colspanx(8)[3 9 26 38 41 49 52 57], (), (), (), (), (), (), (), 
  colspanx(4)[3 26 41 52], (), (), (), colspanx(4)[9 38 49 57], (), (), (), 
  colspanx(2)[3 41], (), colspanx(2)[26 52], (), colspanx(2)[38 57], (), colspanx(2)[9 49], (), 
  [3], [41], [52], [26], [38], [57], [9], [49],
)

== 课本7.1-1 参照图7-1的方法，说明PARTITION在数组A=\<13，19，9，5，12，8，7，4，21，2，6，11>上的操作过程。

加粗的与斜体的表示参照图7-1的阴影区域。红色的是x。

斜体的为浅阴影($<=x$)，粗的为深阴影($>x$)

#tablex(
  columns: 12,
  align: center + horizon,
  auto-vlines: false,
  map-cells: cell => {
    if get_text(cell.content) == "11" {
      cell.content = {
        set text(red.lighten(30%))
        strong(cell.content)
      }
    }
    cell
  },
  [*13*],[*19*],[9],[5],[12],[8],[7],[4],[21],[2],[6],[11],
  [_9_],[*13*],[*19*],[5],[12],[8],[7],[4],[21],[2],[6],[11],
  [_9_],[_5_],[*13*],[*19*],[12],[8],[7],[4],[21],[2],[6],[11],
  [_9_],[_5_],[*13*],[*19*],[*12*],[8],[7],[4],[21],[2],[6],[11],
  [_9_],[_5_],[_8_],[*13*],[*19*],[*12*],[7],[4],[21],[2],[6],[11],
  [_9_],[_5_],[_8_],[_7_],[*13*],[*19*],[*12*],[4],[21],[2],[6],[11],
  [_9_],[_5_],[_8_],[_7_],[_4_],[*13*],[*19*],[*12*],[21],[2],[6],[11],
  [_9_],[_5_],[_8_],[_7_],[_4_],[*13*],[*19*],[*12*],[*21*],[2],[6],[11],
  [_9_],[_5_],[_8_],[_7_],[_4_],[_2_],[*13*],[*19*],[*12*],[*21*],[6],[11],
  [_9_],[_5_],[_8_],[_7_],[_4_],[_2_],[_6_],[*13*],[*19*],[*12*],[*21*],[11],
  [_9_],[_5_],[_8_],[_7_],[_4_],[_2_],[_6_],[11],[*13*],[*19*],[*12*],[*21*],
)

== 课本8.2-1 参照图8-2的方法，说明COUNTING-SORT在数组A=\<6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2>上的操作过程。

原先：
#tablem[
  |*a*|6|0|2|0|1|3|4|6|1|3|2|
]
#tablem[
  |*c*|0|0|0|0|0|0|0|
]

计数并累加：

#tablem[
  |*a*|6|0|2|0|1|3|4|6|1|3|2|
]
#tablem[
  |*c*|2|4|6|8|9|9|11|
]

填入：
1. 

#tablem[
  |*b*|x|x|x|x|x|2|x|x|x|x|x|
]#tablem[
  |*c*|2|4|5|8|9|9|11|
]

2. 

#tablem[
  |*b*|x|x|x|x|x|2|x|x|3|x|x|
]#tablem[
  |*c*|2|4|5|7|9|9|11|
]

3. 

#tablem[
  |*b*|x|x|x|1|x|2|x|x|3|x|x|
]#tablem[
  |*c*|2|3|5|7|9|9|11|
]

...

最后：

#tablem[
  |*b*|0|0|1|1|2|2|3|3|4|6|6|
]

== 课本8.3-1 参照图8-3的方法，说明RADIX-SORT在下列英文单词上的操作过程：COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX.

第一次：

#tablex(
  columns: 3,
  align: center + horizon,
  map-cells: cell => {
    if cell.x == 2 {
      cell.content = {
        set text(red.lighten(30%))
        strong(cell.content)
      }
    }
    cell
  },
  [S],[E],[A],
  [T],[E],[A],
  [M],[O],[B],
  [T],[A],[B],
  [D],[O],[G],
  [R],[U],[G],
  [D],[I],[G],
  [B],[I],[G],
  [B],[A],[R],
  [E],[A],[R],
  [T],[A],[R],
  [C],[O],[W],
  [R],[O],[W],
  [N],[O],[W],
  [B],[O],[X],
  [F],[O],[X],
)

第二次：

#tablex(
  columns: 3,
  align: center + horizon,
  map-cells: cell => {
    if cell.x == 1 {
      cell.content = {
        set text(red.lighten(30%))
        strong(cell.content)
      }
    }
    cell
  },
  [T],[A],[B],
[B],[A],[R],
[E],[A],[R],
[T],[A],[R],
[S],[E],[A],
[T],[E],[A],
[D],[I],[G],
[B],[I],[G],
[M],[O],[B],
[D],[O],[G],
[C],[O],[W],
[R],[O],[W],
[N],[O],[W],
[B],[O],[X],
[F],[O],[X],
[R],[U],[G],
)

第三次：

#tablex(
  columns: 3,
  align: center + horizon,
  map-cells: cell => {
    if cell.x == 0 {
      cell.content = {
        set text(red.lighten(30%))
        strong(cell.content)
      }
    }
    cell
  },
  [B],[A],[R],
[B],[I],[G],
[B],[O],[X],
[C],[O],[W],
[D],[I],[G],
[D],[O],[G],
[E],[A],[R],
[F],[O],[X],
[M],[O],[B],
[N],[O],[W],
[R],[O],[W],
[R],[U],[G],
[S],[E],[A],
[T],[A],[B],
[T],[A],[R],
[T],[E],[A],
)



== 课本8.4-1 参照图8-4的方法，说明BUCKET-SORT在数组A=\<0.79，0.13，0.16，0.64，0.39，0.20，0.89，0.53，0.71，0.42>上的操作过程。

10 个桶，每个桶范围为 0.1

```
[
[]
[ 0.13, 0.16 ]
[ 0.2 ]
[ 0.39 ]
[ 0.42 ]
[ 0.53 ]
[ 0.64 ]
[ 0.71, 0.79 ]
[ 0.89 ]
[]
]
```

== 假设对于n个不同的元素$x_1,x_2...x_n$有正加权值$w_1,w_2...w_n$，有$sum(w_i)=1$，我们定义加权中位数$x_k$为满足以下条件的元素：
$sum_(x_i<x_k) w_i<1/2$ 且 $sum_(x_i>x_k) w_i>=1/2$

=== (a) 证明，当$w_i=1/n$时，$x_1,x_2...x_n$的中位数是加权中位数。

中位数的左边和右边的数字个数 $<= floor(n/2)$。因此每一边的数字的权和 $<= 1/2$

=== (b)设计一种基于排序的算法求解加权中位数，要求其最差算法复杂度小于$O(n lg n)$。证明设计算法的时间复杂度

首先对元素按照其值进行排序，然后计算加权前缀和，直到找到第一个加权前缀和大于等于 1/2 的元素。这个元素就是加权中位数。

该算法的时间复杂度分为排序和计算加权前缀和两个部分。排序的时间复杂度为$O (n log n)$，而计算加权前缀和的时间复杂度为$O (n)$。因此，总体时间复杂度为 $O (n log n)$

=== (c) 考虑一维快递中心选址问题。我们给出n个不同点$p_1,p_2...p_n$（即n个数值），分别拥有权重$w_1,w_2...w_n$，我们需要找到一个点p（p可以是任意一个点，不一定是n个给定点中的一个），要求最小化$sum_(i=1)^n w_i d(p,p_i)$，这里d是距离，定义为$p-p_i$。证明， 序列的加权中位数即是所求的p点。（提示：p这里是连续变量，其导数为0时，有极值）

$ f(p)=sum_(i=1)^n w_i |p-p_i| $

$ f'(p)=sum_(i=1)^n w_i "sgn"(p-p_i) = sum_(x_i<p) w_i - sum_(x_i>p) w_i $ 

当 p 为加权中位数时，$sum_(x_i<p) w_i$ 与 $sum_(x_i>p) w_i$ 最接近，得 $f'(p)$ 最小，即为 $f(p)$ 的极值。

=== (d) 进一步的，我们考虑二维的快递中心选址问题，此时$p_i=(x_i,y_i)$，采用曼哈顿距离$d(p,p_i)=|x-x_i|+|y-y_i|$。给出一种算法复杂度为$O(n lg n)$的算法来解决该问题，写出相应的伪代码。

#include_code("算法导论/code/sort-3.py")

== （不做要求）课本第2章思考题：2-1。这道思考题实际上就是Timsort的介绍。请大家思考这个问题，完成习题部分，以及给出伪代码（或是程序）。

== （leetcode题目）leetcode 题库 88、21、23、147、148、41、75、34、74。

https://github.com/lxl66566/OJ/tree/main/leetcode_cn