/*
std::stable_sort has some extra overhead in allocating the temp buffer,
which takes some time. The cutover point where it starts to get faster
than quicksort seems to be somewhere around 10 to 40 records.
So we're a bit conservative, and stay with quicksort up to 100 records.
*/
if (count <= 100)
{
if (param->sort_length < 10)
{
std::sort(m_sort_keys, m_sort_keys + count,
Mem_compare(param->sort_length));
return;
}
std::sort(m_sort_keys, m_sort_keys + count,
Mem_compare_longkey(param->sort_length));
return;
}
// Heuristics here: avoid function overhead call for short keys.
if (param->sort_length < 10)
{
std::stable_sort(m_sort_keys, m_sort_keys + count,
Mem_compare(param->sort_length));
return;
}
std::stable_sort(m_sort_keys, m_sort_keys + count,
Mem_compare_longkey(param->sort_length));
最后附上快速排序的代码
带排序数据是13,3,2,9,34,5,102,90,20,2
排序完成后如下:
gaopeng@bogon:~/datas$ ./a.out
sort result:2 2 3 5 9 13 20 34 90 102
/*************************************************************************
> File Name: qsort.c
> Author: gaopeng QQ:22389860
> Mail: gaopp_200217@163.com
> Created Time: Fri 06 Jan 2017 03:04:08 AM CST
************************************************************************/
#include
#include
int partition(int *k,int low,int high)
{
int point;
point = k[low]; //基准点,采用数组的第一个值,这里实际可以优化
while(low
{
while(low
{
high--;
}
k[low] = k[high]; //基准点多次交换为无谓交换直接赋值即可
while(low
{
low++;
}
k[high] = k[low]; //基准点多次交换为无谓交换直接赋值即可
}
k[low] = point;
return low;
}
int q_sort(int *k,int low,int high)
{
int point;
if(low
{
point = partition(k,low,high);
q_sort(k,low,point-1); //实现递归前半部分
q_sort(k,point+1,high); //实现递归后半部分
}
return 0;
}
int main()
{
int i,a[10]={13,3,2,9,34,5,102,90,20,2}; //测试数据
q_sort(a,0,9); //数组下标0 9
printf("sort result:");
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
来源: