输入n个整数并找出其中的最小k个数

输入n个整数并找出其中的最小k个数2015-09-14题目: 输入n个整数, 找出其中的最小k个数.

使用快速排序（Quick Sort）的方法求解, 把索引值（index）指向前k个数.

代码:

/** main.cpp**Created on: 2014.6.12*Author: Spike*//*eclipse cdt, gcc 4.8.1*/#include <stdio.h>#include <stdlib.h>int RandomInRange（int min, int max） {int random = rand（） % （max-min+1） + min;return random;}void Swap （int* num1, int* num2） {int temp = *num1;*num1 = *num2;*num2 = temp;}int Partition（int data[], int length, int start, int end） {if （data == NULL || length <= 0 || start < 0 || end >= length）return -1;int index = RandomInRange（start, end）;Swap（&data[index], &data[end]）;int small = start-1;for （index = start; index < end; ++index） {if （data[index] < data[end]） {small++;if （small ！= index）Swap（&data[small], &data[index]）;}}small++;Swap（&data[small], &data[end]）;return small;}void GetLeastNumbers（int* input, int n, int* output, int k） {if （input == NULL || n <= 0 || output == NULL || k <= 0 || k>n）return;int start = 0;int end = n-1;int index = Partition（input, n, start, end）;while （index ！= k-1） {if （index > k-1） {end = index - 1;index = Partition（input, n, start, end）;} else {start = index + 1;index = Partition（input, n, start, end）;}}for （int i=0; i<k; ++i） {output[i] = input[i];}}int main（void）{int input[] ={4, 5, 1, 6, 2, 7, 3, 8};int output[4];GetLeastNumbers（input, 8, output, 4）;for （int i=0; i<4; ++i） {printf（"%d ", output[i]）;}printf（"
"）;return 0;}

输出:

1 2 3 4