现有𝑛(𝑛 > 100000)个数保存在一维数组𝑀中，需要 查找𝑀中最小的 10 个数。用两种方法，c语言实现。

方法一：选择排序

选择排序是一种简单直观的排序算法，它的基本思想是：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

对于寻找最小的10个数，我们可以使用选择排序的思想，每次找到当前未排序部分的最小值，放到已排序部分的末尾，直到找到前10个最小值即可。

以下是基于选择排序的C语言实现代码：

#include <stdio.h>

void select_sort(int arr[], int n, int k) {
    int i, j, min_idx, temp;
    for (i = 0; i < k; i++) {
        min_idx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}

int main() {
    int M[100000];
    int n, k, i;
    printf("请输入数组长度n: ");
    scanf("%d", &n);
    printf("请输入需要查找的最小数个数k: ");
    scanf("%d", &k);
    printf("请输入数组M: ");
    for (i = 0; i < n; i++) {
        scanf("%d", &M[i]);
    }
    select_sort(M, n, k);
    printf("最小的%d个数为: ", k);
    for (i = 0; i < k; i++) {
        printf("%d ", M[i]);
    }
    return 0;
}

方法二：堆排序

堆排序是一种树形选择排序，它的基本思想是：将待排序的序列构造成一个大根堆或小根堆，此时整个序列的最大值或最小值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值或最小值。然后将剩余的n-1个元素重新构造成一个堆，如此反复执行，直到排序完成。

对于寻找最小的10个数，我们可以先构造一个大小为10的大根堆，然后遍历剩余的n-10个数，如果小于堆顶元素，则替换堆顶元素并进行堆调整，直到遍历完毕，此时堆中的10个元素即为前10个最小值。

以下是基于堆排序的C语言实现代码：

#include <stdio.h>

void adjust_down(int arr[], int i, int n) {
    int j, temp;
    temp = arr[i];
    j = 2 * i + 1;
    while (j < n) {
        if (j + 1 < n && arr[j + 1] > arr[j]) {
            j++;
        }
        if (arr[j] <= temp) {
            break;
        }
        arr[i] = arr[j];
        i = j;
        j = 2 * i + 1;
    }
    arr[i] = temp;
}

void heap_sort(int arr[], int n, int k) {
    int i, temp;
    for (i = k / 2 - 1; i >= 0; i--) {
        adjust_down(arr, i, k);
    }
    for (i = k; i < n; i++) {
        if (arr[i] < arr[0]) {
            temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            adjust_down(arr, 0, k);
        }
    }
}

int main() {
    int M[100000];
    int n, k, i;
    printf("请输入数组长度n: ");
    scanf("%d", &n);
    printf("请输入需要查找的最小数个数k: ");
    scanf("%d", &k);
    printf("请输入数组M: ");
    for (i = 0; i < n; i++) {
        scanf("%d", &M[i]);
    }
    heap_sort(M, n, k);
    printf("最小的%d个数为: ", k);
    for (i = 0; i < k; i++) {
        printf("%d ", M[i]);
    }
    return 0;
}