快速排序 顺序统计量 数组分割

#include <stdio.h>
#include <string.h>

#define N 2578 

void swap(int *p, int *q)
{
	int		tmp;

	tmp = *p;
	*p = *q;
	*q = tmp;
}

int partition(int *a, int s, int t)
{
    int pv = a[t];

    while(s < t) {
        for (; s < t && a[s] < pv; s++);
        swap(a+s, a+t);
        for (; t > s && a[t] > pv; t--);
        swap(a+t, a+s);
    }

    return s;
}

/* 选择数组中第i大的元素并返回 */
int quick_select(int *a, int s, int t, int i)
{
	int		p, m;

	if (s == t) return a[t];
	p = partition(a, s, t);	/* 用a[t]分割数组 */
	m = p - s + 1;			/* m是a[t]在小组内的排名 */
	if (m == i) return a[p];
	if (m > i) {
		return quick_select(a, s, p-1, i);
	}
	return quick_select(a, p+1, t, i-m);
}

void quick_sort(int *a, int s, int t)
{
	int 	p;

	if (s < t) {
		p = partition(a, s, t);
		quick_sort(a, s, p-1);
		quick_sort(a, p+1, t);
	}
}

int main()
{
	int	i;
	int a[N+1];

	for (i = 0; i <= N; i++) {
		a[i] = N-i;
	}
	quick_sort(a, 0, N);

	printf("第%d大的数为%d\n", 2, quick_select(a, 0, N, 2));

	return 0;
}