排序算法之选择排序
[toc]
介绍
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。 选择排序算法是在一组数中有选择的从大到小或者小到大进行排序，其逻辑是：
逻辑
在一组数据中从第一个数开始比较出该组数据中最小数，然后将其与第一个数互换位置，然后第二个数再依次从后面的数再进行比较，找出全数组中第二小的数，再与第二个数互换位置，剩余的数依次类推，即可得出数组的排序。列如：
数组{6，3， 5， 9， 4， 7， 8}
首先以[0 , 7)分别为上列数组元素的索引
第一次比较以i = 0（就是6的索引）将6与{3, 5, 9, 4, 7, 8}中的元素进行比较（如：6大于3，则将比较索引1赋值给i,再将 i = 1的数与后面的数进行比较），找出的最小值为3，则将3与6位置互换，依次就完成了选择排序算法的整个逻辑。
实现
Golnag:
func SelectionSort(arr []int) []int {
for i := 0; i < len(arr); i++ {
tag := i
for j := i + 1; j < len(arr); j++ {
if arr[tag] > arr[j] {
tag = j
}
}
arr[i], arr[tag] = arr[tag], arr[i]
}
return arr
}
测试：
func main() {
arr := []int{2, 0, 44, 1, 2, 34, 32, 10}
fmt.Println(SelectionSort(arr)) //打印：[0 1 2 2 10 32 34 44]
}
C++：
#include <iostream>
using namespace std;
template<typename T>
void selectionSort(T arr[], int n){
for(int i = 0 ; i < n ; i ++){
int minIndex = i;
for( int j = i + 1 ; j < n ; j ++ )
if( arr[j] < arr[minIndex] )
minIndex = j;
swap( arr[i] , arr[minIndex] );
}
}
如下是测试：
int main() {
// 测试模板函数，传入整型数组
int a[10] = {2,6,12,32,54,77,53,45,31,200};
selectionSort( a , 10 );
for( int i = 0 ; i < 10 ; i ++ )
cout<<a[i]<<" ";
cout<<endl;
// 测试模板函数，传入浮点数数组
float b[4] = {4.4,3.3,2.2,1.1};
selectionSort(b,4);
for( int i = 0 ; i < 4 ; i ++ )
cout<<b[i]<<" ";
cout<<endl;
// 测试模板函数，传入字符串数组
string c[4] = {"D","C","B","A"};
selectionSort(c,4);
for( int i = 0 ; i < 4 ; i ++ )
cout<<c[i]<<" ";
cout<<endl;
return 0;
}
其输出结果为：
