快速选择实例

功能：查找集合S中第k个最小元。

快速选择算法修改自快速排序算法，当算法终止时，第k个最小元就在位置k上。这破坏了原来的排序；如果不希望这样，那么需要做一份拷贝。

快速选择函数：

/* quick_select.h */

#ifndef _QUICK_SELECT_H
#define _QUICK_SELECT_H

void qselect(int array[], int k, int left, int right);

#endif

/* quick_select.c */

#include "quick_select.h"
#include "common.h"
#include "insertion_sort.h"
#include "quick_sort.h"

#define CUTOFF    (3)

/* places the kth smallest element in the kth position */
/* because arrays start at 0, this will be index k-1 */
void 
qselect(int array[], int k, int left, int right)
{
    int i, j;
    int pivot;
    
    if(left + CUTOFF <= right)
    {
        pivot = median3(array, left, right);
        i = left; j = right - 1;
        for(;;)
        {
            while(array[++i] < pivot){}
            while(array[--j] > pivot){}
            if(i < j)
                swap(&array[i], &array[j]);
            else 
                break;
        }
        swap(&array[i], &array[right - 1]);

        if(k <= i)
            qselect(array, k, left, i - 1);
        else if(k > i + 1)
            qselect(array, k, i + 1, right);
    }
    else
        insertion_sort(array + left, right - left + 1);
}

其中，

common.h参考：http://www.cnblogs.com/nufangrensheng/p/3665397.html；

insertion_sort.h参考：http://www.cnblogs.com/nufangrensheng/p/3657887.html；

quick_sort.h参考：http://www.cnblogs.com/nufangrensheng/p/3669915.html

测试函数：

/* quick_select_test.c */

#include "quick_select.h"
#include "common.h"
#include <stdio.h>

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

    printf("array :");
    print_array(array, 10);
    qselect(array, 3, 0, 9);
    printf("the 3th smallest element is %d\n", array[2]);
    
    return 0;
}

测试结果：