|
今天打扫卫生，找到一堆废纸，看到去年参加google笔试的一道题目：
问：有一整数组，设为s[n]，存有n个整数，其值落在[0 ~ n*n-1]这个区间内，求对其快速排序
当时的解法为：
利用时空原理，可以得到 O(n) 的排序
设存在有一个整数组 a[n*n]， 则其可以存储 0 ～n*n-1 共n*n个数，令数组内所有数初始值为-1
则有
for (int i=0; i<n; i++){
a[s[i]] = s[i];
}
这样 数组a中 存储的非 -1 的值，即为数组s中的值，依从小到大的顺序 排好序
| 
转播
