簡單經過改編的排序算法，你的編譯器能通過嗎？
本帖最后由 andalousie 于 2014-6-21 23:06 编辑這個演算法是改編的STL的 std::sort的某個實現版本，快排已經改得不是快排了，但是，重要的是，你的編譯器能跟我一樣編譯正常嗎？據我多次嘗試，沒有幾個編譯器會正常。問題可能出在decltype上面，可是我用的有錯嗎？
這裏貼出代碼
//Quicksort_Experiment.cpp
//author: andalousie
#include <iostream>
#include <algorithm>
const int SORT_MAX = 16;
template<class Ty> inline
Ty median(Ty a, Ty b, Ty c)
{
if (a < b)
return (b < c ? b : a < c ? c : a);
else
return (a < c ? a : b < c ? c : b);
}
template<class BI, class T> inline
void unguarded_insert(BI i2, T v)
{
for (BI scan = i2; v < *(--scan); i2 = scan)
*i2 = *scan;
*i2 = v;
}
template<class BI> inline
void insertion_sort(BI i1, BI i2)
{
if (i1 == i2) return;
for (BI scan = i1; ++scan != i2; )
{
decltype(*i1) v = *scan;
if (!(v < *i1))
unguarded_insert(scan, v);
else
{
std::copy_backward(i1, scan, scan + 1);
*i1 = v;
}
}
}
template<class It, class T> inline
void unguarded_partition(It i1, It i2, T pivot)
{
for (; ; ++i1)
{
for (; *i1 < pivot; ++i1);
for (; pivot < *(--i2); );
if (i2 < i1)
return;
std::swap(*i1, *i2);
}
}
template<class It> inline
void sort(It i1, It i2)
{
if (i2 - i1 <= SORT_MAX)
insertion_sort(i1, i2);
else
{
int distance = i2 - i1;
for (It s = i1, e; SORT_MAX < distance; )
{
It save;
if (distance >= i2 - s)
e = i2, distance >>= 1, save = i1;
else
e = s + distance, save = e;
unguarded_partition(s, e,
median(*s, *(s + (e - s) / 2), *(e - 1)));
s = save;
}
insertion_sort(i1, i1 + SORT_MAX);
for (i1 += SORT_MAX; i1 != i2; ++i1)
unguarded_insert(i1, *i1);
}
}
int main()
{
int a[] = {1,2,4,3,5,7,0,2,6,4,33,765,345,234,252,23,64,34,54,6,5,3,645,254,234,5,23,25,422,432};
sort(a, a+30);
for (int i = 0; i < 30; ++i)
std::cout << *(a+i) << " ";
} 而且這個排序已經不快了。我一開始的目標是不用遞歸實現一下。現在還是有難度
页:
[1]