直接访问数组排序按键而非值排序的工作原理及合理性探讨

这个算法的核心是利用键值直接作为数组索引来实现排序，具体步骤拆解：

• 先遍历原数组，找到所有元素的最大键值u，创建一个长度为u的空数组D——数组的每个索引对应一个可能的键值。
• 再遍历原数组中的每个元素x，把x直接放到D中索引等于x.key的位置。因为题目里明确键是唯一的，所以不会出现多个元素抢占同一个索引的情况。
• 最后从键值0开始，依次遍历D数组的每个索引：只要遇到非空的位置（也就是存放了元素的位置），就把这个元素按顺序放回原数组A。因为是按键值从小到大遍历的，所以最终A里的元素就是按键升序排列的。

你觉得它“只对键排序，没对值排序”是个误解——排序算法的本质是根据指定的规则（这里是键的大小），将元素集合重新排列成有序序列，这里的“有序”指的是元素满足规则的顺序，而元素本身是和键绑定在一起被排列的。

看代码就能明白：

• 我们从来没有单独提取键来排序，而是把整个元素和它的键绑定处理：把元素放到对应键的索引位置，再按键的顺序取出整个元素。
• 最终原数组A里的元素，是完整按键的升序排列的——每个元素的“值”（也就是元素本身）也跟着键的顺序被重新组织了。举个实际例子：
  假设A里的元素是[{'key':3, 'val':'apple'}, {'key':1, 'val':'banana'}, {'key':2, 'val':'cherry'}]
  经过算法处理后，A会变成[{'key':1, 'val':'banana'}, {'key':2, 'val':'cherry'}, {'key':3, 'val':'apple'}]
  你看，不是只排了键，而是整个元素都按键的顺序排好了。

这个算法完全符合排序算法的定义：将一组元素按照指定的比较规则（键的大小），排列成有序的集合。

内容的提问来源于stack exchange，提问作者csy