NzN的数据结构--选择排序

接上文，本章我们来介绍选择排序。先三连后看才是好习惯~~~

一、基本思想

二、直接选择排序

三、堆排序

一、基本思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

二、直接选择排序

在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//选择排序
void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		for (int i = begin + 1; i <= end; i++) 
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&a[begin], &a[mini]);
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}

三、堆排序

堆排序算法我们已经在二叉树part2部分详细讲解过了，如果还不理解，可以再返回学习一下。

堆排序(Heapsort)是指利用堆积树（堆）所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

//大堆的向下调整算法
void AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		//默认左孩子大，假设错误就更新一下  
		if (child + 1 < size && a[child] < a[child + 1]) //右孩子存在且右孩子大于左孩子  
		{
			++child; // child原本是左孩子，+1变成右孩子  
		}
 
		//如果子节点大于父节点则交换 
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
 
//升序建大堆，降序建小堆
//建小堆如果想要升序，堆顶元素在对应位置，剩余元素重新建小堆，时间复杂度大大增加
void HeapSort(int* a, int n)
{
	//对数组直接建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
 
	// O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);//上面建的大堆，根节点最大，把大的数据往后放
		AdjustDown(a, end, 0);//新的根节点可能会破坏大堆性质，需要向下调整
		end--;
	}
}

堆排序的特性总结：