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;
}