前几天发现老外的开源项目中事件队列中用的就是std::qsort排序，后续插入时候使用了堆方式。
快速排序实际应用中是比堆排序要快的，这主要是因为硬件层次会对数据执行高速缓存，
数据使用一二三级高速缓存比访问内存块很多，
所以堆排序实际上是比较慢的。
面试一般是考快速排序，
我没有事也默写了一个，并且和std::qsort与std::sort比较了一下，
代码的核心就是递归：
每个递归：
1）拿左边第一个元素作为标杆，小于的放它左侧，大于的放右侧，最后找到标杆合适的位置；
2）处理左侧；
2）处理右侧；
备注，递归深度与先后没有关系，与标杆是否平衡有关系；教科书算法没有考这些：
// 快速排序
static int GetMark(int *v, int i, int j)
{
int temp = v[i];
while (i < j)
{
while (temp <= v[j] && i < j)
j--;
v[i] = v[j];
while (temp >= v[i] && i < j)
i++;
v[j] = v[i];
}
v[i] = temp;
return i;
}
void quickSort(int * v, int begin, int end)
{
if (begin >= end)
return;
int index = GetMark(v, begin, end);
quickSort(v, begin, index - 1);
quickSort(v, index + 1, end);
}
这个写法是比较标准的教科书写法，下面写个计时器：
//使用高性能计时器实现的 GetTickCount 函数
double GetTickCountA()
{
__int64 Freq = 0;
__int64 Count = 0;
if (QueryPerformanceFrequency((LARGE_INTEGER*)&Freq)
&& Freq > 0
&& QueryPerformanceCounter((LARGE_INTEGER*)&Count))
{
//乘以1000，把秒化为毫秒
return (double)Count / (double)Freq * 1000.0;
}
return 0.0;
}
我们用一组随机数测试一下：
// 配套的比较函数
int cmpInt(const void * a, const void * b)
{
return *(int *)a - *(int *)b;
}
void testSort()
{
int n = 100000;
int * v = new int[n];
static default_random_engine engine;
static uniform_int_distribution<int> uniform(0, 750);
for (int i = 0; i < n; i++)
{
v[i] = uniform(engine);
//cout << v[i] << "\t";
}
cout << endl;
double tms1 = GetTickCountA();
InsertSort(v, n);
//quickSort(v, 0, n - 1);
//std::qsort(v, n, sizeof(int), cmpInt);
//std::sort(v, v + n-1);
double tms2 = GetTickCountA();
cout << tms2 - tms1 << endl;
/*for (int i = 0; i < n; i++)
{
cout << v[i] << "\t";
}*/
cout << "ok" << endl;
}
测试100万一下的数，其实还算好的，很快就算完了，
但是加到1000万时候，栈就崩了，vc默认的栈大小是1M，可以使用参数加载
linux设置环境变量可以加大，但是这不是解决问题的终极办法。
当随机的数类似二叉树时候，递归深度是log2(n)，但是如果分左右时候比较极端，直接考1侧分开，则深度可能达到N；
我打算看看有没有使用循环来代替的方法，但是好像应该没有；
实际上可以自己用堆上建立一个栈对象模拟递归，但是我更想知道人家怎么做到的。
1000万数据使用std::qsort时候很快，2秒多就结束了，人家没有崩溃，
std::sort非常慢，比自己写的还要慢，所以还是不要用了；
直接插入排序更慢，也不要用了；
所以很想看看qsort怎么实现的，于是我使用everything工具进行搜索，找到了微软的qsort.cpp文件，
它 核心思想有3个：
1）短于8个元素，改用选择排序；
2）因为有相等的部分，找标杆时候，使用2个标杆，分为三个部分：小于，等于，大于；这样就不再继续处理等于部分了；
3）使用自定义栈来避免递归。
歌词大意是这样的：
1）当分组下降到某个临界值时候，使用短距离排序；（注释里写的插入排序，但是看代码应该是选择排序）
临界值设置为8，注释所经过了测试，发现这个数值比较合适。
#define CUTOFF 8
2）这样递归堆栈的理论的深度应该是： 1 + log2(num) - log(CUTOFF) , 即log2(num) - 2，
num= 2^32,或者2^64
那么 32-bit系统上不超过30 的栈对象， 64-bit 系统需要62个；当然这是理论上的，所以源码定义了一个值：
#define STKSIZ (8 * sizeof(void*) - 2)
// 64位机器寻址范围是2^64, 这里就是字节数*8bits, 得到最大log2(2^64)
3）于是在程序的开始自己定义了2个栈
char* lostk[STKSIZ]; // 低标志的栈大小
char* histk[STKSIZ]; // 高标志的栈大小
int stkptr = 0; // 栈顶
4）定义栈之后，就可以开始准备手动递归了，定义一个标志，用于goto
recurse:
手动递归开始：
计算当前排序范围的距离，
5）如果长度小于8 ，则使用短距离排序，
否则：
6）使用第1个，最后1个元素，中间元素，三者进行比较，按顺序排列3个元素；
这样就用三个数定义了2个区间，lo----------mid------------hi，
比如：250----------460------------730
注释这样说：
首先我们要选择一个分区项(partition)。算法的高效性要求我们找到一个近似数组中间值的项，但我们要保证能够很快找到它。
我们选择数组的第一项、中间项和最后一项的中间值，来避免最坏情况下的低效率。
测试表明，选择三个数的中间值，比单纯选择数组的中间项的效率要高。
7）将数组分为3个部分：比分区值小，等于分区值，大于分区值；所以加了2个标记位：
char* loguy = lo; // lo + guy
char* higuy = hi;
那么：lo --------小于分区值------------loguy ------------等于分区值------------higuy -----------------大于分区值------------------hi
方法是：
循环：满足 (higuy < loguy)
a) loguy从左向右，如果A[loguy] <= A[mid] 移动;直到 A[loguy] > A[mid] ，（其中loguy可能越过mid）,
b) higuy从右向左，如果A[higuy] >A[mid] 则向左移动;直到 A[higuy] <= A[mid]， （其中higuy一直在mid右侧）,
c) if (higuy < loguy) break; 不需要交换了，停止！！！
d）交换A[loguy] 和 A[higuy]， 则 loguy左侧 <= A[mid]， higuy右侧 > A[mid]
lo -------------loguy ------------mid------------higuy -------大于-------------hi
lo---------小于等于------------mid------------大于-----------------------------hi
e）因为我们要求：higuy一直在mid右侧，
所以如果，higuy==mid，则令mid = loguy，
这样算法进入状态：loguy在mid右侧向右移动，higuy准备向左移动，
lo ----小于等于旧Amid---------[mid] --loguy===================higuy -------大于旧Amid-------------hi,
比如：
lo ----小于等于旧Amid---------500 --489,458,501===================600-------大于旧Amid-------------hi,
下面循环中，[mid] 不再移动，相当于两侧向中间移动，保证大的交换到右侧，小于等于的在左侧；
结束循环！
8）如果a[higuy] == A[mid] ，则继续左移，也就是找到相等的部分
lo ----------- higuy--------------[mid] ----------loguy------------------hi,
9）将一部分压栈，另一部分直接处理！
10）如果栈顶到负数，则结束。
简化后代码如下：
1）交换与交换排序
// 交换
void swapint(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
// 选择交换排序
void shortSort(int *v, int begin, int end)
{
int index; // 最大值的索引
while (begin < end)
{
index = begin; // 左侧不动，每个循环将最大的交换到最后，不稳定
for (int i=index+1; i<=end; i++)
{
if (v[i] > v[index])
{
index = i;
}
}
if (index < end)
swapint(v[index], v[end]);
end--;
}
}
2）寻找标记，分为三段：
//#define IS_PRINT_MARK2
inline void DEBUG_PRINT_MARK2(const char *str,int *v, int begin, int end, int mark1, int mark2, int mid)
{
#ifdef IS_PRINT_MARK2
// 调试输出
cout << str << endl;
for (int i = begin; i <= end; i++)
{
if (i == mid)
{
cout << "[" << v[i] << "]" << " ";
}
else if (i == mark2)
{
cout << "(" << v[i] << ")" << " ";
}
else if (i == mark1)
{
cout << "{" << v[i] << "}" << " ";
}
else if ((i+1 == mid) || (i+1 == mark2) || (i+1 == mark1)
|| (i - 1 == mid) || (i - 1 == mark2) || (i - 1 == mark1))
{
cout << v[i] << " ";
}
else
cout << v[i] << " ";
}
cout << endl;
#endif
}
// 分三个部分；返回mid
// 分为三段， 执行后，begin------mark2 等于部分不用处理 mark1---- - end
// 传统算法是将第1个元素作为标准，分左右，
// 这里是先选3个，第1，最后，中间，比较一下取中间作为标杆，之后执行分界
inline int Get2Mark(int *v, int& mark1, int &mark2, int begin, int end)
{
// 这里不少于8个元素
int count = end - begin + 1;
int mid = begin + count / 2;
// 冒泡法，排序3个数字
if (v[begin] > v[mid])
swapint(v[begin], v[mid]);
if (v[begin] > v[end])
swapint(v[begin], v[end]);
if (v[mid] > v[end])
swapint(v[mid], v[end]);
mark1 = begin; // 处理过了，跳过
mark2 = end;
DEBUG_PRINT_MARK2("准备开始：", v, begin, end, mark1, mark2, mid);
while (true)
{
// 这里是分阶段的，所有要判断左右关系
// 首先是: begin------mark1------mid------mark2-----end
// 之后是: begin------mid------mark1------mark2-----end
// 最后是: begin------mark2------mid------mark1-----end
// 找到大于的 微软这么做的，但是似乎有逻辑问题，不知道为啥，
//if (mark1 < mid) // 1) 阶段
//{
// do { mark1++; }
// while (mark1 < mid && v[mark1] <= v[mid]);
//
//}
//else // 2) 阶段
//{
while (mark1 <= end && v[mark1] <= v[mid])
mark1++;
//}
// 向左找到小于等于的；这里可能会越过mid，越过mark1
while (mark2 > mid && v[mark2] > v[mid])
mark2--;
if (mark2 < mark1) // 证明不需要交换了，这里从2阶段结束
break;
// 如同传统算法一样，交换一下，左边小于或者等于，右边大于
DEBUG_PRINT_MARK2("交换前：", v, begin, end, mark1, mark2, mid);
swapint(v[mark1], v[mark2]);
DEBUG_PRINT_MARK2("交换后：", v, begin, end, mark1, mark2, mid);
//cout << endl;
// 之前1）阶段，mark1 < mid，这里不会出现mark1 == mid，直到mark2左移到mid,
// 进入2) 阶段，begin------mid---[mark1]------[mark2]-----end
// 此时，mid和mark1之间都是小于等于mid, 大于的都放到右侧，
// 也就是在【mark1】 和【mark2】 位置上交换【mid】为标杆的数字，与传统算法近似但不同，
if (mid == mark2)
mid = mark1;
}
// 循环结束时候，mark2位置的数字应该是小于等于v[mid]
// 满足：
// 1) mark1左侧都是 <= v[mid]; mid 也在mark1左侧；
// 2) mark2右侧都是 >= v[mid];
// 3) mark2-----mark1
// 一般来说：mark2 == mark1 - 1
// 如图：-[mid:10]--9--8--10--[mark2][mark1]--11--12--11--
// 或者：v[end] == v[mid]，mark2 == end - 1, mark1 == end + 1,
// 如图 -[mid:10]--9--8--10--[mark2][end:10]|[mark1] j
// 所以要移动一次mark2
mark2++;
do
{
mark2--;
} while (mark2 >= begin && v[mark2] == v[mid]);
// 连续移动后，mark2----mark1之间如果有数据，则与v[mid]相等；
// 也可能没有；
//cout << mid << "," << mark2 << "," << mark1 << endl;
DEBUG_PRINT_MARK2("结束：", v, begin, end, mark1, mark2, mid);
return mid;
}
// 检测分界是否错误；
BOOL checkMark2(int *v, int begin, int end, int mark1, int mark2, int mid)
{
// 小于等于部分
for (int i=begin; i<mark2; i++)
{
if (v[i] > v[mid])
return FALSE;
}
// 都是大于
for (int j=mark1; j<=end; j++)
{
if (v[j] <= v[mid])
return FALSE;
}
return TRUE;
}
// 测试分界效果
int testmark2()
{
int n = 1000;
int *v = new int[n];
static default_random_engine engine;
static uniform_int_distribution<int> uniform(0, 750);
for (int i = 0; i < n; i++)
{
v[i] = uniform(engine);
// cout << v[i] << ", ";
}
cout << endl;
int mark1, mark2;
int mid = Get2Mark(v, mark1, mark2, 0, n-1);
int ret = checkMark2(v, 0, n - 1, mark1, mark2, mid);
if (ret == FALSE)
{
for (int i = 0; i < n; i++)
{
if (i == mid)
{
cout << "[" << v[i] << "]" << " ";
}
else if (i == mark2)
{
cout << "(" << v[i] << ")" << " ";
}
else if (i == mark1)
{
cout << "{" << v[i] << "}" << " ";
}
else if ((i + 1 == mid) || (i + 1 == mark2) || (i + 1 == mark1)
|| (i - 1 == mid) || (i - 1 == mark2) || (i - 1 == mark1))
{
cout << v[i] << " ";
}
else
cout << v[i] << " ";
}
cout << endl;
cout << endl;
}
delete[]v;
return ret;
}
这段代码和微软的流程有改动，因为测试发现微软的代码有点逻辑问题，但是没有想通，直接改了，如果有发现错误的，请告知！！
分界单独测试结果：生成30个随机数,查看与[mid], (mark2), {mark1}位置：
结果还算满意：
6, 3, 10, 9, 4, 7, 0, 6, 5, 4, 2, 3, 3, 8, 0, 5, 2, 3, 2, 7, 6, 5, 7, 8, 6, 3, 1, 7, 1, 6,
准备开始：
{5} 3 10 9 4 7 0 6 5 4 2 3 3 8 0 [6] 2 3 2 7 6 5 7 8 6 3 1 7 1 (6)
交换前：
5 3 {10} 9 4 7 0 6 5 4 2 3 3 8 0 [6] 2 3 2 7 6 5 7 8 6 3 1 7 1 (6)
交换后：
5 3 {6} 9 4 7 0 6 5 4 2 3 3 8 0 [6] 2 3 2 7 6 5 7 8 6 3 1 7 1 (10)
交换前：
5 3 6 {9} 4 7 0 6 5 4 2 3 3 8 0 [6] 2 3 2 7 6 5 7 8 6 3 1 7 (1) 10
交换后：
5 3 6 {1} 4 7 0 6 5 4 2 3 3 8 0 [6] 2 3 2 7 6 5 7 8 6 3 1 7 (9) 10
交换前：
5 3 6 1 4 {7} 0 6 5 4 2 3 3 8 0 [6] 2 3 2 7 6 5 7 8 6 3 (1) 7 9 10
交换后：
5 3 6 1 4 {1} 0 6 5 4 2 3 3 8 0 [6] 2 3 2 7 6 5 7 8 6 3 (7) 7 9 10
交换前：
5 3 6 1 4 1 0 6 5 4 2 3 3 {8} 0 [6] 2 3 2 7 6 5 7 8 6 (3) 7 7 9 10
交换后：
5 3 6 1 4 1 0 6 5 4 2 3 3 {3} 0 [6] 2 3 2 7 6 5 7 8 6 (8) 7 7 9 10
交换前：
5 3 6 1 4 1 0 6 5 4 2 3 3 3 0 [6] 2 3 2 {7} 6 5 7 8 (6) 8 7 7 9 10
交换后：
5 3 6 1 4 1 0 6 5 4 2 3 3 3 0 [6] 2 3 2 {6} 6 5 7 8 (7) 8 7 7 9 10
结束：
5 3 6 1 4 1 0 6 5 4 2 3 3 3 0 [6] 2 3 2 6 6 (5) {7} 8 7 8 7 7 9 10
最后一个关键的函数：
// 按照微软的qsort.cpp简化处理
void ms_qsort(int * v, int begin, int end)
{
const int CUTOFF = 8; // 临界值
const int STKSIZ = 100; // 堆栈100个；
int *lowStack = new int[STKSIZ];
int *higStack = new int[STKSIZ];
int top = 0; // 栈顶，栈顶为空
int mark1; // 用于分段的游标
int mark2;
int mid;
// goto 手动递归
recurse:
int count = end - begin + 1; // 计算个数
if (count <= 8)
{
shortSort(v, begin, end); // 优化；
}
else
{
// 第一阶段，分段；
// 如果分段后分成3部分，就压栈一部分，剩下的递归，直到都是小于7的小部分，小部分执行后会退栈
mark1 = begin;
mark2 = end;
// 分为三段， 执行后，begin------mark2 等于部分不用处理 mark1-----end
mid = Get2Mark(v, mark1, mark2, begin, end);
// 为了缩短栈深度，先做短的部分，长的部分先压栈，
// 这里能缩短，主要是8以下直接算不用压栈；传统算法标准递归不需要，没有用
// 如果左侧长
if (mark2-begin >= end-mark1)
{
if (begin < mark2) // 左侧部分先不处理，压栈，回头再说
{
// Save the big recursion for later:
lowStack[top] = begin;
higStack[top] = mark2;
++top;
}
if (mark1 < end) // 设置边界，直接处理后面的部分
{
begin = mark1;
goto recurse;
}
}
else // 如果右侧长
{
if (mark1 < end) // 右侧延展
{
lowStack[top] = mark1;
higStack[top] = end;
++top;
}
if (begin < mark2) // 左侧直接处理
{
end = mark2;
goto recurse;
}
}
}// end of else
--top; // 退栈
if (top >= 0)
{
// Pop sub-array from the stack:
begin = lowStack[top];
end = higStack[top];
goto recurse;
}
else
{
delete[] lowStack;
delete[] higStack;
return;
}
}
性能测试：
| 数据 \ 算法 | std::qsort | 简化版 | 栈最大深度 |
| 100万 int | 322毫秒 | 210毫秒 | 6 |
| 1000万int | 2.4秒 | 1.7秒 | 7 |
有兴趣大家可以测试一下。测试代码如下：
void testSort()
{
int n = 1000000;
int * v = new int[n];
static default_random_engine engine;
static uniform_int_distribution<int> uniform(0, 750);
for (int i = 0; i < n; i++)
{
v[i] = uniform(engine);
//cout << v[i] << " ";
}
cout << endl;
double tms1 = GetTickCountA();
//InsertSort(v, n);
//quickSort(v, 0, n - 1);
//std::sort(v, v + n-1);
//shortSort(v, 0, n - 1);
//int mark1, mark2;
//int mid = Get2Mark(v, mark1, mark2, 0, n-1);
//ms_qsort(v, 0, n - 1);
std::qsort(v, n, sizeof(int), cmpInt);
double tms2 = GetTickCountA();
cout << "-----------------------------------------------------------" <<endl;
//for (int i = 0; i < n; i++)
{
//cout << v[i] << " ";
}
cout << endl;
cout << tms2 - tms1 << " ";
cout << "ok" << endl;
delete[]v;
}
总结：
简化后之所以比std::qsort快，是因为比较部分都是直接比较，没有调用函数开销。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
