排序算法之选择排序|c++实现

引言

排序算法学习第二弹之选择排序，这也是入门的一个基础算法。

算法描述

1. 从序列中选择最大（小）的元素，放在序列的结束位置（下标为n-1）

2. 从剩下的未排序序列中继续选择最大（小）的元素，放在未排序序列末尾

3. 重复步骤2，直到排序完成

时间复杂度

可以看到selectionsort函数代码中有两层循环，因比时间复杂度为O(n^2)

代码实现

//每次找到最大（小）放在最左（右）端 
#include<bits/stdc++.h>
using namespace std;
template <typename T>
void selectionsort(T arr[],int len){
	for(int i=0;i<len -1;i++){
		T max =0;
		for(int j=1;j<len-i;j++){
			if(arr[j]>arr[max]){
				max=j;
			}
		}
		swap(arr[max],arr[len-i-1]);
	}
}
int main(){
	int arr[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
		int len = (int) sizeof(arr) / sizeof(*arr);
		selectionsort(arr, len);
		for (int i = 0; i < len; i++) {
			cout << arr[i] << " ";
		}
		cout << endl;
		float arrf[] = {17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.7, 5.4};
		int lenf = sizeof(arrf) / sizeof(*arrf);
		selectionsort(arrf, lenf);
		for (int i = 0; i < lenf; i++) {
			cout << arrf[i] << " ";
		}
		
		return 0;
}

运行截图：