最大/最小堆排序

时间:2023-01-30 16:24:17



void swap(int *arr, int a, int b){//交互两个数的位置
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

void BuildMaxHeap(int *arr, int i, int n){//建立大顶堆,进行调整
    int parent = arr[i], j;
    for(j = 2 * i; j <= n;j *= 2){
        if(j < n && arr[j] < arr[j+1])
            j++;
        if(parent >= arr[j]) break;
        arr[i] = arr[j];
        i = j;
    }
    arr[i] = parent;
}

void BuildMinHeap(int *arr, int i, int n){//建立小顶堆,进行调整
    int parent = arr[i], j;
    for(j = 2 * i; j <= n;j *= 2){
        if(j < n && arr[j] > arr[j+1])
            j++;
        if(parent <= arr[j]) break;
        arr[i] = arr[j];
        i = j;
    }
    arr[i] = parent;
}

void HeadSort(int *arr, int n){//堆排序
    for(int i = n/2;i >= 1;i--){//建堆
//        BuildMaxHeap(arr, i, n);//最大堆
        BuildMinHeap(arr, i, n);//最小堆
    }
    for(int i = n;i >= 1;i--)//调整排序
    {
        swap(arr, 1, i);
//        BuildMaxHeap(arr, 1, i-1);//最大堆
        BuildMinHeap(arr, 1, i-1);//最小堆
    }
}