洛谷—題解 P1177 【模闆】快速排序

原題連結P1177 【模闆】快速排序

題目描述

利用快速排序算法将讀入的N個數從小到大排序後輸出。

快速排序是資訊學競賽的必備算法之一。對于快速排序不是很了解的同學可以自行上網查詢相關資料，掌握後獨立完成。（C++選手請不要試圖使用STL，雖然你可以使用sort一遍過，但是你并沒有掌握快速排序算法的精髓。）

輸入輸出格式

輸入格式：

第1行為一個正整數N，第2行包含N個空格隔開的正整數ai，為你需要進行排序的數，資料保證了Ai不超過1000000000。

輸出格式：

将給定的N個數從小到大輸出，數之間空格隔開，行末換行且無空格。

題解：

所需知識：堆排序

Q：等等，不是說好了快排模版嗎？

A：額，好像是哦。

Q：那你快排過了嗎？

A：emmmm，并沒有

我相信各位小夥伴快排都是了熟于心的，是以在這裡我就不用快排了（快排不做特殊處理—合理選擇基準值，在這裡是過不了的）。在這裡堆排序我采用的是向下調整的方式，建構一個最小堆的形式。

代碼如下：

#include <stdio.h>

int h[1000001];
int n;

void swap(int x,int y)
{
	int t;
	t=h[x];
	h[x]=h[y];
	h[y]=t;
	return;
}

void siftdown(int i)
{
	int t,flag=0;

	while(i*2<=n&&flag==0)
	{
		if(h[i]>h[i*2])
			t=i*2;
		else
			t=i;

		if(i*2+1<=n)
		{
			if(h[t]>h[i*2+1])
				t=i*2+1;
		}

		if(t!=i)
		{
			swap(t,i);
			i=t;
		}
		else
			flag=1;
	}
	return;
}

void create()
{
	int i;
	for(i=n/2;i>=1;i--)
	{
		siftdown(i);
	}
	return;
}

int deletemax()
{
	int t;
	t=h[1];
	h[1]=h[n];
	n--;
	siftdown(1);
	return t;
}

int main()
{
	int i,num;

	scanf("%d",&num);

	for(i=1;i<=num;i++)
	{
		scanf("%d",&h[i]);
	}
	n=num;

	create();

	for(i=1;i<=num;i++)
		printf("%d ",deletemax());

	getchar();
	getchar();

	return 0;
}
           

新手上路，希望大家多多批評，多多交流，多多指教。

祝各位小夥伴，學的開心，A的愉快，早日成為大牛。

我是Mario，一個立志考進MIT的程式猿。