常见选择排序算法

基本思想：从待排序列中选择一个最小/最大元素，将此元素与当前待排序列的第一个元素进行交换，直到处理完所有元素，如果待排序列中只剩一个元素，则无需处理

#define _CRT_SECURE_NO_WARNINGS
#include
//选择待排序列中最小的元素
//将此元素与待排序列第一个元素进行交换
//重复以上操作直到下标i=min
//注意如果待排序列中只剩一个元素则无需处理
void SelectionSort(int a[],int n) {
	int i,j,temp,min;
	for ( i = 0; i < n-1; i++)//控制趟数
	{
		min = i;//当前最小元素下标
		for ( j = i+1; j < n; j++)
		{
			if (a[min]>a[j])//找待排序列中最小元素
			{
				min = j;//记录最小元素下标
			}
		}//找到了待排序列中的最小元素
		if (min!=i)//最后一个元素不进行处理
		{
			temp = a[min];
			a[min] = a[i];
			a[i] = temp;

		}	
	}
}
int main() {
	//一个待排序数组
	int a[8] = { 10,43,54,45,3,20,22,86 };
	//选择排序
	SelectionSort(a, 8);
	//输出排序结果
	for (int i = 0; i < 8; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

回顾二叉树的性质：二叉树的性质五

大根堆：首先是完全二叉树其次且满足： 根 ≥ geq ≥ 左孩子， 根 ≥ geq ≥ 右孩子

基本思想：将完全二叉树调整为满足根大于左和右的树，此时根为所有元素中最大的元素，输出此最大元素，将此元素与最后一个元素互换，继续调整，直到树中无元素

将非叶子结点全部检查一遍，看是否满足根大于左，根大于右，若不满足则进行调整
非叶子结点（分支结点、非终端结点）下标满足 i ≤ ⌊ n / 2 ⌋ i leq lfloor n/2rfloor i≤⌊n/2⌋

#define _CRT_SECURE_NO_WARNINGS
#include
//双亲结点i，左孩子2i，右孩子2i-1

void swap(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b=temp;
}
//将元素k为根的子树进行调整
void HeapAdjust(int a[], int k, int n) {
	a[0] = a[k];//将根结点a[k]暂存至a[0]
	for (int i = 2 * k; i <= n; i *= 2)//调整以a[k]为根结点的子树
	{
		if (i < n && a[i] < a[i + 1])//比较以a[k]为根结点的左右孩子
			i++;	//i++使得记录到较大孩子的下标
		if (a[0] >= a[i])//根结点大于较大孩子
			break; //满足大根堆要求，不进行处理
		else //根结点小于较大孩子
		{
			a[k] = a[i]; //将较大孩子放到根结点位置
			k = i;	//记录较大孩子位置
		}
	}
	a[k] = a[0];  //将根结点放到较大孩子位置，至此完成了以a[k]为根结点的子树的调整
}
//初始建堆
void BuildMaxHeap(int a[],int n) {
	//检查所有非叶子结点的树并进行调整
	//非叶子结点的下标满足 0 < i < floor(n/2)
	for (int i = n/2; i > 0; i--) //从i=n/2到1反复调整堆
	{
		HeapAdjust(a, i, n); //调整以i为根结点的子树
	}
}

//堆排序
void HeapSort(int a[],int n) {
	BuildMaxHeap(a, n);
	for (int i = n; i > 1; i--)
	{
		swap(&a[i],&a[1]);//将堆顶元素与最后一个叶子结点交换(堆顶元素加入到有序序列中)
		HeapAdjust(a, 1, i - 1);//交换后之前的堆顶元素放到了数组最后，下次重新调整堆时只处理a[i]到a[i-1]
	}
}

int main() {
	//一个待排序数组
	int a[8] = { 10,43,54,45,3,20,22,86 };
	//堆排序
	HeapSort(a, 8);
	//输出排序结果
	for (int i = 1; i < 8; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}