C語言排序演演算法之選擇排序(直接選擇排序,堆排序)

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
 
//交換
void Swap(int* mini, int* maxi)
{
	int tmp = *mini;
	*mini = *maxi;
	*maxi = tmp;
}
 
//列印
void Print(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}
 
//直接選擇排序
void SelectSort(int *a,int n)
{
	//下標
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mini = begin, maxi = end;
		//選出最大的給maxi，選出最小的給mini
		for (int i=begin;i<=end;++i)
		{
			if (a[i]>a[mini])//升序
			{
				mini = i;   //改兩個if的符號即可實現升序、降序轉換。
			}
			if (a[i] <a[maxi])
			{
				maxi = i;
			}
		}
		//交換
		Swap(&a[begin],&a[mini]);
        //因為還有一種特殊情況，就是begin跟maxi重疊，然後執行第一次交換之後，maxi記錄的是最小值
        if (begin == maxi)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		++begin;
		--end;
	}
}
直接選擇排序
//void SelectSort(int* a, int n)//(升序)
//{
//	for (int j=0;j<n-1;j++)//整體遍歷
//	{
//		for (int i=j+1;i<n;i++)//遍歷比較
//		{
//			if (a[j] > a[i])//比較交換
//			{
//				int tmp = a[j];
//				a[j] = a[i];
//				a[i] = tmp;
//			}
//		}
//	}
//}
int main()
{
	int a[10] = { 3,5,9,7,4,2,1,6,0,8 };
	SelectSort(a, sizeof(a) / sizeof(a[0]));
	//列印
	Print(a, sizeof(a) / sizeof(a[0]));
	return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//列印資料
void Printf(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
}
 
//交換,傳地址
void Swap(int* child, int* parent)
{
	int tmp = *child;
	*child = *parent;
	*parent = tmp;
}
//向下調整演演算法
//從根節點開始，如果是建立小堆選出左右孩子中小的那一個，跟父親比較，如果比父親小就交換
void AdjustDwon(int* a, int n, int root)//建小堆
{
	int parent = root;//父親節點
	int child = parent * 2 + 1;//預設是左孩子
	while (child < n)//葉子節點下標不會超過陣列總下標數n
	{
		//選出左右孩子中最小的那一個
		if (child+1 < n&& a[child + 1] < a[child])
		{
			child += 1;//用a[child]與父親節點a[parent]比較
		}
		if (a[child] < a[parent])
		{
			//交換,傳地址
			Swap(&a[child], &a[parent]);
			//交換後，將child,作為根節點繼續向下調整，持續建堆
			parent = child;
			//新的左孩子
			child = parent * 2 + 1;
		}
		else
		{
			break;//如果不用交換，直接結束迴圈
		}
	}
}
//堆的建立
//大堆要求：樹中所有的父親都>=孩子,根是最大的
//小堆要求：書中所有的父親都<=孩子,根是最小的
//建大堆排升序，建小堆排降序
//建堆的時間複雜度是O(N);
void HeapSort(int *a,int n)
{
	//找父親節點
	for (int i=(n-1-1)/2;i>=0;--i)
	{
		//向下調整演演算法
		AdjustDwon(a,n,i);
	}
    //大堆或小堆建立完畢，排序
	//用主根節點與最後一個節點交換位置
	int end = n - 1;
	while (end>0)
	{
		//交換，傳地址
		Swap(&a[0],&a[end]);
		//繼續向下調整
		AdjustDwon(a,end,0);
		--end;
	}
}
//選擇排序—堆排序
int main()
{
	int a[10] = {9,2,5,4,3,1,6,7,8,0};
	//堆的建立
	HeapSort(a,sizeof(a) / sizeof(a[0]));
	//列印資料
	Printf(a,sizeof(a) / sizeof(a[0]));
	return 0;
}