写了一个优化版的快速排序(svQuickSort)和一个归并排序(svMergeSort),和stdlib中的qsort一较高下。
先说说svQuickSort使用的优化。
首先使用Median-3算法寻找pivot。
其次短排序使用插入排序优化。因为Shell sort是进阶版的插排
而且Shell sort是第一个打破Quadratic barrier的排序算法,所以短排序我们使用Shell sort优化。
别急,至此,Shell sort还能被优化。我们知道,一般来说Shell sort取得gap值是以2为倍数的,
但是这个gap还能被进一步优化。在维基百科上我找到了Macin Ciura‘s gap sequence
这个数组的使用使得Shell sort的效率又上了一个档次。
最后因为svQuickSort有4个参数,压栈的时候要压4个指针长度的整数。
我们可以自己制造一个raw stack总共需要压栈两个指针整数的长度即可。
详情请看下图代码。
测试结果,Linux上clang开O3优化执行后约22秒。
svMergeSort约27秒,stdlib自带的qsort约17秒。
接下来,用MSVC编译优化的结果就逆天了,
一个1024*1024*128的int数组排序耗时7.7秒!
MSVC自带的cstdlib排序用时11秒。
这是svQuickSort源码:
00
这是Shell sort源码:
MSVC优化编译测试结果:
以上代码均可以在这里下载:
先说说svQuickSort使用的优化。
首先使用Median-3算法寻找pivot。
其次短排序使用插入排序优化。因为Shell sort是进阶版的插排
而且Shell sort是第一个打破Quadratic barrier的排序算法,所以短排序我们使用Shell sort优化。
别急,至此,Shell sort还能被优化。我们知道,一般来说Shell sort取得gap值是以2为倍数的,
但是这个gap还能被进一步优化。在维基百科上我找到了Macin Ciura‘s gap sequence
这个数组的使用使得Shell sort的效率又上了一个档次。
最后因为svQuickSort有4个参数,压栈的时候要压4个指针长度的整数。
我们可以自己制造一个raw stack总共需要压栈两个指针整数的长度即可。
详情请看下图代码。
测试结果,Linux上clang开O3优化执行后约22秒。
svMergeSort约27秒,stdlib自带的qsort约17秒。
接下来,用MSVC编译优化的结果就逆天了,
一个1024*1024*128的int数组排序耗时7.7秒!
MSVC自带的cstdlib排序用时11秒。
这是svQuickSort源码:
00
这是Shell sort源码:
MSVC优化编译测试结果:
以上代码均可以在这里下载: