堆排序（C语言版）

一.堆排序

1.1.利用上下调整法实现堆排序

第一步：建堆

好了，每次建堆都要问自己下，要建的是什么堆？大堆还是小堆呢？

我们这里就一一来实现，先建大堆

void Print(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
void Swap(int* p1, int* p2)
{
	int* tmp = *p1;
	* p1=*p2;
	*p2 = tmp;
}
void Adjustup(int* arr2, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr2[child]>arr2[parent])//注意我们是建的大堆
		{
			Swap(&arr2[child], &arr2[parent]);//传地址才能改变值
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void Heapsort(int* arr, int n)
{
	//建立堆
	//问题是：你是建大堆还是小堆？
	//我们这里要建大堆
	for (int i = 1; i < n; i++)
	{
		Adjustup(arr, i);//利用向上调整法
	}
	Print(arr,n);
}

如果你实现过堆的代码相信上面的代码对你来说绝对小菜一碟

由于我们直接调用了打印函数，那么我们来看看结果吧。

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void Print(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
void Swap(int* p1, int* p2)
{
	int* tmp = *p1;
	* p1=*p2;
	*p2 = tmp;
}
void Adjustup(int* arr2, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr2[child]>arr2[parent])//注意我们是建的大堆
		{
			Swap(&arr2[child], &arr2[parent]);//传地址才能改变值
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void Heapsort(int* arr, int n)
{
	//建立堆
	//问题是：你是建大堆还是小堆？
	//我们这里要建大堆
	for (int i = 1; i < n; i++)
	{
		Adjustup(arr, i);//利用向上调整法
	}
	Print(arr,n);
}
int main()
{
	int arr[] = { 4,6,2,1,5,8,2,9 };
	int sz = sizeof(arr) / sizeof(int);
	Heapsort(arr, sz);
	return 0;
}

结果：

这个是不是就满足了大堆

第二步：如何实现排序呢？（别看上面是从大到小排好的，这只是一个巧合，我们要学会正确的排序法）

如果你对此不清楚，那么我要开始表演了。

如果你想，我们是大堆，这说明最大的数即是堆顶，如果我交换数组首尾位置，然后这是不是不再是一颗完全二叉树了，那么如果我再通过向下调整法来排好，重复操作，是不是就会得到一个从小到大的数组，那么不就排好序了，想到这，相信你肯定联想到了堆的删除操作，下面就让我们利用堆的删除来实现它吧！

void Swap(int* p1, int* p2)
{
	int* tmp = *p1;
	* p1=*p2;
	*p2 = tmp;
}
void Adjustdown(int* arr3, int n, int parent)
{
	int child = parent * 2 + 1;//假设左孩子大
	//注意我们建的是大堆
	while (child < n)
	{
		if ((child + 1) < n && (arr3[child] < arr3[child + 1]))
		{
			child++;
		}
		if (arr3[parent] < arr3[child])
		{
			Swap(&arr3[parent], &arr3[child]);//交换父子位置
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


//堆建好了，现在实现第二步：堆删除
int end = n - 1;
while (end > 0)
{
	//堆删除分以下几步：
	//第一步:首尾元素互换
	Swap(&arr[0], &arr[end]);
	//第二步：向下调整法调整树根
	Adjustdown(arr, end, 0);
	//第三步：删除堆尾
	end--;
}

这对于学过实现堆的你来说依然so easy。

那么就让我们整体检查代码的正确性：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void Print(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
void Swap(int* p1, int* p2)
{
	int* tmp = *p1;
	* p1=*p2;
	*p2 = tmp;
}
void Adjustup(int* arr2, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr2[child]>arr2[parent])//注意我们是建的大堆
		{
			Swap(&arr2[child], &arr2[parent]);//传地址才能改变值
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void Adjustdown(int* arr3, int n, int parent)
{
	int child = parent * 2 + 1;//假设左孩子大
	//注意我们建的是大堆
	while (child < n)
	{
		if ((child + 1) < n && (arr3[child] < arr3[child + 1]))
		{
			child++;
		}
		if (arr3[parent] < arr3[child])
		{
			Swap(&arr3[parent], &arr3[child]);//交换父子位置
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void Heapsort(int* arr, int n)
{
	//建立堆
	//问题是：你是建大堆还是小堆？
	//我们这里要建大堆
	for (int i = 1; i < n; i++)
	{
		Adjustup(arr, i);//利用向上调整法
	}
	Print(arr,n);
	//堆建好了，现在实现第二步：堆删除
	int end = n - 1;
	while (end > 0)
	{
		//堆删除分以下几步：
		//第一步:首尾元素互换
		Swap(&arr[0], &arr[end]);
		//第二步：向下调整法调整树根
		Adjustdown(arr, end, 0);
		//第三步：删除堆尾
		end--;
	}
	Print(arr, n);
}
int main()
{
	int arr[] = { 4,6,2,1,5,8,2,9 };
	int sz = sizeof(arr) / sizeof(int);
	Heapsort(arr, sz);
	return 0;
}

结果：

如果你是要从大到小排序，操作如下：

建小堆-》堆的尾删

整体而言有三处改动：

1.在void Adjustup(int* arr2, int child)函数中这个语句要改变符号，因为是建小堆了。
?? ??? ?if (arr2[child]>arr2[parent])//
2.在void Adjustdown(int* arr3, int n, int parent)这个函数中这两处符号也要改变，原因是因为你现在是小堆，向下调整法肯定要调整
?? ??? ?if (arr3[child] < arr3[child + 1]))
?? ??? ?if (arr3[parent] < arr3[child])
?

整体如下：

//表示原来的语句

//arr2[child]>arr2[parent]
arr2[child]<arr2[parent]

//if ((child + 1) < n && (arr3[child] < arr3[child + 1]))
if ((child + 1) < n && (arr3[child] > arr3[child + 1]))


//if (arr3[parent] < arr3[child])
if (arr3[parent] > arr3[child])

改完之后结果如下：

现在我们就要对这个算法进行分析：

时间复杂度:建堆为O(NlogN)+选数O(N-1logN)

得出结果：O(NlogN)(非常牛逼的算法）

1.2.只利用向下调整法实现堆排序

大家看上面的代码是不是感觉一个排序要写这么麻烦好不方便啊，是的，我们其实可以只通过一个向下调整就可以实现堆排序，下面看看我的表演吧！

步骤还是和上面一样，其实就改变了建堆的过程，我们现在是通过向下调整法建堆。

看代码：

for (int i = ; i ; i)
{
	Adjustdown(arr,,);
}

我们就是要把上面的空缺填好，那么该如何写呢？

我要告诉你一个概念：向下调整建堆是从第一个非叶子节点开始调整，我们肯定要调整到0

所以我们可以这样写：

for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
	Adjustdown(arr,n,i);
}

其他部分不用改变，所以整体代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void Print(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
void Swap(int* p1, int* p2)
{
	int* tmp = *p1;
	* p1=*p2;
	*p2 = tmp;
}
void Adjustdown(int* arr3, int n, int parent)
{
	int child = parent * 2 + 1;//假设左孩子大
	//注意我们建的是大堆
	while (child < n)
	{
		if ((child + 1) < n && (arr3[child] < arr3[child + 1]))
		{
			child++;
		}
		if (arr3[parent] < arr3[child])
		{
			Swap(&arr3[parent], &arr3[child]);//交换父子位置
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void Heapsort(int* arr, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		Adjustdown(arr,n,i);
	}
	Print(arr, n);
	//堆建好了，现在实现第二步：堆删除
	int end = n - 1;
	while (end > 0)
	{
		//堆删除分以下几步：
		//第一步:首尾元素互换
		Swap(&arr[0], &arr[end]);
		//第二步：向下调整法调整树根
		Adjustdown(arr, end, 0);
		//第三步：删除堆尾
		end--;
	}
	Print(arr, n);
}
int main()
{
	int arr[] = { 4,6,2,1,5,8,2,9 };
	int sz = sizeof(arr) / sizeof(int);
	Heapsort(arr, sz);
	return 0;
}

结果：

来我们该讨论该算法时间复杂度情况了

建堆O(N)+选数O(NlogN)

时间复杂度：O(N*logN)

注意：该写法不仅简单（比上面那种），而且效率也比上面的高。