对数值范围为 0到 n^2-1的 n 个整数进行排序。请详细

[问答题]

对数值范围为 0到 n^2-1的 n 个整数进行排序。请详细描述算法（若引用经典算法也需要给出具体实现），并分析算法的时间复杂度和空间复杂度。要求时间复杂度尽量优化，在此前提下空间复杂度尽量优化。

zt_xcyk

题目要求说 “要求时间复杂度尽量优化”，所以我们肯定要想到基数排序、计数排序、桶排序等，这些时间复杂度比较小（ O(n) ）

首先将这个数拆成两部分，我们知道每个数的取值范围是[0,n^2-1]，那么它

占用的比特数就是|log(n^2-1)| =（约等于） |2*log(n)|，其中(|*|代表向上取整)。

1，首先把每个元素拆成两个|log(n)|的数字（可以用比特移位和或操作完成）。

2，然后先对低的|log(n)|位进行计数排序，每个元素的大小不超过(2^(|log(n)|)-1) =(约等于)n-1

3，然后在对高的|log(n)|位进行计数排序。

最终时间复杂度O(2*(n+n-1))=O(n)

空间复杂度为O(n)

发表于 2015-10-06 14:45:34 回复(1)

江小鱼2015

  (1) if n^2 is very small, which can be put into a basic data
  structure(take integer as example): 

  use bitmap, time:O(n), space:O(1) 

  (2) if n^2 is small, which can be put into memory: 

  use hashtable, time:O(n), space:O(n) 

  (3) if n^2 can not be put into memory but n can be put into: 

  quick sort, time：O(nlogn) space:O(n) 

  (4)*n is too big to put into memory: 

  use external sorting(like merge sort)

编辑于 2016-08-14 20:17:02 回复(1)