C语言数据结构中堆排序的分析总结

void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])//如果孩子大于父亲，则将它们交换。
		{
			Swap(&a[child], &a[parent]);
            //迭代过程：
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
            //如果孩子小于父亲，结束调整
			break;
		}
	}
}

void AdjustDown(HPDataType* a, int size, int root)
{
	int parent = root;
	int child = parent * 2 + 1;//左孩子
	while (child < size)
	{
		if (child + 1 < size && a[child] < a[child + 1])//如果左孩子小于右孩子，则选右孩子
		{
			//务必加上child+1，因为当child=size-1时，右孩子下标是size，对其接引用会越界访问。
            child++;//右孩子的下标等于左孩子+1
		}
		if (a[child] > a[parent])//让较大的孩子与父亲比较，如果孩子大于父亲，则将它们交换。
		{
			Swap(&a[child], &a[parent]);
            //迭代过程
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

for (int i = 1; i < n; i++)
{
	AdjustUp(a, i);
}

//n代表数组元素个数，j的初始值代表最后一个元素的父亲下标
for (int j = (n - 1 - 1) / 2; j >= 0; j--)
{
	AdjustDown(a, n, j);
}

    int end = n - 1;//n代表数组元素的个数
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}

void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}
 
void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void AdjustDown(int* a, int n, int root)
{
	int child = 2 * root + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] < a[child+1])
		{
			child++;
		}
		if (a[child] > a[root])
		{
			Swap(&a[child], &a[root]);
			root = child;
			child = 2 * root + 1;
		}
		else
		{
			break;
		}
	}
}
 
void HeapSort(int* a, int n)
{
	//建大堆(向上调整)
	//for (int i = 1; i < n; i++)
	//{
	//	AdjustUp(a, i);
	//}
 
	//建大堆(向下调整)
	for (int j = (n - 1 - 1) / 2; j >= 0; j--)
	{
		AdjustDown(a, n, j);
	}
	//升序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}
void printarr(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
 
int main()
{
	int arr[10] = { 9,2,4,8,6,3,5,1,10 };
	int size = sizeof(arr) / sizeof(arr[0]);
	HeapSort(arr, size);
	printarr(arr, size);
	return 0;
}