标题: a few concetps about sorting algorithms and questions [打印本页] 作者: 30左右结次婚 时间: 2009-11-3 01:27 标题: a few concetps about sorting algorithms and questions 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)?作者: 风化雪夜 时间: 2009-11-3 01:27
帅哥！不会说中文吗？作者: ▄愛變鎖ゞ 时间: 2009-11-3 01:27
话说回来，HJin的E语很好》》》作者: √死胖子 时间: 2009-11-3 01:27
Q1：
任何非稳定排序都可以转化为稳定排序的，只是看时空代价多少，我想lgn似乎不行吧，没验证，我想快速的话，nlgn是可以的。时间上，就多了一次比较。