[数据结构与算法]排序算法②——选择排序&&堆排序

选择排序

基本思想

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

直接选择排序

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

参考代码

#include <stdio.h>

void Swap(int* m, int* n)
{
	int tmp = *m;
	*m = *n;
	*n = tmp;
}
//升序
//一次选出最大和最小
void SelectSort(int* arr, int n)
{
	int begin = 0;
	int end = n - 1;
	int i = 0;
	while (begin < end)
	{
		int i = 0;
		for (i = begin; i < end; i++)
		{
			if (arr[i] < arr[begin])
			{
				Swap(&arr[i], &arr[begin]);
			}
			if (arr[i] > arr[end])
			{
				Swap(&arr[i], &arr[end]);
			}
		}
		begin++;
		end--;
	}
}

int main()
{
	int arr[] = { 1,5,6,2,0,3,4,7,10,44,10,15,12,22,19,20 };
	SelectSort(arr, sizeof(arr) / sizeof(arr[0]));
	int i = 0;
	for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

直接选择排序的特性总结

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

堆排序

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

• 堆是一种顺序结构，它的特点与完全二叉树有些类似，因此可以通过提前了解二叉树（堆排序也在这个链接中~~~），来理解堆的概念。