|
本文对快速排序的几种实现进行速度分析。
首先根据《算法导论》p85提供的伪代码有如下快速排序的实现：
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | int partition(int *a, int start, int end)
{
int x = a[end];
int i = start-1;
int j=start;
for (int j = start; j < end; j++)
{
if (a[j] < x)
{
i++;
exch(a[i], a[j]);
}
}
exch(a[i+1], a[end]);
return i+1;
}
void quickSort(int *a, int start, int end)
{
if (start < end)
{
int p = partition(a, start, end);
quickSort(a, start, p-1);
quickSort(a, p+1, end);
}
}
|
其中第8行做了小小的改进，原文中是a[j]
下面是一个没有partition函数调用的递归实现：
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 | void quickSort1(int *a, int start, int end)
{
if (start < end)
{
int x = a[end];
int i = start-1;
int j=start;
for (int j = start; j < end; j++)
{
if (a[j] < x)
{
i++;
exch(a[i], a[j]);
}
}
exch(a[i+1], a[end]);
quickSort1(a, start, i);
quickSort1(a, i+2, end);
}
}
|
从测试结果看，这种没有partition函数调用的实现方式速度能提高将近10%，这是因为函数调用的开销很大，虽然patition函数调用的次数并不多（log n次）。
非递归实现：
理论上说非递归算法要比递归算法速度快，因为非递归算法减少了函数调用开销。将递归算法改为非递归算法的原理也就是使用stack保存函数每次递归调用所用到的参数，这些在递归算法中是有系统保存函数调用状态时一起保存的。所以理论上说只要自己能实现一个高效的stack，改写后的非递归算法就能比递归算法速度快。
在这篇博客中看到作者实现的非递归算法，作者发现非递归算法要比递归算法速度慢，而且做出里分析。我感觉很不可思议，和算法课上学习的“非递归算法比对应的递归算法速度快”不同，于是自己也使用stl的stack实现了一个非递归的快速排序算法，代码如下：
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | void quickSort2(int *a, int size)
{
stack<int> paraStack;
paraStack.push(0);
paraStack.push(size-1);
while (!paraStack.empty())
{
int end = paraStack.top();
paraStack.pop();
int start = paraStack.top();
paraStack.pop();
int x = a[end];
int i = start-1;
int j=start;
for (int j = start; j < end; j++)
{
if (a[j] < x)
{
i++;
exch(a[i], a[j]);
}
}
exch(a[i+1], a[end]);
if (start < i)
{
paraStack.push(start);
paraStack.push(i);
}
if (i+2 < end)
{
paraStack.push(i+2);
paraStack.push(end);
}
}
}
|
测试发现这种实现的非递归算法速度奇慢，比刚才提到的博客中作者测试的数据还慢（与非递归算法速度的差距），我严重怀疑stl实现的stack的性能存在很大的问题。
下面是我实现的使用自己的简单的stack实现的非递归快速排序算法，性能要比没有patition函数调用的递归算法要高。
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | void quickSort3(int *a, int size)
{
int mystack[32];
int top=-1;
mystack[++top] = 0;
mystack[++top] = size-1;
while (top>0)
{
int end = mystack[top--];
int start = mystack[top--];
int x = a[end];
int i = start-1;
int j=start;
for (int j = start; j < end; j++)
{
if (a[j] < x)
{
i++;
exch(a[i], a[j]);
}
}
exch(a[i+1], a[end]);
if (start < i)
{
mystack[++top]=start;
mystack[++top]=i;
}
if (i+2 < end)
{
mystack[++top] = i+2;
mystack[++top] = end;
}
}
}
|
下图是以上提到的几种实现的对相同大小的随机数组排序所用的时间。数据集为2^20（0xfffff）个随机整数数组，在windows下测试。
从图中可以看出，使用stl的实现竟然是使用自己的简单的stack的实现用时的10倍！
下面是我在Mac下做的测试，数据集为2^24（0xffffff）个随机整数数组。stl stack 和custom stack的差距要小一些。
1 2 3 | Quick Sort1 Time: 4702347
No Recursive Quick Sort Time(stl stack): 6614722
No Recursive Quick Sort Time(custom stack): 3660126
|
下面所Ubuntu下测试的结果，和mac下测试结果差不多，但是因为不在同一台机器上测试的，所以没法直接比较。stl stack和custom stack的差距和mac下测试结果差不多。由此是否能说吗windows下实现的stl效率很低呢？
1 2 3 | Quick Sort1 Time: 7030000
No Recursive Quick Sort Time(stl stack): 9100000
No Recursive Quick Sort Time(custom stack): 6590000
|
总结：
- <=和>=判断由于要进行两次比较和一次布尔运算，所以速度较低，尽量不要使用。
- 函数调用开销比较大，对于要提高算法运行速度的题目来说，尽量减少函数调用。最后一种非递归实现中，我将exch函数改用去掉，结果用时减少了30%。
- stl的stack实现效率很低，不适合实现快速算法
- 非递归算法总要比响应的递归算法速度快
本文中完整源码可以在这里查看，还包括其他一些排序算法的实现：https://github.com/hustwcw/SortAlgorithm/blob/master/SortAlgorithm/main.cpp
|
