如何在数组中选取k个最小的值进行从低到高排序？

如何在数组中选取k个最小的值进行从低到高排序？
如何在数组中选取k个最小的值进行从低到高排序？

回答：可以用快速排序的选择第K大的数，或者采用堆排序，选择前k个最小的，然后选完了就排序结束，
可以参考这篇文章：https://blog.csdn.net/bingbingyihao/article/details/127925976

堆排序：

#include <stdio.h>

#define MAX_SIZE 20
typedef int Type;

void printArr(Type arr[], int length)
{
    int i;
    for (i = 0; i < length; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void heapAdjust(Type arr[], int low, int high)
{
    Type temp = arr[low];
    int i;
    for (i = 2 * low; i < high; i *= 2)
    {
        if (i < high && arr[i] < arr[i + 1])
        {
            i++;
        }
        if (temp >= arr[i])
        {
            break;
        }
        arr[low] = arr[i];
        low = i;
    }
    arr[low] = temp;
}

void createHeap(Type arr[], int length)
{
    int i;
    for (i = length / 2; i >= 0; i--)
    {
        heapAdjust(arr, i, length);
    }
}

void heapSort(Type arr[], int length)
{
    createHeap(arr, length);

    int i;
    Type temp;
    for (i = length - 1; i > 0; i--)
    {
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapAdjust(arr, 0, i - 1);

        printArr(arr, length);
    }
}

int main()
{
    Type arr[] = { 1, 1, 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
    int length = sizeof(arr) / sizeof(Type);

    heapSort(arr, length);
}

快速排序

#include <stdio.h>

#define MAX_SIZE 20
typedef int Type;

void printArr(Type arr[], int length)
{
    int i;
    for (i = 0; i < length; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int Partition(Type arr[], int low, int high)
{
    Type temp = arr[low];
    Type pivot = arr[low];
    while (low < high)
    {
        while (low < high && arr[high] >= pivot)
        {
            high--;
        }
        arr[low] = arr[high];
        while (low < high && arr[low] <= pivot)
        {
            low++;
        }
        arr[high] = arr[low];
    }
    arr[low] = temp;
    return low;
}

void quickSort(Type arr[], int low, int high, int length)
{
    if (low < high)
    {
        int pivot = Partition(arr, low, high);
        quickSort(arr, low, pivot - 1, length);
        quickSort(arr, pivot + 1, high, length);
    }
    printArr(arr, length);
}

int main()
{
    Type arr[] = { 5, 3, 1, 7, 9, 2, 4, 6, 8, 10 };
    int length = sizeof(arr) / sizeof(Type);

    quickSort(arr, 0, length - 1, length);
}

可用STL 排序算法 std::partial_sort 该函数从指定区域中提取出部分数据，并对它们进行排序。

#include <iostream>     // std::cout
#include <algorithm>    // std::partial_sort
#include <vector>       // std::vector
using namespace std;
//以普通函数的方式自定义排序规则
bool mycomp1(int i, int j) 
{
    return (i > j);
}
//以函数对象的方式自定义排序规则
class mycomp2 
{
public:
    bool operator() (int i, int j)
    {
        return (i > j);
    }
};

int main() 
{
    std::vector<int> myvector{ 3,2,5,4,1,6,9,7};

    //以默认的升序排序作为排序规则，将 myvector 中最小的 4 个元素移动到开头位置并排好序
    std::partial_sort(myvector.begin(), myvector.begin() + 4, myvector.end());
    cout << "第一次排序:\n";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << *it << ' ';
    cout << "\n第二次排序:\n";

    // 以指定的 mycomp2 作为排序规则，将 myvector 中最大的 4 个元素移动到开头位置并排好序
    std::partial_sort(myvector.begin(), myvector.begin() + 4, myvector.end(), mycomp2());
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << *it << ' ';
    return 0;
}

打印输出

第一次排序:
1 2 3 4 5 6 9 7
第二次排序:
9 7 6 5 1 2 3 4