C++直接排序算法问题
发布网友
发布时间：2022-04-22 09:14
共1个回答
热心网友
时间：2022-05-23 05:32
快速排序实际上就是分治之排序实际上是将复杂排序划分为多个子排序,对不同的子排序利用不同的算法以提高效率.数量大的采用二分排序,如果雷同元素多,可能会导致二分区间划不出来,则采用堆排序.前两种都是利用堆栈排序,开销还是比较大的但效率高.数量较小的直接利用插入排序即可.
对于快速排序，stl有了较好的实现，不必重复写，我大概注释了一下，给你参考参考
template
inline
//
stl
内部的排序函数实现
void
_sort(_ranit
_first,
_ranit
_last,
_diff
_ideal,
_pr
_pred)
{
//
_count是容器的尺寸,首先根据容器的尺寸选择算法
_diff
_count;
for
(;
_isort_max
<
(_count
=
_last
-
_first)
&&
0
<
_ideal;
)
{
//
二分排序,取中间下标,左边是小于中间值的,右边是大于中间值的
//
不断的递归,直到无法再划分这样的大,小区间.
pair<_ranit,
_ranit>
_mid
=
std::_unguarded_partition(_first,
_last,
_pred);
_ideal
/=
2,
_ideal
+=
_ideal
/
2;
if
(_mid.first
-
_first
<
_last
-
_mid.second)
{
//
对左侧的区间递归
std::_sort(_first,
_mid.first,
_ideal,
_pred);
_first
=
_mid.second;
}
else
{
//
对右侧的区间递归
std::_sort(_mid.second,
_last,
_ideal,
_pred);
_last
=
_mid.first;
}
}
//
如果雷同元素多,可能会导致划分失败,这个时候采用堆排序
if
(_isort_max
<
_count)
{
//
heap
sort
if
too
many
divisions
std::make_heap(_first,
_last,
_pred);
std::sort_heap(_first,
_last,
_pred);
}
else
if
(1
<
_count)
//
元素较少的情况插入排序
std::_insertion_sort(_first,
_last,
_pred);
//
small
}
#include
#include
void
main()
{
int
arrint[]
=
{1,
2,
2,
3,
4,
5,
3,
4};
std::sort(arrint,
arrint
+
sizeof(arrint)/sizeof(arrint[0]));
std::copy(arrint,
arrint
+
sizeof(arrint)/sizeof(arrint[0]),
std::ostream_iterator
(std::cout,
"
"));
}
