本篇博文旨在介紹內(nèi)排序算法中的選擇排序；詳細(xì)介紹了選擇排序和堆排序，并通過時(shí)間復(fù)雜度和空間復(fù)雜度進(jìn)行了分析；最后實(shí)現(xiàn)了兩種選擇排序的代碼

選擇排序

基本思想

這里按照升序舉例

1、選出當(dāng)前范圍中的最小值

2、將該最小值放入當(dāng)前范圍的第一個(gè)位置

3、縮小排序的范圍，直到只有范圍中只有一個(gè)元素為止

圖解

選擇排序的時(shí)間復(fù)雜度和空間復(fù)雜度

選擇排序時(shí)間復(fù)雜度為O（N* N）

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

下一趟中少1次，所以其每趟排序比較的次數(shù)是一個(gè)等差數(shù)列

故其時(shí)間復(fù)雜度是一個(gè)N方級別

由于沒有利用額外的空間，其空間復(fù)雜度為O（1）

選擇排序普通版本代碼的實(shí)現(xiàn)

這里運(yùn)用模板，利用防函數(shù)來控制是升序還是降序

#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進(jìn)行初始化	int max = 0;	//進(jìn)行選擇排序	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);}
選擇排序的優(yōu)化
每次找出范圍內(nèi)的最大值和最小值，同時(shí)放入兩邊的位置
雖然效率高了一倍，其還是N方級別，所以時(shí)間復(fù)雜度還是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;}//選擇排序的優(yōu)化版本//時(shí)間復(fù)雜度：O(N* N)//思想：//每次循環(huán)在找出最小值的同時(shí)，找出最大值//效率會提高一倍，但是時(shí)間復(fù)雜度的數(shù)量級并沒有變//注意：//  同時(shí)置換最大值和最小值時(shí)，如果最大值出現(xiàn)在begin的位置上，交換兩次會打亂//在置換的時(shí)候需要加入一個(gè)判斷，具體如代碼所示////  [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)		{			//找出最小的數(shù)的下標(biāo)和最大數(shù)的下標(biāo)			if (a[i] < a[minIndex])				minIndex = i;			if (a[i] > a[maxIndex])				maxIndex = i;		}		//交換最小的數(shù)和第一個(gè)數(shù)		swap(a[minIndex], a[begin]);		//防止位置沖突而被打亂		if (maxIndex == begin)			maxIndex = minIndex;		//交換最大的數(shù)和最后一個(gè)數(shù)		swap(a[maxIndex], a[end]);		//區(qū)間向中間減少		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]));}
堆排序
堆
堆是一種數(shù)據(jù)結(jié)構(gòu)，是一個(gè)數(shù)組對象
大堆：堆頂元素是最大值
小堆：堆頂元素是最小值
基本思想
按升序舉例
我們選用大堆，每次選出最大的數(shù)，將其和最后一個(gè)數(shù)進(jìn)行交換（最大的數(shù)放入了最后的位置）
然后將排序的范圍縮小（將最后一個(gè)位置的數(shù)排除排序范圍）
排序的時(shí)間復(fù)雜度以及空間復(fù)雜度
堆排序單趟排序的時(shí)間復(fù)雜度為O（logN）
需要排N次，所以堆排序的時(shí)間復(fù)雜度為O（N* logN）
空間復(fù)雜度為O（1）
堆排序的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：排序比較快，一般排序的時(shí)間復(fù)雜度為O（N* N）
而堆排序達(dá)到了O（N* logN）
缺點(diǎn)：堆排序只能排存儲于數(shù)組中的元素，故在某些場合無法使用
堆排序的實(shí)現(xiàn)
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){	//構(gòu)建一個(gè)堆	int* heap = new int[n];	for (size_t i = 0; i < n; i++)	{		heap[i] = a[i];	}	//向下調(diào)整	for (int i = (n-2)/2; i >= 0; --i)	{		AdjustDown(heap, n, i);	}	//堆排序的實(shí)質(zhì)性部分	int end = n - 1;	//先將第一個(gè)元素和最后一個(gè)元素的值進(jìn)行交換	//然后將最后一個(gè)元素不再視為堆內(nèi)的內(nèi)容，縮小排序范圍	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]));}