快速排序算法问题，看看大家的思路

Question

请补完下面的partition函数，这个函数有多种写法，请选择时间常数尽可能小的实现方法。
int partition(int start, int end)
{
从a[start..end]中选取一个pivot元素（比如选a[start]为pivot）;
在一个循环中移动a[start..end]的数据，将a[start..end]分成两半，
使a[start..mid-1]比pivot元素小，a[mid+1..end]比pivot元素大，而a[mid]就是pivot元素;
return mid;
}

void quicksort(int start, int end)
{
int mid;
if (end > start) {
mid = partition(start, end);
quicksort(start, mid-1);
quicksort(mid+1, end);
}
}
注意：请使用问题中的函数原型。《Linux C编程一站式学习》上的思考题。
我把我自己想的partition函数代码放上来，希望看到不同的解法。
int partition(int start, int end)
{
int key = a[start];
int i, j, mid = start;
printf("partition(%d-%d)\n", start, end);
for (i = start + 1; i <= end; i++) {
if (a[i] < key) {
a[mid] = a[i];
for (j = i; j > mid + 1; j--)
a[j] = a[j-1];
a[mid+1] = key;
mid = mid + 1;
}
printf("%d %d %d %d %d %d %d %d, mid = %d\n",
a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], mid);
}
return mid;
}
------------------------------------------------------------------------------------
不知道是我描述不清还是大家思维都太活跃了，对于提问要求中的“请使用问题中的函数原型”都视而不见。唏嘘。。。
quicksort函数已经给出了，不需要变化。直接补充partition函数即可。
mian函数中直接调用 quicksort(0, LEN-1)。

Answer 1

/*刚看了下算法导论，写了一个，感觉效率还可以，你看看 */
#include <stdio.h>

static int a[8] = {3, 7, 2, 8, 4, 5, 3, 9};

void swap (int *m, int *n)
{
int temp = *m;
*m = *n;
*n = temp;
}

int partition (int p, int r)
{
int j;
int x = a[r];
int i = p - 1;

for (j=p; j<r; j++)
{
if (a[j] <= x)
{
i++;
swap(&a[i], &a[j]);
}
}
swap(&a[i+1], &a[r]);

return i+1;
}

void quicksort (int p, int r)
{
int q;

if (p < r)
{
q = partition (p, r);
quicksort (p, q - 1);
quicksort (q+1, r);
}
}

int main ()
{
int i;
int len = sizeof(a) / 4;

for (i=0; i<len; i++)
printf ("%d ", a[i]);
printf ("\n");

quicksort (0, len - 1);

for (i=0; i<len; i++)
printf ("%d ", a[i]);
printf ("\n");

return 0;
}
/* 我空间里还有一篇文章是关于qsort的，glibc里的源码，我也没怎么看懂，感兴趣可以研究下 */
刚才看了楼上给出的网址，文章写的不错，里面给的网址对qsort的分析也很透彻，感觉人外有人，学习的路还很长阿。

追问

谢谢，支持原创！
可以运行。能不能讲一下为什么不直接交换数组元素而是用指针？
我还没看到指针这一节。

追答

因为用指针才能改变调用它的的函数的值，也就是改变实参的值。
如果不是指针的话函数是传值调用，所以形参是实参的一份拷贝，调用完之后实参
的值不会发生改变。

Answer 2

不懂

追问

谢谢！很诚实。
只要你愿意，可以由不懂到懂。^_^

Answer 3

就是一个从头走，一个从尾走，双进程，只遍历一次，时间复杂度0(n)

追问

要的是代码。谢谢!
我自己已经写出来了，只是想看看大家的思路。

追答

直接百度 快速排序法
C
　　//参照《数据结构》（C语言版）
　　//调用：quicksort-->qsort-->partitions
　　int partitions(int a[],int low,int high)
　　{
　　int pivotkey=a[low];
　　//a[0]=a[low];
　　while(low=pivotkey)
　　--high;
　　a[low]=a[high];
　　while(low
　　//#include
　　#include "myfunc.h" //存放于个人函数库中
　　main()
　　{
　　int i,a[11]={0,11,12,5,6,13,8,9,14,7,10};
　　for(i=0;i<11;printf("%3d",a[i]),++i);
　　printf("\n");
　　quicksort(a,10);
　　for(i=0;i<11;printf("%3d",a[i]),++i);
　　printf("\n");
　　}

追问

Sorry. 可能我没讲清楚。我不是要一个标准答案（标准答案貌似还不如我自己想到的简单），而是要一个发散的思维——大家自己的思路。标准答案到处都有，copy即可。

Answer 4

上学期课余做的快速排序优化的比较，欢迎拍砖：
http://hi.baidu.com/ycdoit/blog/item/e63d943cb5a24612bba167e8.html

Answer 5

用qsort()排序多简单啊 不用这么复杂的
还节约程序执行时间