c/c++排序算法-堆排序 旧城等待, 2022-10-02 11:57 118阅读 0赞 ### 文章目录 ### * * 基本思想 * 算法的实现: * 时间复杂度 * 空间复杂度 ## 基本思想 ## > 堆顶元素(即第一个元素)必为最小项(小顶堆) > 堆顶元素(即第一个元素)必为最大项(大顶堆) > 初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树),调整它们的存储序,使之成为一个堆,将堆顶元素输出,得到n 个元素中最小(或最大)的元素,这时堆的根节点的数最小(或者最大)。然后对前面(n-1)个元素重新调整使之成为堆,输出堆顶元素,得到n 个元素中次小(或次大)的元素。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。称这个过程为堆排序。 因此,实现堆排序需解决两个问题: 1. 如何将n 个待排序的数建成堆; 2. 输出堆顶元素后,怎样调整剩余n-1 个元素,使其成为一个新堆。 首先讨论第二个问题:输出堆顶元素后,对剩余n-1元素重新建成堆的调整过程。 调整小顶堆的方法: > 1)设有m 个元素的堆,输出堆顶元素后,剩下m-1 个元素。将堆底元素送入堆顶((最后一个元素与堆顶进行交换),堆被破坏,其原因仅是根结点不满足堆的性质。 > 2)将根结点与左、右子树中较小元素的进行交换。 > 3)若与左子树交换:如果左子树堆被破坏,即左子树的根结点不满足堆的性质,则重复方法 (2). > 4)若与右子树交换,如果右子树堆被破坏,即右子树的根结点不满足堆的性质。则重复方法 (2). > 5)继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。 称这个自根结点到叶子结点的调整过程为筛选。如图: ![在这里插入图片描述][20190618175454239.jpg] 再讨论第一个问题对n 个元素初始建堆的过程。 建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。 > 1)n 个结点的完全二叉树,则最后一个结点是第 个结点的子树。 > 2)筛选从第 个结点为根的子树开始,该子树成为堆。 > 3)之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。 如图建堆初始过程:无序序列:(49,38,65,97,76,13,27,49) ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JfTmVtbw_size_16_color_FFFFFF_t_70] ## 算法的实现: ## 从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。 #include <stdio.h> #include <stdlib.h> void printfarr(int *buf, unsigned int len, int count) { if (buf == NULL) { return; } printf("%d:", count); unsigned int i = 0; for (i = 0; i < len; i++) { printf("%d ", buf[i]); } printf("\n"); } void HeapAdjust(int *arr, int parent, unsigned int len) { int tmp = arr[parent]; int child = 2 * parent + 1;//左孩子节点位置 printf("左孩子:%d,右孩子:%d\n",arr[child],arr[child + 1]); while (child < len) { if (child + 1 < len && arr[child] < arr[child + 1]) { ++child; } if (arr[parent] < arr[child])//如果较大的子节点大于父节点 { arr[parent] = arr[child];//那么把较大的子节点往上移动,替换它的父节点 parent = child; //重新设置parent,等待调整下一个节点的位置 child = 2 * parent + 1; } else { break; } arr[parent] = tmp; printfarr(arr, len, parent); } } void BuildHeap(int *arr, int len) { //最后一个有孩子的节点的位置(len - 1)/ 2 for (int parent = (len - 1) / 2; parent >= 0; --parent) { printf("父节点:%d\n", arr[parent]); HeapAdjust(arr, parent, len); } } void HeapSort(int *arr, unsigned int len) { BuildHeap(arr, len); //从最后一个元素开始对序列进行调整 for (int i = len - 1; i > 0; --i) { arr[i] = arr[i] ^ arr[0]; arr[0] = arr[i] ^ arr[0]; arr[i] = arr[i] ^ arr[0]; HeapAdjust(arr, 0, i); } } int main() { int arr[] = { 9,8,7,6,5,4,3,2,1,0 }; HeapSort(arr, sizeof(arr) / sizeof(arr[0])); printfarr(arr, sizeof(arr) / sizeof(arr[0]), 0); return 0; } 运行结果: 父节点:5 左孩子:0,右孩子:-858993460 父节点:6 左孩子:2,右孩子:1 父节点:7 左孩子:4,右孩子:3 父节点:8 左孩子:6,右孩子:5 父节点:9 左孩子:8,右孩子:7 左孩子:8,右孩子:7 1:8 0 7 6 5 4 3 2 1 3:8 6 7 0 5 4 3 2 1 7:8 6 7 2 5 4 3 0 1 左孩子:6,右孩子:7 2:7 6 1 2 5 4 3 0 5:7 6 4 2 5 1 3 0 左孩子:6,右孩子:4 1:6 0 4 2 5 1 3 4:6 5 4 2 0 1 3 左孩子:5,右孩子:4 1:5 3 4 2 0 1 左孩子:3,右孩子:4 2:4 3 1 2 0 左孩子:3,右孩子:1 1:3 0 1 2 3:3 2 1 0 左孩子:2,右孩子:1 1:2 0 1 左孩子:0,右孩子:2 左孩子:1,右孩子:2 0:0 1 2 3 4 5 6 7 8 9 ## 时间复杂度 ## T ( n ) = O ( n l o g n ) T(n) = O(nlogn) T(n)=O(nlogn) ## 空间复杂度 ## S ( n ) = O ( 1 ) S(n) = O(1) S(n)=O(1) [20190618175454239.jpg]: /images/20220112/77e73ce4a0614f15bd615090fc389f85.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JfTmVtbw_size_16_color_FFFFFF_t_70]: /images/20220112/1bead3d7f9b741baaa41f77f1cbb6447.png
还没有评论,来说两句吧...