稳固排序比不稳定排序,在统计上需要花费更多的时间吗

稳定排序比不稳定排序,在统计上需要花费更多的时间吗?
今天面试C/C++的算法，被问到这个问题，一时语塞。

举例说，C++ STL的stable_sort会不会比sort有更多的判断呢?
[解决办法]
内存不够用的时候std::stable_sort用的是O(n(logn)^2)的stable mergesort
[解决办法]
当然要更多的时间，要不然都用稳定排序了，谁还用不稳定排序
[解决办法]

引用:

当然要更多的时间，要不然都用稳定排序了，谁还用不稳定排序

关键在于，N*LogN的通用排序算法中，只有归并排序有稳定形式，而归并排序列的时间和空间率都比不上堆排序，更比不上快速排序。我们通常会选择快速排序或它的变化算法（比如内省排序），它可以或得最少的平均比较次数，可它没有稳定形式。

稳定排序与不稳定排序的比较，只有在面对同一算法的两种形式时才有意义。

对于归并排序来说，稳定形式与不稳定形式相比，其额外代价完全可以忽略。
插入排序的稳定形式需要放弃基本逆序时的快速判断，其它方面与不稳定的插入排序没有太大区别。
冒泡天生是稳定的，要想让它不稳定，反而要多一些比较和交换次数。
不稳定的选择排序可以实现N次交换的原位排序，稳定的选择排序或者是O（N）的空间效率，或者需要N^2级的元素移动次数，但它们的比较次数没有区别。

基数排序和桶排序稳定与不稳定基本没有区别。
[解决办法]

引用:

Quote: 引用:

当然要更多的时间，要不然都用稳定排序了，谁还用不稳定排序

关键在于，N*LogN的通用排序算法中，只有归并排序有稳定形式，而归并排序列的时间和空间率都比不上堆排序，更比不上快速排序。我们通常会选择快速排序或它的变化算法（比如内省排序），它可以或得最少的平均比较次数，可它没有稳定形式。

稳定排序与不稳定排序的比较，只有在面对同一算法的两种形式时才有意义。

对于归并排序来说，稳定形式与不稳定形式相比，其额外代价完全可以忽略。
插入排序的稳定形式需要放弃基本逆序时的快速判断，其它方面与不稳定的插入排序没有太大区别。
冒泡天生是稳定的，要想让它不稳定，反而要多一些比较和交换次数。
不稳定的选择排序可以实现N次交换的原位排序，稳定的选择排序或者是O（N）的空间效率，或者需要N^2级的元素移动次数，但它们的比较次数没有区别。

基数排序和桶排序稳定与不稳定基本没有区别。

钻什么文字游戏，lz问题的“统计上”3个字就可以说明lz想问的是对一般意义上所有的排序方法进行比较而不是什么“同一算法的两种形式”
[解决办法]
1.

template <class RandomAccessIterator>
  void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
  void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,
                     Compare comp );

If enough extra memory is available, linearithmic in the distance between first and last: Performs up to N*log2(N) element comparisons (where N is this distance), and up to that many element moves.

Otherwise, polyloglinear in that distance: Performs up to N*log22(N) element comparisons, and up to that many element swaps.

2.

template <class RandomAccessIterator>
  void sort (RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

On average, linearithmic in the distance between first and last: Performs approximately N*log2(N) (where N is this distance) comparisons of elements, and up to that many element swaps (or moves).
[解决办法]
稳定排序 和不稳定排序, 在统计上? 在统计上怎么理解呢?.统计上,统计上? 啥意思.是不是排完之后要用的情况下 ? 那稳定排序不就比不稳定排序时间 要短了. 因为统计来比较方便.

查看更多 下一篇