C语言实现选择排序——堆排序（大根堆、小根堆）

C语言实现堆排序

文章目录

C语言实现堆排序大根堆排序算法1.交换操作2.对结点进行调整为大根堆3.建立大根堆4.大根堆排序算法实现小根堆排序算法1.交换操作2.对结点进行调整为小根堆3.建立小根堆4.大根堆排序算法实现项目完整代码运行效果图

大根堆排序算法

1.交换操作

//交换实现
void swap(int &a, int &b) {int temp = a;a = b;b = temp;
}

2.对结点进行调整为大根堆

//将以k为根结点的子树调整为大根堆
void MaxHeadAdjust(int A[], int k, int len) {A[0] = A[k];                                //将子树根结点暂存在A[0]for (int i = 2 * k; i <= len; i *= 2) {     //沿值较大的子节点向下筛选if (i < len && A[i] < A[i + 1])         //如果它的左孩子的值小于右孩子的值i++;if (A[0] >= A[i])                       //如果根结点的值比左右孩子的最大值还要大或相等break;else {A[k] = A[i];                        //交换根结点与左右子孩子中最大值的结点k = i;                              //修改k的值，以便继续向下筛选}}A[k] = A[0];                                  //被筛选结点的值放入最终位置
}

3.建立大根堆

//建立大根堆
void BuildMaxHeap(int A[], int len) {for (int i = len / 2; i > 0; --i) {         //从i=[len/2]~1，反复调整堆MaxHeadAdjust(A, i, len);}
}

4.大根堆排序算法实现

//大根堆排序
void MaxHeapSort(int A[], int len) {BuildMaxHeap(A, len);                       //初始建立大根堆for (int i = len; i > 1; --i) {             //len-1趟交换和建堆过程swap(A[i], A[1]);                 //将对顶元素和堆底元素交换MaxHeadAdjust(A, 1, i - 1);      //调整，将剩余的i-1个元素继续整理为大根堆}
}

小根堆排序算法

1.交换操作

//交换实现
void swap(int &a, int &b) {int temp = a;a = b;b = temp;
}

2.对结点进行调整为小根堆

//将以k为根结点的子树调整为小根堆
void MinHeadAdjust(int A[], int k, int len) {A[0] = A[k];                                //将子树根结点暂存在A[0]for (int i = 2 * k; i <= len; i *= 2) {     //沿值较大的子节点向下筛选if (i < len && A[i] > A[i + 1])         //如果它的左孩子的值大于右孩子的值i++;if (A[0] <= A[i])                       //如果根结点的值比左右孩子的最小值还要小或相等break;else {A[k] = A[i];                        //交换根结点与左右子孩子中最小值的结点k = i;                              //修改k的值，以便继续向下筛选}}A[k] = A[0];                                  //被筛选结点的值放入最终位置
}

3.建立小根堆

//建立小根堆
void BuildMinHeap(int A[], int len) {for (int i = len / 2; i > 0; --i) {         //从i=[len/2]~1，反复调整堆MinHeadAdjust(A, i, len);}
}

4.大根堆排序算法实现

//小根堆排序
void MinHeapSort(int A[], int len) {BuildMinHeap(A, len);                       //初始建立小根堆for (int i = len; i > 1; --i) {             //len-1趟交换和建堆过程swap(A[i], A[1]);                 //将对顶元素和堆底元素交换MinHeadAdjust(A, 1, i - 1);      //调整，将剩余的i-1个元素继续整理为小根堆}
}

项目完整代码

//选择排序————堆排序（不稳定，空间效率为O(1)，时间效率为O(nlogn)）
#include <stdio.h>//交换
void swap(int &a, int &b) {int temp = a;a = b;b = temp;
}//将以k为根结点的子树调整为大根堆
void MaxHeadAdjust(int A[], int k, int len) {A[0] = A[k];                                //将子树根结点暂存在A[0]for (int i = 2 * k; i <= len; i *= 2) {     //沿值较大的子节点向下筛选if (i < len && A[i] < A[i + 1])         //如果它的左孩子的值小于右孩子的值i++;if (A[0] >= A[i])                       //如果根结点的值比左右孩子的最大值还要大或相等break;else {A[k] = A[i];                        //交换根结点与左右子孩子中最大值的结点k = i;                              //修改k的值，以便继续向下筛选}}A[k] = A[0];                                  //被筛选结点的值放入最终位置
}//将以k为根结点的子树调整为小根堆
void MinHeadAdjust(int A[], int k, int len) {A[0] = A[k];                                //将子树根结点暂存在A[0]for (int i = 2 * k; i <= len; i *= 2) {     //沿值较大的子节点向下筛选if (i < len && A[i] > A[i + 1])         //如果它的左孩子的值大于右孩子的值i++;if (A[0] <= A[i])                       //如果根结点的值比左右孩子的最小值还要小或相等break;else {A[k] = A[i];                        //交换根结点与左右子孩子中最小值的结点k = i;                              //修改k的值，以便继续向下筛选}}A[k] = A[0];                                  //被筛选结点的值放入最终位置
}//建立大根堆
void BuildMaxHeap(int A[], int len) {for (int i = len / 2; i > 0; --i) {         //从i=[len/2]~1，反复调整堆MaxHeadAdjust(A, i, len);}
}//建立小根堆
void BuildMinHeap(int A[], int len) {for (int i = len / 2; i > 0; --i) {         //从i=[len/2]~1，反复调整堆MinHeadAdjust(A, i, len);}
}//大根堆排序
void MaxHeapSort(int A[], int len) {BuildMaxHeap(A, len);                       //初始建立大根堆for (int i = len; i > 1; --i) {             //len-1趟交换和建堆过程swap(A[i], A[1]);                 //将对顶元素和堆底元素交换MaxHeadAdjust(A, 1, i - 1);      //调整，将剩余的i-1个元素继续整理为大根堆}
}//小根堆排序
void MinHeapSort(int A[], int len) {BuildMinHeap(A, len);                       //初始建立小根堆for (int i = len; i > 1; --i) {             //len-1趟交换和建堆过程swap(A[i], A[1]);                 //将对顶元素和堆底元素交换MinHeadAdjust(A, 1, i - 1);      //调整，将剩余的i-1个元素继续整理为小根堆}
}int main() {//0号位置为辅助空间，不存放有效元素！int MaxArr[] = {-1, 53, 17, 78, 9, 45, 65, 87, 32};int MinArr[] = {-1, 53, 17, 78, 9, 45, 65, 87, 32};int len_max = sizeof(MaxArr) / sizeof(int) - 1;int len_min = sizeof(MinArr) / sizeof(int) - 1;//大根堆排序MaxHeapSort(MaxArr, len_max);//将排序好的结果输出printf("大根堆排序结果为：");for (int i = 1; i <= len_max; ++i) {printf("%d ", MaxArr[i]);}printf("\n");//小根堆排序MinHeapSort(MinArr, len_min);//将排序好的结果输出printf("小根堆排序结果为：");for (int i = 1; i <= len_min; ++i) {printf("%d ", MinArr[i]);}return 0;
}

运行效果图

    //0号位置为辅助空间，不存放有效元素！int MaxArr[] = {-1, 53, 17, 78, 9, 45, 65, 87, 32};int MinArr[] = {-1, 53, 17, 78, 9, 45, 65, 87, 32};