c++数据结构堆排序

一、提要

这篇和上一篇有关系，我就不重复上一篇写的了，有兴趣的可以看一下。这篇就当我自已的笔记了直接上代码

解释都在代码的注释里了

二、代码实现

1.初始化堆

这段代码在上一篇中有详细的解释，我就不在写了

typedef int DataType;typedef struct _Heap {	DataType *array;	int size;	int capacity;}Heap;void adjustDown(Heap &h,int index){	int cur = h.array[index];	int parent, child;	//在遍历元素还是已h.size 总元素个数遍历	for ( parent = index;parent*2+1 < h.size; parent = child) {		child = parent * 2 + 1;		if (((child + 1) < h.size)&& (h.array[child + 1] > h.array[child])) {			child++;		}		if (h.array[child] < h.array[parent]) {			break;		}		else {			h.array[parent] = h.array[child];			h.array[child] = cur;		}	}}void buildHeap(Heap& h) {	for (int i = (h.size / 2 - 1); i >= 0; i--){		adjustDown(h,i);	}}void  initHeap(Heap &h,int *original,int size) {	h.capacity = size;	h.size = size;	//不需要再动态内存分配了,直接在把original的地址赋值给堆结构体中的数组	h.array = original;	cout <<"最后一个元素"<
   
    << endl;	if (size > 0) {		buildHeap(h);		cout << "最后一个元素" << h.array[h.size - 1] << endl;			}}

2.堆排序

这里我每行代码都写了注释

void heapSort(Heap& h) {	//循环执行直到h.size小于零	while (h.size >= 0) {		//保存第一个元素也是最大元素		int cur = h.array[0];		//把数组最后的元素赋值给数组的第一个元素		h.array[0] = h.array[h.size - 1];		//把保存的数组中第一的元素的值赋给数组中的最后一个元素		h.array[h.size - 1] = cur;		//size 减一,在数组遍历时把最后一个元素排除		h.size--;		//向下执行堆调整,重新让这个数组成为最大堆		adjustDown(h, 0);	}}

3、main函数演示

int main(void) {	Heap h;	int original[] = { 1,2,3,4,5,9,6,7,12,10 };	 	initHeap(h, original, sizeof(original) / sizeof(original[0]));		//堆排序	heapSort(h);		for (int i = 0; i < sizeof(original) / sizeof(original[0]); i++) {		cout << original[i] << endl;	}	return 0;}