问题

对给定数组a[l ... r]排序.

方案

思路

分治. 先选一个数作为基准值, 然后小的放左边, 大的放右边.递归下去.

举个例子: 7 8 4 3 6 9 5 1 2

不妨选5作为基准值, 排一次成了这样: 4 3 1 2 5 7 8 6 9

由于左边<基准值<右边, 所以我们发现原来的问题变成了两个子问题, 即排序4 3 1 2和7 8 6 9.

递归求解即可.

基准值的选取

当然是中位数最优. 但找中位数本身很难. 所以我们选取位置在最左, 最右和中间的数的中位数来替代.

我们记这个值是v. 在上面的例子中, 即7 6 2的中位数’6’.

如何将数分在两侧

我们先把基准值和a[l]换一下位置.

记指针i代表a[l ... i - 1] < v,j代表a[j + 1 ... r] > v. 一开始取i = l, j = r.

再记’k’代表当前处理到了第k个元素, 并让k = l + 1(因为l处的元素就是基准值).

我们维护这样一件事:

l ... i - 1 小于v

i ... k - 1 等于v

k ... j 未处理

j + 1 ... r 大于v

那么当k > j时处理结束. 具体地:

如果a[k] > v, 把a[k]和a[j]互换位置, 并--j(把大的放到后面).

如果a[k] < v, 把a[k]和a[i]互换位置, 并++i, ++k(把小的放到前面).

如果a[k] == v, ++k.

这样便将数组里的数分在了基准值两侧.

递归过程

原来是l ... r, 现在只需要解决子问题l ... i - 1和j + 1 ... r.

l >= r时不再递归下去.

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

inline void cswap(int &a, int &b) { int c = a; a = b; b = c; }
inline void quick_sort(int *l, int *r)
{
	if (l >= r) return;
	int *i = l, *j = r, *k = l + ((r - l) >> 1);
	if (*k > *i) cswap(*i, *k);
	if (*k > *j) cswap(*j, *k);
	if (*i > *j) cswap(*i, *j);
	int v = *i; k = i + 1;
	while (k <= j)
	{
		if (*k > v) cswap(*j, *k), --j;
		else if (*k < v) cswap(*i, *k), ++i, ++k;
		else ++k;
	}
	quick_sort(l, i - 1);
	quick_sort(j + 1, r);
}

常见类型总结

其他

原理

弱酸弱碱盐在溶液中电离出的弱碱阳离子和弱酸酸根离子能发生相互促进的水解反应.
若水解产物能脱离体系, 则平衡不断正向移动, 反应到水解完全,即为完全双水解反应

常见的完全双水解反应

$Al^{3+}$和$HCO_3^-/CO_3^{2-}/AlO_2^-/SiO_3^{2-}/HS^-/S^{2-}/ClO^-$

$Fe^{3+}$和$HCO_3^-/CO_3^{2-}/AlO_2^-/SiO_3^{2-}/ClO^-$

$NH_4^+$和$SiO_3^{2-}/AlO_2^-$

常见的不是完全双水解反应的情况

$Fe^{3+}$和$HS^-/S^{2-}$的氧化还原反应

$Fe^{2+}/Cu^{2+}$等和$S^{2-}/CO_3^{2-}$等的沉淀反应

$AlO_2^-$和$HCO_3^-$的置换反应(强酸置弱酸)

多元弱酸

例1 $H_3PO_4$
$$H_3PO_4 \rightleftharpoons H_2PO_4^-+H^+$$

$$H_2PO_4^- \rightleftharpoons HPO_4^{2-}+H^+$$

$$HPO_4^{2-} \rightleftharpoons PO_4^{3-}+H^+$$

$$H_2O \rightleftharpoons H^++OH^-$$

$$c(H^+)>c(H_3PO_4)>c(H_2PO_4^-)>c(HPO_4^{2-})>c(PO_4^{3-})>c(OH^-)$$

多元弱酸的正盐

例2 $Na_2CO_3$
$$Na_2CO_3=2Na^++CO_3^{2-}$$

$$CO_3^{2-}+H_2O \rightleftharpoons HCO_3^-+OH^-$$

$$HCO_3^-+H_2O \rightleftharpoons H_2CO_3+OH^-$$

$$H_2O \rightleftharpoons H^++OH^-$$

$$c(Na^+)>c(CO_3^{2-})>c(OH^-)>c(HCO_3^-)>c(H_2CO_3)>c(H^+)$$

多元弱酸的酸式盐

例3 $NaHCO_3(pH>7)$
$$NaHCO_3=Na^++HCO_3^-$$

$$HCO_3^- \rightleftharpoons CO_3^{2-}+H^+$$

$$HCO_3^-+H_2O \rightleftharpoons H_2CO_3+OH^-$$

$$H_2O \rightleftharpoons H^++OH^-$$

$$K_{a2}<K_h$$

$$c(Na^+)>c(HCO_3^-)>c(OH^-)>c(H_2CO_3)>c(H^+)>c(CO_3^{2-})$$

例4 $NaHSO_3(pH<7)$

$$NaHSO_3=Na^++HSO_3^-$$

$$HSO_3^- \rightleftharpoons SO_3^{2-}+H^+$$

$$HSO_3^-+H_2O \rightleftharpoons H_2SO_3+OH^-$$

$$H_2O \rightleftharpoons H^++OH^-$$

$$K_{a2}>K_h$$

$$c(Na^+)>c(HSO_3^-)>c(H^+)>c(SO_3^{2-})>c(OH^-)>c(H_2SO_3)$$

abandon

verb

1. to leave sb, especially sb you are responsible for, with no intention of returning ~ sb to do sth

2. to leave a thing or place, especially because it is impossible or dangerous to stay ~ sth to sb/sth

3. to stop doing sth, especially before it is finished; to stop having sth

4. to stop supporting ir helping sb; to stop believing in sth
   Critics accused him of abandoning his principles.

5. ~ yourself to sth (literary) to feel an emotion so strongly that you can feel nothing else

   noun [U] (formal) an uncontroled way of behaving that shows that sb does not care what other people think with ~

abandoned

adj.

1. left and no longer wanted, used, or needed
2. (of people or their behaviour) wild; not following accepted standards

abandonment

noun [U] (formal)

1. the act of leaving a person, thing or place with no intention of returning
2. the act of giving up an idea or stopping an activity with no intention of returning to it

able

adj.

1. ~ to do sth (used as a modal verb) to have the skill, intelligence, opportunity, etc. needed to do sth
2. (abler, ablest) intelligent; good at sth

-able, -ible

suffix (in adjectives)

1. that can or must be
2. having the quality of

about

adv.

1. a little more or less than; a little before or after
2. nearly; very close to
3. (especially BrE) in many directions; here and there
4. (especially BrE) in no particular order; in various places
5. (especially BrE) doing nothing in particular
   People were standing about in the road.
6. (especially BrE) able to be found in a place
   There was nobody about.
7. (specialist or formal) facing the opposite direction
   He brought the ship about.
8. IDM
   that’s about all | that’s about it used to say that you have finished telling sb about sth and there is nothing to add

prep.

1. on the subject of sb/sth; in connection with sb.sth
   I don’t know what you’re on about(=talking about).
2. used to describe the purpose or an aspect of sth
   Movies are all about making money.
   What was all that about?(=what was the reason for what
   has just happened)
3. busy with sth; doing sth
   Everywhere people were going about their daily business.
   And while you’re about it…(=while you are doing that)
4. (especially BrE) in many directions in a place; here and there
5. (especially BrE) in various parts of a place; here and there
6. (especially BrE) next to a place or person; in the area memtioned
7. (literary) surrounding sb/sth
   She wore a shawl about her shoulders.
8. IDM
   • how/what about…?
     1. used when asking for information about sb/sth
     2. used to make a suggestion

adj.

1. IDM
   • be about to do sth to be close to doing sth; to be going to do sth very soon
   • not be about to do sth to not be willing to do sth; to not intend to do sth