排序算法之堆排序

爱被打了一巴掌 2022-11-07 04:13 196阅读 0赞

# 排序算法-----堆排序 #

堆就是父节点值大于(大顶堆)子节点值或者父节点的值小于(小顶堆)子节点的值的完全二叉树，利用堆可以进行数组排序，如果要进行从小到大排序就使用大堆排序，如果进行从大到小排序就使用小堆排序，下面亮出代码(使用大堆从小到大排序)。

#include <iostream>
    using namespace std;
    
    //交换函数
    void Swap(int*arr, int a, int b) { 
    	int temp = 0;
    	temp = arr[a];
    	arr[a] = arr[b];
    	arr[b] = temp;
    }
    
    //打印函数
    void Print(int* arr, int len) { 
    	for (int ix = 0; ix < len; ix++) { 
    		cout << arr[ix] << " ";
    	}
    	cout << endl;
    }
    
    //堆排序 大堆 从小到大
    void Heapjust(int* arr, int index, int length) { 
    	
    	int max = index;
    	int lchild = 2 * index + 1;
    	int rchild = 2 * index + 2;
    
    	//将父节点与子节点进行比较
    	//选择最大的数为父节点的值
    	if (lchild < length && arr[max] < arr[lchild]) { 
    		max = lchild;
    	}
    	if (rchild < length && arr[max] < arr[rchild]) { 
    		max = rchild;
    	}
    
    	if (index != max) { 
    		Swap(arr, max, index);
    		Heapjust(arr, max, length);
    	}
    	//cout << arr[0] << endl;
    }
    
    //堆排序
    void HeapSort(int* myArr, int len) { 
    	//初始化堆
    	for (int i = len / 2 - 1; i >= 0; i--) { 
    		Heapjust(myArr, i, len);
    	}
    	//交换堆顶和最后一个值
    	//cout << myArr[0] << endl;
    	for (int ix = len - 1; ix >= 0; ix--) { 
    		Swap(myArr, 0, ix);
    		Heapjust(myArr, 0, ix);
    	}
    }
    
    
    int main() { 
    	int arr[9] = {  4,2,8,0,5,7,1,3,9 };
    	int len = sizeof(arr) / sizeof(int);
    
    	cout << "排序之前的数组为：" << endl;
    	Print(arr, len);
    
    	//堆排序
    	HeapSort(arr, len);
    	cout << "排序之后的数组为：" << endl;
    	Print(arr, len);
    
    	system("pause");
    	return 0;
    }

**代码执行结果为：**  
![堆排序结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70]  
可以看到输出的数列是从小到大排序。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70]: /images/20221023/799e2e3913f3492cb1656835aa3df375.png