快速排序这个自己想了一会，真的想不出来，还是查了资料，使用 C89 标准函数库有一个非常简单的写法，（维基上的不能跑，自己稍稍改了一下）

#include <stdio.h>
#include <stdlib.h>

static int cmp(int *a, int *b)
{
	return *a-*b;
}

int main()
{
	int arr[10]={5, 3, 7, 4, 1, 9, 8, 6, 2};

	qsort(arr, 10, sizeof(int), (int(*) (const void *,const void *))cmp);

	return 0;
}

而我交到 hdu 的是

#include <stdio.h>
#define MAX 1005

int get(int arr[])
{
	int n, i;
	scanf("%d", &n);
	for (i=0; i<n; i++)
	{
		scanf("%d", &arr[i]);
	}
	return n;
}

void print(int arr[], int n)
{
	printf("%d", arr[0]);
	int i;
	for (i=1; i<n; i++)
	{
		printf(" %d", arr[i]);
	}
	printf("n");
}

void quick_sort(int arr[], int left, int right)
{
	int i = left, j = right;
	int pivot = arr[(i+j)/2];
//	printf("pivot is %dn", pivot);
	while (i <= j)
	{
		while (arr[i] < pivot)
		{
			i++;
		}
		while (arr[j] > pivot)
		{
			j--;
		}
		if (i <= j)
		{
		//	printf("swapping arr[%d]:%d and arr[%d]:%dn",
		//		i, arr[i], j, arr[j]);
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i++;
			j--;
		}
	}
	if (left < j)
	{
		quick_sort(arr, left, j);
	}
	if (i < right)
	{
		quick_sort(arr, i, right);
	}
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int arr[MAX] = {0};
		int n = get(arr);
		quick_sort(arr, 0, n-1);
		print(arr, n);
	}
	return 0;
}

最后，附上一个 python 的版本，再次体会到 python 的简洁

def qsort(L):
   if not L: return []
   return qsort([x for x in L[1:] if x< L[0]]) + L[0:1] + 
          qsort([x for x in L[1:] if x>=L[0]])

不仅简洁，而且思路非常清晰，易懂，不过 python 这个版本空间复杂度比较高就是了

==============================================================

2012-08-11 00:37:12 update: 上面那个快排，有两个地方想不懂：

1. 在 31 行 while 循环那里，为什么需要小于等于呢，为什么不能去掉等号呢
2. 在 52 和 56 行那里，为什么需要判断 if 呢，那个地方是一个递归终止条件这我知道，问题是，那个 if 在什么情况下会不成立呢，i 从左往右递增，怎么会超过 right 呢，同理 j 也一样啊

==============================================================

2012-08-11 01:01:26 update: 第二个问题看下面这个代码的输出应该就能有体会了，具体我也不知道怎么说

#include <stdio.h>
#define MAX 1005

int total;
int *p_arr;

int get(int arr[])
{
	int n, i;
	scanf("%d", &n);
	for (i=0; i<n; i++)
	{
		scanf("%d", &arr[i]);
	}
	return n;
}

void print(int arr[], int n)
{
	n = total;
	arr = p_arr;
	printf("%d", arr[0]);
	int i;
	for (i=1; i<n; i++)
	{
		printf(" %d", arr[i]);
	}
	printf("n");
}

void quick_sort(int arr[], int left, int right)
{
	int i = left, j = right;
	int pivot = arr[(i+j)/2];
	printf("left is %d right is %d pivot is %dn", left, right, pivot);
	while (i <= j)
	{
		while (arr[i] < pivot)
		{
			i++;
		}
		while (arr[j] > pivot)
		{
			j--;
		}
		if (i <= j)
		{
			printf("swapping arr[%d]:%d and arr[%d]:%dn",
				i, arr[i], j, arr[j]);
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i++;
			j--;
			print(arr, 0);
		}
	}
	if (left < j)
	{
		quick_sort(arr, left, j);
	}
	else
	{
		printf("left is %d and not smaller than j is %dn", left, j);
	}
	if (i < right)
	{
		quick_sort(arr, i, right);
	}
	else
	{
		printf("i is %d and not smaller than right is %dn", i, right);
	}
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int arr[MAX] = {0};
		p_arr = arr;
		int n = get(arr);
		total = n;
		quick_sort(arr, 0, n-1);
		print(arr, n);
		printf("donen");
	}
	return 0;
}

至于第一个问题嘛，我把等于号删掉了，交到 hdu 上是可以过的，看起来应该是没问题的，但是怎么证明呢