数据结构 堆排序

首先  了解一下堆排序的思想

堆排序把数组看作是一个 完全二叉树  倒数第二层节点

要么没有孩子

要么只有一个孩子 

要么有两个孩子

假设当前节点的下标为i

那么如果他有右孩子  右孩子的下标为2*i+2

那么如果他有左孩子  左孩子的下标为2*i+1

如果我们想把数组从小到大排序  那我们可以把二叉树假设成大根堆  :

即  当前层的下一层的每一个节点的值都小于当前层的节点的值

我们会通过调整让这个二叉树总是大根堆

排序的方法 :

经过调整

最上面的节点总是最大的 

 我们让最大的这个节点和最后面的节点(最后一层的最右边的节点)交换 

然后将最后的这个节点放入到数组中 

同时将这个最后一个节点视为从二叉树上移除 

继续调整二叉树   调整完  最上面的节点又是最大的了 

但是没有开始移除的那个节点大  是第二大的  ....如此往复

就直到二叉树中没有节点了  我们的数组也就排序好了

我们的堆排序分为构建堆树   和  排序两个部分  组成 

void  HeapSort(int arr[], int nLen)
{
	//参数校验
	if (arr == NULL || nLen <= 1)
	{
		return;
 
	}
	//构建堆树
	for (int i = nLen / 2 - 1; i >=0; i--)
	{
        //将树调整成大根堆
		Adjust(arr,nLen,i);
	}
	//排序
	for (int i = nLen - 1; i > 0; i--)//每次排完一个节点  二叉树中视为移除了一个节点
	{
        //顶部节点与最后一个节点交换
		arr[0] = arr[0] ^ arr[i];
		arr[i] = arr[0] ^ arr[i];
		arr[0] = arr[0] ^ arr[i];
		//再调整成大根堆(最上面的arr[0]是最大的节点)
		Adjust(arr, i, 0);
 
 
	}
		
 
	
}

其中 堆排序中用到的调整

void Adjust(int arr[], int nLen, int index)
{
	
	while (1)
	{
		if (2 * index + 2 < nLen)//两个孩子
		{
			
			//找到大的孩子
			int idex= arr[2 * index + 2] > arr[2 * index + 1] ? 2 * index + 2 : 2 * index + 1;
			//大孩子和当前节点比较
			  //大孩子更大  交换
			if (arr[idex] > arr[index])
			{
				arr[index] = arr[idex] ^ arr[index];
				arr[idex] = arr[idex] ^ arr[index];
				arr[index] = arr[idex] ^ arr[index];
				index = idex;//以孩子为节点继续调整
			}
			//否则结束
			else 
				break;
			
	
 
		}
		//一个孩子
		else if (2 * index + 1 < nLen)
	    {
			int idex = 2 * index + 1;
			//和孩子就比较
			  //比孩子小  交换
			if (arr[index] < arr[idex])
			{
				arr[index] = arr[idex] ^ arr[index];
				arr[idex] = arr[idex] ^ arr[index];
				arr[index] = arr[idex] ^ arr[index];
				
			}
			//比孩子大 结束
			else
				break;
			
			
	    
	    }
		//没孩子  结束
	    else
	    {
	    	break;
	    }
		
	}
}

主函数中 我们定义了一个数组用来测试

  

int arr[10] = { 9,8,7,6,5,4,3,3,1,0 };
	HeapSort(arr, 10);
	for (int val : arr)
	{
		cout << val << " ";
	}

测试结果如下

 

完整代码如下

#include
using namespace std;
 
void Adjust(int arr[], int nLen, int index)
{
	
	while (1)
	{
		if (2 * index + 2 < nLen)//两个孩子
		{
			
			//找到大的孩子
			int idex= arr[2 * index + 2] > arr[2 * index + 1] ? 2 * index + 2 : 2 * index + 1;
			//大孩子和当前节点比较
			  //大孩子更大  交换
			if (arr[idex] > arr[index])
			{
				arr[index] = arr[idex] ^ arr[index];
				arr[idex] = arr[idex] ^ arr[index];
				arr[index] = arr[idex] ^ arr[index];
				index = idex;
			}
			//否则结束
			else 
				break;
			
	
 
		}
		//一个孩子
		else if (2 * index + 1 < nLen)
	    {
			int idex = 2 * index + 1;
			//和孩子就比较
			  //比孩子小  交换
			if (arr[index] < arr[idex])
			{
				arr[index] = arr[idex] ^ arr[index];
				arr[idex] = arr[idex] ^ arr[index];
				arr[index] = arr[idex] ^ arr[index];
				
			}
			//比孩子大 结束
			else
				break;
			
			
	    
	    }
		//没孩子  结束
	    else
	    {
	    	break;
	    }
		
	}
}
void  HeapSort(int arr[], int nLen)
{
	//参数校验
	if (arr == NULL || nLen <= 1)
	{
		return;
 
	}
	//构建堆树
	for (int i = nLen / 2 - 1; i >=0; i--)
	{
		Adjust(arr,nLen,i);
	}
	//排序
	for (int i = nLen - 1; i > 0; i--)
	{
		arr[0] = arr[0] ^ arr[i];
		arr[i] = arr[0] ^ arr[i];
		arr[0] = arr[0] ^ arr[i];
		//调整
		Adjust(arr, i, 0);
 
 
	}
		
 
	
}
 
int main()
{
	int arr[10] = { 9,8,7,6,5,4,3,3,1,0 };
	HeapSort(arr, 10);
	for (int val : arr)
	{
		cout << val << " ";
	}
	return 0;
}