网站建设的需要是什么,中文网站模板免费下载,四川省微信网站建设公,一个普通的网站做线上交易好吗1. 简述 假设待排序数组为 int array[], 数组长度为n。 主要是利用堆的性质。对于升序排序#xff0c;使用最大堆。 首先#xff0c;建堆#xff0c;使用递归后根序遍历得方法#xff0c;通过交换元素#xff0c;保证根元素比孩子元素大。 第1趟#xff0c;堆顶…1. 简述 假设待排序数组为 int array[], 数组长度为n。 主要是利用堆的性质。对于升序排序使用最大堆。 首先建堆使用递归后根序遍历得方法通过交换元素保证根元素比孩子元素大。 第1趟堆顶元素array[0]与array[n-1]交换保证array[n-1]的数值正确根据array[0]新的数值更新堆。 第2趟堆顶元素array[0]与array[n-2]交换保证array[n-2]的数值正确根据array[0]新的数值更新堆。 ··· 第n-1趟堆顶元素array[0]与array[1]交换保证array[1]的数值正确根据array[0]新的数值更新堆。 2. 复杂度 平均时间复杂度为O(N*logN)空间复杂度为O(1)。 3. 代码 void make_heap(int array[], int n, int node) { // 自底向上构建堆 int left 2 * node 1; int right 2 * node 2; if(left n-1) return; else if(right n-1) { // 堆是完全的二叉树所以此时不需要递归 if(array[node] array[left]) { swap(array[node], array[left]); } } else { make_heap(array, n, left); make_heap(array, n, right); if(array[node] array[left] array[right] array[left]) { swap(array[node], array[left]); } else if(array[node] array[right] array[left] array[right]) { swap(array[node], array[right]); } }}void update_heap(int array[], int n, int node) { // 自顶向下更新堆 int left 2 * n 1; int right 2 * n 2; if(left n-1) return; else if(right n-1) { if(array[node] array[left]) swap(array[node], array[left]); } else { if(array[node] array[left] array[right] array[left]) { swap(array[node], array[left]); update_heap(array, n, left); } else if(array[node] array[right] array[left] array[right]) { swap(array[node], array[right]); update_heap(array, n, right); } }}void heap_sort(int array[], int n) { make_heap(array, n, 0); for(int in; i1; i--) { swap(array[i], array[0]); update_heap(array, n, node); } } 实际上堆的构建和更新都可以使用非递归的方式实现对于堆的构建需要首先找到最后一个有孩子的节点array[k]然后从array[k]一直更新到array[0]即可其中的kn/2。k的求法如下假设k存在2*k1n或者2*k2n对于第一种情况kn/2对于第二种情况kn/2-1。对于堆的更新就更简单了只要从array[0]开始选择一条通路一直向下更新直到没有孩子了为止。 值得注意的是对于下标从0开始的数组k号节点的孩子节点分别是2*k1和2*k2。 而对于下标从1开始得数组k号节点的孩子节点分别是2*k和2*k1。 堆排序属于选择排序实际上就是利用最大堆这个数据结构每次选择一个剩余元素中最大的元素交换到合适的位置上去。 4. 参考资料 维基百科-堆排序 http://en.wikipedia.org/wiki/Heapsort
