常见的排序方法—选择排序

2 选择排序

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

// 直接选择排序
void SelectSort(int* a, int n);
 
 
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);

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

图解

第一排序后的结果应该是：
最小值：（在下标为0的位置）

最大值：（在下标为9的位置）

依次类推找出次小、次大。

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

void SelectSort(int* a, int n)
{
    
	assert(a);
	int begin = 0, end = n - 1;
	while (begin < end)
	{
    
		int min = begin, max = end;
		for (int i = begin; i <= end; ++i)
		{
    

			if (a[min] > a[i])
				min = i;
			if (a[max] < a[i])
				max = i;
		}
		Swap(&a[begin], &a[min]);

		if (begin == max)
			max = min;

		Swap(&a[end], &a[max]);
		++begin;
		--end;

	}

}

·
·
·

2.3 堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是
通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
当然不了解堆的先看下这个;堆的实现

//向下调整
void AdjustDwon(int* a, int n, int root)
{
    
	assert(a);
	int parent = root;
	int child = parent * 2 + 1;

	while (child < n)
	{
    
		//在两个孩子中选出最大的那个
		if (child + 1 < n && a[child] < a[child + 1])
			++child;

		//调整
		if (a[child] > a[parent])
		{
    
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
    
			break;
		}
	}
}

建堆，先从最后两个叶子上的根(索引为(n - 2) / 2开始建堆
 先建最小的堆，直到a[0]  (最大的堆)
 这就相当于在已经建好的堆上面，新加入一个
 根元素，然后向下调整，让整个完全二叉树
 重新满足堆的性质

void HeapSort(int* a, int n)
{
    
	assert(a);

	//建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
    
		AdjustDwon(a, n, i);
	}

	//end:表示最后一个位置
	//排序
	int end = n - 1;
	while (end > 0)
	{
    
		Swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);
		--end;
	}
}

最后排序方法：调整后的大堆a[0]位置是最大值，我们可以让它与最后一个交换然后调整，依次类推我们就可以排出升序了。
第一次交换：（未向下调整）

调整：（次小的跑到堆顶了这个n-1还是一个大堆，剩下的依次类推）