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};
更多推荐
语言,大根堆,小根堆
发布评论