c/c++排序算法-堆排序

旧城等待， 2022-10-02 11:57 168阅读 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