查找最小的 k 个元素
题目：输入 n 个整数，输出其中最小的 k 个。
例如输入 1，2，3，4，5，6，7 和 8 这 8 个数字，则最小的 4 个数字为 1，2，3 和 4。
代码思路：方法有很多种，只是时间复杂度问题。
代码一：快速排序C语言实现
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#define N 6
int partition(int a[], int low, int high)
{
int key = a[low];
a[0] = a[low];
while (low < high)
{
while (low < high&&a[high] >= key)
{
high--;
}
a[low] = a[high];
while (low < high&&a[low] <= key)
{
low++;
}
a[high] = a[low];
}
a[low] = a[0];
return low;
}
void qsort(int a[], int low, int high)
{
int p;
if (low < high)
{
p = partition(a, low, high);
qsort(a, low, p - 1);
qsort(a, p + 1,high);
}
}
void output(int a[], int num)
{
for (int i = 1; i <= num; i++)
{
printf("%d ", a[i]);
}
}
void main()
{
int a[N];
int num;
printf("请输入数字个数\n");
scanf("%d", &num);
for (int i = 0; i < num; i++)
{
scanf("%d", &a[i]);
}
qsort(a, 1, 5);
printf("\n");
printf("请输入最小的n个元素\n");
int n;
scanf("%d", &n);
output(a, n);
system("pause");
}
代码2：最小堆排序算法
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#define N 6
void heapjust(int a[], int i, int length)
{
int child = 0, tmp;
for (tmp = a[i]; 2 * i + 1
{
child = 2 * i + 1;
if (child < length - 1 && a[child+1] < a[child])
{
child++;
}
if (tmp>a[child])
{
a[i] = a[child];
}
else
{
break;
}
a[child] = tmp;
}
}
int getmin(int a[], int i, int length)
{
int min = a[0];
a[0] = a[length-1];
a[length-1] = min;
int tmp, child = 0;
int k = 0, j = i - 1;
for (tmp = a[0];2 * k + 1 < length-1; k = child)
{
child = 2 * k + 1;
if (child < length - 2 && a[child + 1] < a[child])
{
child++;
}
if (tmp>a[child])
{
a[k] = a[child];
}
else
{
break;
}
a[child] = tmp;
}
return min;
}
void kmin(int a[], int length, int k)
{
for (int i = length - 1; i >= 0; i--)
{
heapjust(a, i, length);
}
int j = length;
for (int i = k; i > 0; i--, j--)
{
int min = getmin(a, i, j);
printf("%d \n", min);
}
}
void main()
{
int a[N];
int num;
printf("请输入数字个数\n");
scanf("%d", &num);
for (int i = 0; i < num; i++)
{
scanf("%d", &a[i]);
}
kmin(a, num, 3);
system("pause");
}
