题目描述

补充一下数组下标从0开始的堆排序

C++ 代码

#include<stdio.h>
int n,m;
int a[100010];
void swap(int i,int j){
    int temp=a[i];
    a[i]=a[j];
    a[j]=temp;
}
void heapify(int n,int i){
    int c1=2*i+1;
    int c2=2*i+2;
    int max=i;
    if(c1<n&&a[c1]>=a[max])
        max=c1;
    if(c2<n&&a[c2]>=a[max])
        max=c2;
    if(max!=i){
        swap(max,i);
        heapify(n,max);
    }
}
void buildheap(int n){
    int lastnode=n-1;
    int parent=(lastnode-1)/2;
    for(int i=parent;i>=0;i--)
        heapify(n,i);
}
void heapsort(int n){
    buildheap(n);
    for(int i=n-1;i>=0;i--){
        swap(i,0);
        heapify(i,0);

    }
}
int main(void){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
    heapsort(n);
    for(int i=0;i<m;i++)
    printf("%d ",a[i]);
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla