heap sort.cpp

来自「经典算法实现」· C++ 代码 · 共 88 行

#include "Sort.h"


/*extern int num;
extern int *arr;*/


/*void swap(int &i,int &j){
	int temp=i;
	i= j;
	j=temp;
}*/

void Hadjust(int start,int end){


	//int current=start;// 逻辑上的编号，从1开始

	int left=-1,right=-1;

	if (start*2 <=end)
	{
		left = start*2;
		if (left+1<=end)
			right=left+1;
	}

	else return;

	bool lorr=0;

	if (right>=0)
	{
		if (arr[left-1] <arr[right -1])
		{
			lorr =1;
		}
	}

	if (lorr)//右边大
	{
	
		if (arr[start-1] < arr[right-1] )
		{
			
			swap(arr[start-1],arr[right-1]);
			/*int temp = arr[current-1];
			arr[current-1] = arr[right-1];
			arr[right-1] = temp;*/

			Hadjust(right,end);
		}
	}

	else {

		if (arr[start-1] < arr[left-1] )
		{
			swap(arr[start-1],arr[left-1]);
			Hadjust(left,end);
		}
	}
		
}

void creatHeap(){

	for (int i=(num/2);i>=1;i--)
	{
		Hadjust(i,num);
	}


}


void heapSort(){

	creatHeap();

	for (int i=num;i>1;i--)
	{
		swap(arr[0],arr[i-1]);
		Hadjust(1,i-1);

	}
	
}