a few concetps about sorting algorithms and questions

30左右结次婚

A few concetps about sorting algorithms and questions
A sorting algorithm is stable if whenever there are two
records R and S with the same key and with R appearing
before S in the original list, R will appear before
S in the sorted list. For example:
(1, 2), (1, 4) --> sorting algo which gives
(1, 2) (1, 4) is stale;
(1, 2), (1, 4) --> sorting algo which gives
(1, 4) (1, 2) is not stale.
A sorting algorithm is in place if only O(1) extra memory is
needed beyond the items being sorted. Comments: when define
the term in place, a book I read said
only O(1) or O(lgn) extra memory is needed.
Let us stick with the first definition: only O(1) memory is allowed
for in place algorithm.
Under these classifications and standard implementations (e.g.,
a not standard implementation of bubble sort can use as such
memory as the coder wants):
bubble, insertion, and merge are stable;
heap and quick are unstable.
bubble, insertion and heap are in place;
merge is not in place.
Q1: Is quick sort considered to be in place? Assume that we use O(lgn)
stack length for quicksort, such as the following implementation:
void quicksort(int* a, int p, int r)
{
while(p<r)
{
int q = partition(a, p, r);
// only sort the smaller part
if(q-p<r-q)
{
quicksort(a, p, q-1);
}
else
{
quicksort(a, q+1, r);
}
}
}

Q2: Is there a stable and in place sorting algorithm (based
on comparsion)?

风化雪夜

帅哥！不会说中文吗？

▄愛變鎖ゞ

话说回来，HJin的E语很好》》》

√死胖子

Q1：
任何非稳定排序都可以转化为稳定排序的，只是看时空代价多少，我想lgn似乎不行吧，没验证，我想快速的话，nlgn是可以的。时间上，就多了一次比较。

Q2：
nlgn的，没有。不额外处理的话。

一世豪杰

以下是引用aipb2007在2007-9-23 11:52:19的发言：

Q1：
任何非稳定排序都可以转化为稳定排序的，只是看时空代价多少，我想lgn似乎不行吧，没验证，我想快速的话，nlgn是可以的。时间上，就多了一次比较。

Q2：
nlgn的，没有。不额外处理的话。


Are there proofs for your statements?

未来的回忆

自己想的！

因为稳定与否就是因为相同元素的原始顺序问题。加一个附属值（下标序）在元素相同时多判断一次。