最小的k个数 代码(C)
本文地址: http://blog.csdn.net/caroline_wendy
题目: 输入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("\n"); return 0;
}
输出:
1 2 3 4