算法：快速排序以及第k小元素的线性选择算法
简要介绍下快速排序的思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。时间复杂度为O(nlogn)
一.《data structure and algorithm analysis in c》中的实现，测试过，觉得该说明的已经注释
#include<stdio.h>
#define LEN 15
#define CUTOFF 3
//用c++则可以写成引用
void swap(int *const p1, int *const p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//插入排序
void insertion_sort(int a[], int n)
{
int i, j;
int tmp;
for (i = 1; i < n; i++)
{
tmp = a[i];
for (j = i; j > 0 && a[j - 1] > tmp; j--)
a[j] = a[j - 1];
a[j] = tmp;
}
}
// return median of left, center, and right
// order these and hide the pivot
int median3(int a[], int left, int right)
{
int center = (left + right) / 2;
if (a[left] > a[center])
swap(&a[left], &a[center]);
if (a[left] > a[right])
swap(&a[left], &a[right]);
if (a[center] > a[right])
swap(&a[center], &a[right]);
// invariant: a[left] <= a[center] <= a[right]
swap(&a[center], &a[right - 1]); //将中位数作为pivot且放置在right-1处
return a[right - 1]; //返回pivot
}
void qsort(int a[], int left, int right)
{
int i, j, pivot;
if (left + CUTOFF <= right)
{
//因为要递归调用，如果不截断判断则会导致数组访问越界进而出现段错误
// left, left+1, ..., right-2, right-1, right 最极限的情况就是保证
// left与right中间至少有一个值，即CUTOFF最小要等于2,否则出现段错误
// CUTOFF=2保证可以取中位数
// 当CUTOFF=1时不出现段错误，但运行结果是错误的
pivot = median3(a, left, right);
i = left;
j = right - 1;
for (; ;)
{
while (a[++i] < pivot) {} //median函数已经比较了left和right，pivot当前位置为right-1
while (a[--j] > pivot) {} //故从left+1和right-2开始比较
if (i < j)
swap(&a[i], &a[j]);
else
break;
}
swap(&a[i], &a[right - 1]); //now i is the pivot index in the array
qsort(a, left, i - 1);
qsort(a, i + 1, right);
}
else // do an insertion sort on the subarray
insertion_sort(a + left, right - left + 1);
}
int main(void)
{
int i;
int arr[LEN] = {43, 423, 13, 6, 34, 64, 24, 69,
32, 28, 432, 641, 4365, 345, 624
};
qsort(arr, 0, LEN - 1);
for (i = 0; i < LEN; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}二.不对pivot进行中位数取值的简易版本
#include<stdio.h>
#define LEN 15
void swap(int *const p1, int *const p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void qsort(int a[], int left, int right)
{
int i, j, pivot;
pivot = a[right]; //the last item as pivot
i = left;
j = right - 1;
if (left < right)
{
for (; ;)
{
for (; a[i] < pivot; i++);
for (; a[j] > pivot; j--);
if (i < j)
swap(&a[i], &a[j]);
else
break;
}
swap(&a[i], &a[right]); //now i is the pivot index in the array
qsort(a, left, i - 1);
qsort(a, i + 1, right);
}
}
int main(void)
{
int i;
int arr[LEN] = {43, 423, 13, 6, 34, 64, 24, 69,
32, 28, 432, 641, 4365, 345, 624
};
qsort(arr, 0, LEN - 1);
for (i = 0; i < LEN; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}三.根据简易快速排序得出的第k小选择算法
#include<stdio.h>
#define LEN 15
#define K 6
void swap(int *const p1, int *const p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
int qsort(int k, int a[], int left, int right)
{
int i, j, pivot;
pivot = a[right];
i = left;
j = right - 1;
for (; ;)
{
for (; a[i] < pivot; i++);
for (; a[j] > pivot; j--);
if (i < j)
swap(&a[i], &a[j]);
else
break;
}
swap(&a[i], &a[right]); //now i is the pivot index in the array
//i.e. a[i] is the (i+1)th smallest item
if (k == i - left + 1)
return a[i];
else if (k < i - left + 1)
return qsort(k, a, left, i - 1); //target before pivot
else //target after pivot
return qsort((k - (i - left + 1)), a, i + 1, right);
}
int main(void)
{
int arr[LEN] = {43, 423, 13, 6, 34, 64, 24, 69,
32, 28, 432, 641, 4365, 345, 624
};
printf("%d\n", qsort(K, arr, 0, LEN - 1));
return 0;
}四.中位数之第k小的线性选择算法
实现该算法的步骤如下：
1.如果n是一个比较小的数，比如n<6，那么只需要对此无序数组进行排序后，即可很容易的得到第K小元素。
此时约束时间T=7。
2.如果n>5，那么我们将这个无序数组分成五组。此时约束时间T=n/5。
3.找出每组的中位数，构成集合M。此时的约束时间T=7n/5.
4.递归的调用selection(M,|M|/2)算法查找上一步中所有中位数的中位数，设为m。此时的约束时间
T=T（n/5）。
5.用m来分割此时的数组，比较m与其他的（n-1）个数，小于m的数置于左集合L，大于m的数置于右集合R。当
然，中位数m的下标r=|L|+1(|L|是左集合L的个数)。此时的约束时间T=T（n）。
如果r=k,那么返回m。
如果r<k,那么在小于m的左集合L中递归查找第K小数。
如果r>k,那么在大于m的右集合R中递归查找第K小数。
-----------------------------------------------------------------------------------------------------------------------------------------
参考：http://bbs.chinaunix.net/thread-116218-1-1.html
http://blog.csdn.net/fengchaokobe/article/details/6784721
http://ds.fzu.edu.cn/fine/resources/FlashContent.asp?id=82