Table-Sort

  表排序...

表排序

• 某些场景，移动元素的成本比较大，元素移动的时间是不可以俘忽略的，为了节省时间，我们不得不寻求其他的办法。
  • 定义一个指针数组作为"表"（table）
• 概述，存在表A，存储的是对应的关键字，每个关键字代表具体的实体，我们根据关键字进行排序，这样省去额外的数据交换的时间。
  • 我们定义一个新的部分table记录数组中每个元素的下标

A	A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]	A[9]
Key	f	d	c	a	g	b	h	e	i	u
table	0	1	2	3	4	5	6	7	8	9

• • 初始状态下，table[index] 等于A 的index
  • 然后我们同通过任意一种排序比较A[table]对应的关键字的大小，从而交换table中的值——排序

• 排序结果 -- 使用插入排序

  A	A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]	A[9]
  Key	f	d	c	a	g	b	h	e	i	u
  table	0	1	2	3	4	5	6	7	8	9
  第零次插入	0
  第一次插入	1	0
  第二次插入	2	1	0
  第三次插入	3	2	1	0
  第四次插入	3	2	1	0	4
  第五次插入	3	5	2	1	0	4
  第六次插入	3	5	2	1	0	4	6
  第七次插入	3	5	2	1	7	0	4	6
  第八次插入	3	5	2	1	7	0	4	6	8
  第九次插入	3	5	2	1	7	0	4	6	8	9
  table	3	5	2	1	7	0	4	6	8	9

• 到此，上述表变得有序：

• 正确的输出结果是:

  • A[table[0]],A[table[0]]........