SelectionSort选择排序思想及实现（泛型）
2-1 选择排序Selection Sort（笔记）
【思想】：每次从未排序部分找出最小的，与当前未排序部分的第一个位置上的元素互换。重复以上步骤，直至排序完毕。
【例子】：(原序列) 3 1 5 2 8
(第一次)13 5 2 8
(第二次)1 2 5 3 8
(第三次)1 2 3 5 8
【代码1】：// SelectionSort.cpp: 定义控制台应用程序的入口点。
//
#include"stdafx.h"
#include<iostream>
#include<algorithm>
//using std::cin;
//using std::cout;
//using std::endl;
usingnamespace std;
voidselectionSort(intarr[],intn) {
for (int i = 0; i <n; i++) {
//寻找(i, n)区间中的最小值及其所在位置
int minIndex = i;//每次默认未排序部分的第一个为最小值
for (int j = i + 1; j <n; j++)
if (arr[j] <arr[minIndex])
minIndex= j;
//交换
swap(arr[i],arr[minIndex]);//老版中swap函数在algorithm库
}
}
int main()
{
int a[10] = { 10, 9, 8,7, 6, 5, 4, 3, 2, 1 };
selectionSort(a,10);
for (int i = 0; i < 10;i++)
cout<< a[i]<<" ";
cout<< endl;
return 0;
}
【问题及解决方式】：上篇博客中说到了用using std::cin;等替换using namespace std; 但在本次的实现中发现，替换后vs2017会出现“未找到swap”的问题，而用using namespace std;程序可正常运行，原因不详。故在未找到原因前，暂时继续使用using namespace std。
【改进1】：对不同类型的对象进行排序 —— 泛型（模板函数）
// SelectionSort.cpp: 定义控制台应用程序的入口点。
//
#include"stdafx.h"
#include<iostream>
#include<algorithm>
#include<string>
usingnamespace std;
//泛型
template<typenameT>
voidselectionSort(Tarr[],intn) {
for (int i = 0; i <n; i++) {
//寻找(i, n)区间中的最小值及其所在位置
int minIndex = i;//每次默认未排序部分的第一个为最小值
for (int j = i + 1; j <n; j++)
if (arr[j] <arr[minIndex])
minIndex= j;
//交换
swap(arr[i],arr[minIndex]);//老版中swap函数在algorithm库
}
}
int main()
{
//整型
int a[10] = { 10, 9, 8,7, 6, 5, 4, 3, 2, 1 };
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;
}
下面对自己定义的类型进行排序：
首先，新建一个.h头文件：
#pragmaonce
//宏定义 解决可能出现的.h头文件的多重引用问题
#ifndefSELECTIONSORT_STUDENT_H
#defineSELECTIONSORT_STUDENT_H
#include<iostream>
#include<string>
usingnamespace std://应尽量避免，容易出现命名空间的污染问题
struct Student {
stringname;
int score;
//为排序，重载“<”
booloperator<(const Student&otherStudent) {
return score <otherStudent.score;
}
//为输出，重载“<<”
friend ostream&operator<<(ostream&os,const Student&student) {
os<< "Student:" << student.name <<"" << student.score << endl;
return os;
}
};
#endif// !SELECTIONSORT_STUDENT_H
测试代码：
//自定义
Student d[4] = { {"D", 90}, {"C", 100}, {"B", 95}, {"A", 95} };
selectionSort(d,4);
for (int i = 0; i < 4;i++)
cout<< d[i] ;
cout<< endl;
【运行结果截图】：