快速排序 顺序统计量 数组分割
#include <stdio.h>#include <string.h>#define N 2578 void swap(int *p, int *q){inttmp;tmp = *p;*p = *q;*q = tmp;}/* 把a[t]作为参考，将数组分成三部分: 小于等于a[t]， * a[t]以及大于a[t]，分割完毕后，a[t]所在的下标即是a[t]的顺序 */int partition(int *a, int s, int t){inti, j;/* i用来遍历a[s]...a[t-1], j指向大于x部分的第一个元素 */for (i = j = s; i < t; i++) {if (a[i] < a[t]) {swap(a+i, a+j);j++;}}swap(a+j, a+t);return j;}/* 选择数组中第i大的元素并返回 */int quick_select(int *a, int s, int t, int i){intp, 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(){inti;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;}