u******s
发帖数: 157 | 1 Hi,大家新年快乐！
小弟最近面试嘛，遇到一些关于算法的问题，比如说，如果已知一列数（已经打乱）是
从1～n，那么如
何不再占用新内存的情况下sort这个数列。
我对这类算法的问题完全没有头绪，请问下板上的牛人们，有没有入门级别的书/网站
或者学习方法给介
绍一下子？
谢谢了！ |
o******l
发帖数: 35 | |
z****s
发帖数: 532 | 3 题目没说清楚吧，是size是n的array?如果说清楚了的话，2楼正解
去wiki 搜索sorting algorithms |
w******i
发帖数: 503 | 4
haha. good humor.
【在 o******l 的大作中提到】
: for( int i=0; i
|
c********g
发帖数: 54 | 5 看一下各种排序算法，有不需要新的空间的
【在 u******s 的大作中提到】
: Hi,大家新年快乐！
: 小弟最近面试嘛，遇到一些关于算法的问题，比如说，如果已知一列数（已经打乱）是
: 从1～n，那么如
: 何不再占用新内存的情况下sort这个数列。
: 我对这类算法的问题完全没有头绪，请问下板上的牛人们，有没有入门级别的书/网站
: 或者学习方法给介
: 绍一下子？
: 谢谢了！
|
m****s
发帖数: 1481 | 6 不需要新空间，交换两个数：
假设x=a;y=b;是要交换的两个数。
x=y-x; (now x=b-a.)
y=y-x; (now y=b-(b-a)=a.)
x=x+y; (now x=b-a+a=b.)
估计不是最优的，但是满足不增加新内存。 |
c********g
发帖数: 54 | 7 Merge sort.
【在 c********g 的大作中提到】
: 看一下各种排序算法，有不需要新的空间的
|
b******n
发帖数: 637 | 8 <>
a bible as my personal opinion, good luck |
k*******d
发帖数: 1340 | |
k*******d
发帖数: 1340 | 10 Merge sort能很容易的做到不用新空间吗？我记得在某个地方看过，in place的merge
sort不是
那么好写的。还是quick sort容易做到把，几乎不要改
【在 c********g 的大作中提到】
: Merge sort.
|
