思路：数据范围最大是1e6，所以我们的排序方式复杂度最好在$O(n\log{n})$以下。

方法一（危）：

为什么写“危”呢？因为快排的不稳定性。差点TLE，但是也能过（注意数组范围）：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N];
int n;
void partition(int a[],int l,int r)
{
    int x=a[l],i=l,j=r;
    if(l>=r) return;
    while(i<j) 
    {
        while(i<j and a[j]>=x) j--;
        a[i]=a[j];
        while(i<j and a[i]<=x) i++;
        a[j]=a[i];
        
    }
    a[i]=x;
    
    partition(a,l,i-1);
    partition(a,i+1,r);
}

int main()
{
   	cin>>n; 
    int m;
    cin >> m;
    for(int i=0;i<n;i++)  cin>>a[i];
    partition(a,0,n-1);
    for(int i=n-1;i>n-m-1;i--)cout << a[i]<<" ";
    return 0;
}

方法二（懒人福利）：

c++的内置函数sort刚好满足需求，所以用sort也行：

#include <bits/stdc++.h>
using namespace std;


int main(){
    int a;
    cin >> a;
    int m;
    cin >> m;
    int sz[1000005]={};
    for(int i=1;i<=a;i++)
        cin >> sz[i];
    sort(sz+1,sz+a+1);
    for(int i=a;i>a-m;i--)
        cout << sz[i]<<" ";
}

方法三：归并

直接归并的版一套就好

#include<iostream>
using namespace std;
int n , a[1000005] , temp[1010000];
void MergeSort(int l , int r)
{
	//2.1、递归的结束条件:只有一个数，就不用再递归下去，直接返回 
	if(l==r){
        return ;
    }
	//2.2、找到中间位置，递归处理左半部分，递归处理右半部分 
	int mid = (l + r) / 2;
	MergeSort(l,mid);
    MergeSort(mid+1,r);
	//3、合并，两个序列分别为[l,mid] 和 [mid+1,r]，从最左边开始，依次比较，小的数放入结果数组temp，下标右移 
	int i = l, j = mid + 1, k = l;
	while(i <=mid && j <= r)
	{
		if(a[i] <= a[j])
			temp[k++] = a[i++];
		else
			temp[k++] = a[j++];
	}
	//3.1、判断两个序列是否有剩余，有剩余的，全部放入结果数组 temp 
	while(i <= mid)
		temp[k++] = a[i++];
	while(j <= r)
		temp[k++] = a[j++];
	//4、把结果数组 temp 重新赋给 a 数组  
    for(int i=l;i<=r;i++)
        a[i]=temp[i];
	
}
int main()
{
	//1、定义变量 n 和数组 
	cin >> n; 
    int m;
    cin >> m;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	//2、划分，左端点为 1，右端点为 n，递归处理  
	MergeSort(1 , n);
	for(int i=n;i>(n-m);i--)
		cout << a[i]<<" "; 
	return 0; 
}

时间复杂度$O(n\log{n})$

---

方法四（堆排）：

直接上模版

#include <iostream>
#include <algorithm> // 用于swap函数

using namespace std;

// 维护最大堆性质
void heapify(int arr[], int n, int i) {
    int largest = i;        // 当前节点设为最大值
    int left = 2 * i + 1;   // 左子节点
    int right = 2 * i + 2;  // 右子节点

    // 找出当前节点、左子节点、右子节点中的最大值
    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果最大值不是当前节点，交换并递归调整
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

// 找出并输出前m大的元素
void findMthLargest(int arr[], int n, int m) {
    // 构建最大堆（从最后一个非叶子节点开始调整）
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 执行m次堆顶提取操作
    for (int i = n - 1; i >= n - m; --i) {
        swap(arr[0], arr[i]);    // 将当前堆顶（最大值）移到末尾
        heapify(arr, i, 0);      // 调整剩余部分为最大堆
    }

    // 输出前m大的元素（逆序输出末尾的m个元素）
    for (int i = n - 1; i >= n - m; --i) {
        cout << arr[i];
        if (i > n - m) cout << " ";
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    int arr[n];
    for (int i = 0; i < n; ++i)
        cin >> arr[i];

    findMthLargest(arr, n, m);
    cout << endl;

    return 0;
}

本代码优化过，时间复杂度为$O(m\log{n})$