快序排序寻找第k小的数：
快速排序每次都可以找到选择的基准数在排序完成的序列中的位置，那么如何寻找排序完成的序列中第k小的数呐？这是蓝桥杯第第八届的一道题目。
#include <stdio.h>
int quick_select(int a[], int l, int r, int k) {
int p = rand() % (r - l + 1) + l;
int x = a[p]; //随机产生一个范围是【l，r】的p，并将a【p】的值赋给X
{
int t = a[p]; a[p] = a[r]; a[r] = t;} //这里将a【p】与最后一个数交换，它为什么要这样做请看接下来的代码
int i = l, j = r; //首先把l和r赋值给i和j
while(i < j) {
//程序用a【i】和a【j】分别从数组的两端向中间移动，每次的移动都会将比X小的数放在角标为i的地方，比X大的放在角标为j的地方
while(i < j && a[i] < x) i++; //首先是从头开始往后移动，找出比X大的数（这个数要放在后面）
if(i < j) {
// 先进行第一次的分析，后面的循环分析是一样的
a[j] = a[i]; // 在进行第一次将前面比X大的数换到j的位置时，不用担心数组中最后一个元素被替换，因为X已经保存了这个元素
j--; //（而在后面几次这里的循环中你会发现这个值被替换前，这个值已经放到其它位置上了，所以不用担心有元素值没了）
} //在这一步我们也会发现最后面的元素已经被i所在的元素赋值了，而当前的i还存着应该放在后面的值，所以后面会把这个值替换
while(i < j && a[j] > x) j--; //从尾部往前走，找出比X大的值 放在i的位置，通过上面的步骤，你会发现那个i的值已经存放在别的地方
if(i < j) {
//而我们也通过i保存比X小的数才是正常的，所以把后面的数赋值给a【i】
a[i] = a[j]; //然后进行同样的操作是一样的意思
i++; // 举个例子如49,38,27,13,65,76,97 如果p=2，X=27，那么将其换到最后面时就成了49,38,97,13,65,76,27, i=0,j=6
} //第一次操作从头比较时,当i=0时就数组就换成了49，38，97，13，65，76，49（x保存了27，所以不用担心！），然后j=5；
} //从后开始比较时，j=3时，13<27，所以放在i的地方，即取代49，变成13，38，97，13，65，76，49（后面是一样的）
a[i] = x; //通过上面的循环操作，就会发现最后i=j，同时i左边的数都比X小，i右边的数都比X大，最后把缺少的数（也就是X）放上去
p = i;
if(i - l + 1 == k) return a[i]; //如果满足条件，就说明这就是要找的数所以直接返回这个值
if(i - l + 1 < k) return quick_select( _______a,i+1,r,k-(i-l+1)______________________ ); //填空
else return quick_select(a, l, i - 1, k); //通过分析i-l+1 和k 的大小来进行选择操作，因为此时i - l + 1的值大小就是这个值在排序后的位置
} //选择操作：如果i-l+1比k大，那就说明k所代表的值在左边，否则就在右边，然后再进行重复的递归操作
int main()
{
int a[] = {
1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12};
printf("%d\n", quick_select(a, 0, 14, 5));
return 0;
}
希尔排序：
类似于插入法排序，它与插入排序的不同之处在于，它会优先比较距离较远的元素。使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。希尔排序又叫缩小增量排序。
#include<stdio.h>
int main ()
{
int a[100], i, j, t, n, k;
scanf("%d", &n);
for ( i = 0; i < n; i++ ) {
scanf("%d", &a[i]);
}
k = n/2;
while ( k > 0 ) {
for ( i = k; i < n; i++ ) {
t = a[i];
for ( j = i-k; j >= 0 && a[j] > t; j-=k ) {
a[j+k] = a[j];
}
a[j+k] = t;
}
k = k/2;
}
for ( i = 0; i < n; i++ ) {
printf("%d ", a[i]);
}
return 0;
}
堆排序：
堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
实现步骤：1.将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;2.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;3.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
堆排序(最小堆性质)
#include<stdio.h>
int h[101];
int n;
void swap ( int x, int y )
{
int t;
t = h[x];
h[x] = h[y];
h[y] = t;
return;
}
void siftDown ( int i )
{
int t, flag = 0;
while ( i*2 <= n ) {
if ( h[i] > h[i*2] )
t = i*2;
else
t = i;
if ( i*2 <= n ) {
if ( h[t] > h[i*2+1] )
t = i*2+1;
}
if ( t != i ) {
swap(t, i);
i = t;
}
else
flag = 1;
}
return;
}
void creat ()
{
int i;
for ( i = n/2; i >= 1; i-- ) {
siftDown(i);
}
return;
}
int deletemax ()
{
int t;
t = h[1];
h[1] = h[n];
n--;
siftDown(1);
return t;
}
int main ()
{
int i, num;
scanf("%d", &num);
for ( i = 1; i <= num; i++ )
scanf("%d", &h[i]);
n = num;
creat();
for ( i = 1; i <= num; i++ )
printf("%d", deletemax());
getchar();
getchar();
return 0;
}