#include<stdio.h>
#include<stdbool.h>
#define ElemType int
#define MaxSize 50



void Swap(ElemType& a, ElemType& b)//交换a,b两元素的值
{
	ElemType temp = a;
	a = b;
	b = temp;
}


void SelectSort(ElemType A[], int n)//简单选择排序
{
	int i = 0, min = 0, j = 0;//进行n-1趟
	for (i = 0; i < n-1; i++)
	{
		min = i;            //记录最小元素的位置
		for (j = i + 1; j <n; j++)//更新A[i]-A[i-1]中最小元素
		{
			if (A[j] < A[min])
				min = j;
		}
		if (min != i)//交换
			Swap(A[i], A[min]);
		
	}
}

void HeadAdjust(ElemType A[], int k, int len)//将元素为k的子树进行调整
{
	int i = 0;
	A[0] = A[k];//A[0]暂存子树根节点
	for (i = 2 * k; i <= len; i=i * 2)
	{
		if (i < len && A[i] < A[i + 1])
			i++;
		if (A[0] >= A[i])
			break;
		else
		{
			A[k] = A[i];
			k = i;
		}
	}
	A[k] = A[0];
}

void BuildMaxHelp(ElemType A[], int len)//反复调整堆
{
	for (int i = len / 2; i > 0; i--)
	{
		HeadAdjust(A, i, len);
	}
}

void HeapSort(ElemType A[], int len)
{
	int i = 0;
	BuildMaxHelp(A, len);//初始建堆
	for (i = len; i > 1; i--)
	{
		Swap(A[i], A[1]);//和堆底元素进行交换
		HeadAdjust(A, 1, i - 1);//把剩余的元素调整为堆
	}
}

void Print1(ElemType A[], int n)
{
	int i = 0;

	for (i = 0; i < n; i++)
	{
		printf("%d ", A[i]);
	}
}



void Print2(ElemType A[], int n)
{
	int i = 1;

	for (i = 1; i <= n; i++)
	{
		printf("%d ", A[i]);
	}
}


int main()
{
	int n = 8;
	ElemType A[] = { 7,8,9,2,5,1,3,6 };
	ElemType B[] =  {0,7,8,9,2,5,1,3,6 };//0位置不储存元素
	SelectSort(A, n);
	printf("简单选择排序后:");
	Print1(A, n);
	HeapSort(B, n);
	printf("\n堆排序后:");
	Print2(B,n);
	return 0;
}