本篇博文旨在介绍内排序算法中的选择排序；详细介绍了选择排序和堆排序，并通过时间复杂度和空间复杂度进行了分析；最后实现了两种选择排序的代码

选择排序

基本思想

这里按照升序举例

1、选出当前范围中的最小值

2、将该最小值放入当前范围的第一个位置

3、缩小排序的范围，直到只有范围中只有一个元素为止

图解

选择排序的时间复杂度和空间复杂度

选择排序时间复杂度为O（N* N）

在第一趟排序中，需要比较N-1次

下一趟中少1次，所以其每趟排序比较的次数是一个等差数列

故其时间复杂度是一个N方级别

由于没有利用额外的空间，其空间复杂度为O（1）

选择排序普通版本代码的实现

这里运用模板，利用防函数来控制是升序还是降序

#PRagma once#include<iostream>using namespace std;void Print(int* arr, size_t n){	for (size_t i = 0; i < n; ++i)	{		cout << arr[i] << " ";	}	cout << endl;}//升序template<typename T>struct Greater{	bool Operator()(T& t1, T& t2)	{		return t1 > t2;	}};//降序template<typename T>struct Less{	bool operator()(T& t1, T& t2)	{		return t1 < t2;	}};template<typename T,typename Com = Greater<int>>void SelectSort(T* arr,size_t n){	//对max进行初始化	int max = 0;	//进行选择排序	for (size_t i = 0; i < n-1; ++i)	{		max = i;		for (size_t j = i; j < n; ++j)		{			if (Com()(arr[max], arr[j]))				max = j;		}		if (max != i)			swap(arr[max], arr[i]);	}}void TestSelectSort(){	int arr[10] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };	SelectSort<int,Less<int>>(arr, 10);	cout << "选择排序:" << endl;	Print(arr, 10);}
选择排序的优化
每次找出范围内的最大值和最小值，同时放入两边的位置
虽然效率高了一倍，其还是N方级别，所以时间复杂度还是O（N* N）
#include<iostream>using namespace std;#include<assert.h>void Print(int* a,size_t n){	assert(a);	for (size_t i = 0; i < n; ++i)	{		cout << a[i] << " ";	}	cout << endl;}//选择排序的优化版本//时间复杂度：O(N* N)//思想：//每次循环在找出最小值的同时，找出最大值//效率会提高一倍，但是时间复杂度的数量级并没有变//注意：//  同时置换最大值和最小值时，如果最大值出现在begin的位置上，交换两次会打乱//在置换的时候需要加入一个判断，具体如代码所示////  [begin,end]void SelectSort(int* a, size_t n){	assert(a);	size_t begin = 0;	size_t end = n - 1;	size_t minIndex = 0;	size_t maxIndex = 0;	while (begin < end)	{		minIndex = begin;		maxIndex = end;		for (size_t i = begin + 1; i <= end; ++i)		{			//找出最小的数的下标和最大数的下标			if (a[i] < a[minIndex])				minIndex = i;			if (a[i] > a[maxIndex])				maxIndex = i;		}		//交换最小的数和第一个数		swap(a[minIndex], a[begin]);		//防止位置冲突而被打乱		if (maxIndex == begin)			maxIndex = minIndex;		//交换最大的数和最后一个数		swap(a[maxIndex], a[end]);		//区间向中间减少		begin++;		end--;	}}void TestSelectSort(){	int a[10] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 };	SelectSort(a, sizeof(a) / sizeof(a[0]));	Print(a, sizeof(a) / sizeof(a[0]));}
堆排序
堆
堆是一种数据结构，是一个数组对象
大堆：堆顶元素是最大值
小堆：堆顶元素是最小值
基本思想
按升序举例
我们选用大堆，每次选出最大的数，将其和最后一个数进行交换（最大的数放入了最后的位置）
然后将排序的范围缩小（将最后一个位置的数排除排序范围）
排序的时间复杂度以及空间复杂度
堆排序单趟排序的时间复杂度为O（logN）
需要排N次，所以堆排序的时间复杂度为O（N* logN）
空间复杂度为O（1）
堆排序的优缺点
优点：排序比较快，一般排序的时间复杂度为O（N* N）
而堆排序达到了O（N* logN）
缺点：堆排序只能排存储于数组中的元素，故在某些场合无法使用
堆排序的实现
void AdjustDown(int* a, size_t n, size_t i){	int parent = i;	int child = parent * 2 + 1;	while (child < n)	{		//找出孩子的最大值		if (child + 1 < n && a[child+1] > a[child])			child++;		if (a[child]>a[parent])		{			swap(a[child], a[parent]);			parent = child;			child = child * 2 + 1;		}		else		{			break;		}	}}void HeapSort(int* a,size_t n){	//构建一个堆	int* heap = new int[n];	for (size_t i = 0; i < n; i++)	{		heap[i] = a[i];	}	//向下调整	for (int i = (n-2)/2; i >= 0; --i)	{		AdjustDown(heap, n, i);	}	//堆排序的实质性部分	int end = n - 1;	//先将第一个元素和最后一个元素的值进行交换	//然后将最后一个元素不再视为堆内的内容，缩小排序范围	while (end>0)	{		swap(heap[0], heap[end]);		end--; 		AdjustDown(heap, end, 0);	}	//打印	for (size_t i = 0; i < 10; i++)	{		cout << heap[i] << " ";	}	cout << endl;}void TestHeapSort(){	int a[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19 };	HeapSort(a,sizeof(a)/sizeof(a[0]));}