設(shè)計(jì)一個算法，找出數(shù)組中最小的k個數(shù)。以任意順序返回這k個數(shù)均可。

找小的數(shù)需要建大堆來解決，首先將數(shù)組中前K個數(shù)建成一個大堆，將從k+1個數(shù)直到數(shù)組結(jié)束的所有數(shù)與堆頂?shù)臄?shù)進(jìn)行比較，如果比堆頂?shù)臄?shù)小，則替換堆頂?shù)臄?shù)據(jù)，然后在向下調(diào)整，重新形成一個新的大堆，如果比堆頂?shù)臄?shù)小，則不替換。以此循環(huán)，直至數(shù)組k+1個數(shù)到數(shù)組結(jié)束所有的數(shù)都比較完，最后留在堆里的數(shù)就是最小的k個數(shù)。用題中的題目來說：使用前4個數(shù) 1 3 5 7 來建一個大堆。

替換了之后由于不是一個大堆，所以進(jìn)行向下調(diào)整，形成一個新的大堆。

替換了之后進(jìn)行向下調(diào)整

最后輸出的結(jié)果

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

void AdjustDown(int* a, int n, int root)//向下調(diào)整
{
? ? int parent = root;
? ? int child = parent * 2 + 1;
? ? while (child < n)
? ? {
? ? ? ? if (child + 1 < n && a[child + 1] > a[child])//選出大的那個孩子
? ? ? ? {
? ? ? ? ? ? child++;
? ? ? ? }
? ? ? ? if (a[child] > a[parent])
? ? ? ? {
? ? ? ? ? ? int tmp = a[child];
? ? ? ? ? ? a[child] = a[parent];
? ? ? ? ? ? a[parent] = tmp;
? ? ? ? ? ? parent = child;
? ? ? ? ? ? child = parent * 2 + 1;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? break;
? ? ? ? }
? ? }
}

int* smallestK(int* arr, int arrSize, int k, int* returnSize)
{
? ? *returnSize = k;
? ? if (k == 0)
? ? ? ? return NULL;
? ? int* retArr = (int*)malloc(sizeof(int) * k);
? ? int i = 0;
? ? for (i = 0; i < k; i++)
? ? {
? ? ? ? retArr[i] = arr[i];
? ? }
? ? //建K個數(shù)的大堆
? ? for (i = (k - 1 - 1) / 2; i >= 0; i--)
? ? {
? ? ? ? AdjustDown(retArr, k, i);
? ? }

? ? for (i = k; i < arrSize; i++)
? ? {
? ? ? ? if (arr[i] < retArr[0])
? ? ? ? {
? ? ? ? ? ? retArr[0] = arr[i];
? ? ? ? ? ? AdjustDown(retArr, k, 0);
? ? ? ? }
? ? }
? ? *returnSize = k;

? ? return retArr;
}

int main()
{
? ? // 測試數(shù)據(jù)
? ? int arr[] = { 1,3,5,7,2,4,6,8 };
? ? int arrSize = sizeof(arr) / sizeof(arr[0]);
? ? int k = 4;
? ? int returnSize;

? ? // 調(diào)用 smallestK 函數(shù)
? ? int* result = smallestK(arr, arrSize, k, &returnSize);

? ? // 輸出結(jié)果
? ? printf("The smallest %d elements are:\n", k);
? ? for (int i = 0; i < returnSize; i++) {
? ? ? ? printf("%d ", result[i]);
? ? }
? ? printf("\n");

? ? // 釋放分配的內(nèi)存
? ? free(result);
? ? return 0;
}