优化的快速排序
按照书上的最优快速排序代码，写了两份简单的。驱动程序读取数据规模n，随机数填充一个长度为n的数组，从小到大排序，并输出排序时间。
@ Athlon 64 X2 5200+ 2.75GHz / 2x2GB DDR2 800
@ Archlinux —- 2.6.37-pf x86-64 内核
GCC 4.5.2：gcc source.c -O3 -std=c99
FPC 2.4.2：fpc source.pas -O3
C99实现（修改COMP改变排序顺序； 用标准库qsort比较时间）：
#include <stdio.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>
#include <sys/time.h>
// 调试开关
//#define DEBUGPRINT
/* 交换变量的宏函数 */
#define SWAP(X,Y) {temp=(X);(X)=(Y);(Y)=temp;}
/* 获取时间差的宏函数 */
#define TIMEDIFF(X,Y) (1000000*((Y).tv_sec-(X).tv_sec)+(Y).tv_usec-(X).tv_usec)
/* 用于自编快排的比较函数 */
extern inline int COMP (const int x, const int y)
{
return x > y ? 1 :
(x < y ? -1 : 0);
}
/* 用于标准qsort()的比较函数 */
int COMP2 (const void *x, const void *y)
{
return *(int*)x - *(int*)y;
}
/* 自编快排 --- 快速排序部分 */
void xquicksort (int *pL, int *pR)
{
ptrdiff_t diff;
int mid, temp, *pi, *pj, *pmid, ppivot;
while (( diff = pR - pL ) >= 36 )
//36可修改为大于3的任何数
//越大快排作用越小，同时插排作用越大
{
mid = rand() % (diff-2) + 1;
pmid = pL + mid;
if (COMP(*pL, *pmid)>0)
SWAP(*pL, *pmid);
if (COMP(*pL, *pR)>0)
SWAP(*pL, *pR);
if (COMP(*pmid, *pR)>0)
SWAP(*pmid, *pR);
SWAP(*pmid, *(pR-1));
pi = pL;
pj = pR - 1;
ppivot = *pj;
while (1)
{
while (COMP(*++pi, ppivot) < 0)
continue;
while (COMP(*--pj, ppivot) > 0)
continue;
if (pi>=pj)
break;
else
SWAP(*pi, *pj);
}
*(pR - 1) = *pi;
*pi = ppivot;
if (pi - pL > pR - pi)
{
xquicksort(pi+1, pR);
pR = pi - 1;
}
else
{
xquicksort(pL, pi-1);
pL = pi + 1;
}
}
}
/* 自编快排 --- 插入排序部分 */
void InsSort (int *arr, const int len)
{
int i, j, temp;
for (i = 1; i < len; i++)
{
temp = arr[i];
for (j = i - 1; j >= 0; j--)
if (COMP(arr[j], temp) > 0)
arr[j+1] = arr[j];
else
break;
arr[j+1] = temp;
}
}
/* 自编快排 --- 用户接口部分 */
void QSort (int *arr, const int len)
{
xquicksort(arr, arr+len-1);
InsSort(arr, len);
}
int main (void)
{
int n, *arr, *arr2, i;
struct timeval stime, etime;
printf("数据规模: ");
scanf("%d", &n);
arr = malloc(n * sizeof(int));
arr2 = malloc(n * sizeof(int));
srand((int)arr);
puts("数组填充中...");
for (i = 0; i < n; i++)
{
arr2[i] = arr[i] = rand();
#ifdef DEBUGPRINT
printf("%d ", arr[i]);
#endif
}
puts("\n开始使用自编函数排序...");
gettimeofday(&stime, NULL);
QSort(arr, n);
gettimeofday(&etime, NULL);
printf("排序用时: %.3f ms\n", (float)TIMEDIFF(stime, etime) / 1000.0);
puts("\n开始使用标准库函数排序...");
gettimeofday(&stime, NULL);
qsort(arr2, n, sizeof(int), COMP2);
gettimeofday(&etime, NULL);
printf("排序用时: %.3f ms\n", (float)TIMEDIFF(stime, etime) / 1000.0);
#ifdef DEBUGPRINT
bool wrong = false;
puts("排序后数组:");
for (i = 0; i < n-1; i++)
{
if (arr[i] != arr2[i])
wrong = true;
printf("%d ", arr[i]);
}
puts(wrong ? "\n算法错误" : "\n正常结束");
#endif
return 0;
}
Pascal实现（修改所有comp注释行，反转不等号，即可调整排序顺序； 用FP示例快排比对时间）：
program QuickSort_im;
uses
dos;
var
n, i, stime, etime : longint;
wrong : boolean;
arr, arr2 : array of longint;
(*
* < gettimeofday_hs: 获取时间 >
* 返回值: 以0.01秒为单位的当日时间
* 本程序中用于统计排序用时。
*)
function gettimeofday_hs : longint;
var
hour, minute, second, sec100 : word;
begin
gettime(hour, minute, second, sec100);
exit( hour*360000 + minute*6000 + second*100 + sec100 );
end;
// ------------ 快速排序所需函数 BEGIN ------------ //
(*
* < swap: 交换变量 >
* swap (变量a, 变量b)
*)
procedure swap (var a, b: longint);
var
temp: longint;
begin
temp := a;
a := b;
b := temp;
end;
(*
* < inssort: 插入排序 >
* inssort (待排序数组, 排序区域下界, 排序区域上界)
* 本程序中用于快排后期处理。
*)
procedure inssort (var a: array of longint; const down, up: longint);
var
i, j, add, temp : longint;
begin
for i := down+1 to up do
begin
temp := a[i];
add := down;
for j := i-1 downto down do
if a[j] > temp then //COMP
arr[j+1] := arr[j]
else
begin
add := j+1;
break;
end;
arr[add] := temp;
end;
end; // inssort END
(*
* < qsort: 自己写的快速排序 >
* qsort (待排序数组, 排序区域下界, 排序区域上界)
* 按照书上的方法，优化过的快排，从C代码移植。
*)
procedure qsort (var a: array of longint; const down, up: longint);
procedure xquicksort (l, r: longint);
var
diff, i, j, pivot: longint;
begin
diff := r - l;
while diff >= 24 do
//24可修改为大于3的任何数
//越大快排作用越小，同时插排作用越大
begin
i := random(diff-2) + 1 + l;
if a[l] > a[i] then //COMP
swap(a[l], a[i]);
if a[l] > a[r] then //COMP
swap(a[l], a[r]);
if a[i] > a[r] then //COMP
swap(a[i], a[r]);
swap(a[i], a[r-1]);
i := l;
j := r-1;
pivot := a[j];
repeat
repeat inc(i); until a[i] >= pivot; //COMP
repeat dec(j); until a[j] <= pivot; //COMP
if i>=j then
break
else
swap(a[i], a[j]);
until false;
a[r-1] := a[i];
a[i] := pivot;
if i-l > r-i then
begin
xquicksort(i+1, r);
r := i-1;
end
else
begin
xquicksort(l, i-1);
l := i + 1;
end;
diff := r - l;
end;
end; // qsort->xquicksort END
begin
xquicksort(down, up);
inssort(arr, down, up);
end; // qsort END
(*
* < qsort_fp: FreePascal 快速排序示例 >
* qsort_fp (待排序数组, 排序区域下界, 排序区域上界)
* FP安装路径/demo/text/qsort.pp 快速排序示例。
*)
procedure qsort_fp (var a: array of longint; const down, up: longint);
procedure sort(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]<x do inc(i);
while x<a[j] do dec(j);
if i<=j then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; // qsort_fp->sort END
begin
sort(down, up);
end; // qsort_fp END
// ------------ 快速排序所需函数 END ------------ //
begin
write('数据规模: ');
readln(n);
randomize;
setlength(arr, n);
setlength(arr2, n);
writeln('数组填充中...');
writeln;
for i := 0 to n-1 do
begin
arr[i] := random(maxlongint);
arr2[i] := arr[i];
end;
writeln('开始使用自编函数排序...');
stime := gettimeofday_hs();
qsort(arr, 0, n-1);
etime := gettimeofday_hs();
writeln('排序用时: ', (etime-stime)/100.0 :0:2, ' s');
writeln;
writeln('开始使用FreePascal示例函数排序...');
stime := gettimeofday_hs();
qsort_fp(arr2, 0, n-1);
etime := gettimeofday_hs();
writeln('排序用时: ', (etime-stime)/100.0 :0:2, ' s');
// 检查排序结果
wrong := false;
for i := 0 to n-1 do
if arr[i] <> arr2[i] then
wrong := true;
writeln;
if wrong then
writeln('算法错误.')
else
writeln('正常结束.');
// 检查 END
end.
排序20000000个数的性能比较： C 实现：2.08 s C qsort()：4.03 s Pascal 实现：3.36 s Pascal 示例：4.18 s