《大话数据结构》之堆排序

秒速五厘米 2022-08-20 11:10 139阅读 0赞

所谓的堆，实际是排序后的完全二叉树。

完成这个算法需要掌握排序后的完全二叉树的一些特性：

1、按层数，从上往下，依次为第一层，第二层，。。。，第n+1层。第n层的数据，一定大于（大顶堆）或小于（小顶堆）第n+1层的数据。

2、如果对一棵有n个节点的完全二叉树（其深度为不大于㏒2ⁿ的最大整数+1）的节点按层序编号（从1到不大于㏒2ⁿ的最大整数+1层，每层从左到右），对任一节点（1≤i≤n）有

2.1、如果i=1，则节点i是二叉树的根，无双亲，如果i>1,则其双亲是节点 不大于i/2的最大整数

2.2、如果2i>n，则节点i无左孩子；否则其左孩子是节点2i

2.3、如果2i+1>n，则i节点无右孩子，否则其右孩子是节点2i+1

知道了上面这些特性，才有办法理解代码中的逻辑循环。

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    #define MAX_LEN 256
    typedef struct
    {
    	int iInput[MAX_LEN];
    	int iLength;
    }SqArr;
    
    void swap(SqArr *pToSwap,int iFirst,int iSecond)
    {
    	if (iFirst != iSecond)
    	{
    		pToSwap->iInput[iFirst] = pToSwap->iInput[iFirst] + pToSwap->iInput[iSecond];
    		pToSwap->iInput[iSecond] = pToSwap->iInput[iFirst] - pToSwap->iInput[iSecond];
    		pToSwap->iInput[iFirst] = pToSwap->iInput[iFirst] - pToSwap->iInput[iSecond];
    	}
    }
    
    int Output(SqArr *pSqToPrint)
    {
    	int iLoop;
    	for(iLoop=1;iLoop<=pSqToPrint->iLength;iLoop++)
    	{
    		printf("%d ",pSqToPrint->iInput[iLoop]);
    	}
    	printf("\n");
    	return 0;
    }
    
    void HeapAdjust(SqArr *pToSort,int iStart,int iEnd)
    {
    	int iLoop;
    	for(iLoop=iStart*2;iLoop<=iEnd;iLoop=iLoop*2)
    	{
    		/*判断左子节点和右子节点哪个更小*/
    		if((iLoop+1)<=iEnd)
    		{
    			if(pToSort->iInput[iLoop+1]<pToSort->iInput[iLoop] )
    			{
    				iLoop = iLoop + 1;
    			}
    		}
    		/*
    		如果父节点已经小于最小的子节点，则没有必要再循环
    		*/
    		if(iLoop<=iEnd && pToSort->iInput[iStart] < pToSort->iInput[iLoop])
    		{
    			break;
    		}
    		swap(pToSort,iStart,iLoop);
    		iStart = iLoop;
    	}
    }
    
    int HeapSort(SqArr *pToSort)
    {
    	int iLoop;
    	int iLength;
    	iLength = pToSort->iLength;
    
    	for(iLoop = iLength/2;iLoop>=1;iLoop--)
    	{
    		HeapAdjust(pToSort,iLoop,iLength);
    	}
    	
    	printf("排序结果为：\n");
    	for(iLoop=1;iLoop<=iLength;iLoop++)
    	{
    		printf("%d ",pToSort->iInput[1]);
    		swap(pToSort,1,iLength-(iLoop-1));
    		HeapAdjust(pToSort,1,iLength-iLoop);
    	}
    	printf("\n");
    	return 0;
    }
    
    int main()
    {
    	char strInput[MAX_LEN];
    	char *pStrInput = NULL;
    	char *pStrtok = NULL;
    	int iLoop;
    	SqArr iToSort;
    
    	memset(strInput,0x00,sizeof(strInput));
    	memset(&iToSort,0x00,sizeof(SqArr));
    
    	printf("%s","请输入待排序数据，以逗号分隔，以回车结束：\n");
    	scanf("%s",&strInput);
    	pStrInput = strInput;
    
    	for(iLoop=1;;iLoop++,pStrInput=NULL)
    	{
    		pStrtok = strtok(pStrInput,",\n");
    		if(NULL == pStrtok)
    		{
    			break;	
    		}
    		iToSort.iInput[iLoop] = atoi(pStrtok);
    		iToSort.iLength = iLoop;
    	}
    	
    	HeapSort(&iToSort);
    
    	getchar();
    	return 0;
    }

这个算法有个很蛋疼的情况：按数组存储，最后输出的话是不能按数组下标输出的，因为他虽然是排序的完全二叉树，但又并不保证左子节点最小，或者是右子节点最小，只能确认按层次，上一层一定比下一层小（或大）。

所以在输出最后排序结果时，仍然需要不断的重新调整。