“回顾数据结构” 之 选择排序

1. 函数selectionSort

#include <iostream> using namespace std; template <typename T> //模板 void selectionSort ( T arr[],int n ){ 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]); } } 

注：1. 使用模板，在主函数中可以使用任意类型的数组
2. 交换函数swap更方便

2. 主函数：

int main() { int a[10] = {10,9,8,7,5,4,3,2,1}; selectionSort( a , 10 ); for( int i = 0 ; i < 10 ; i++ )         cout << a[i] << endl; double b[10] = {10.1,9.5,8.0,7.3,5.0,4.0,3.3,2.4,1.1}; selectionSort( b , 10 ); for( int j = 0 ;j < 10 ; j++ )         cout << b[j] << endl; return 0; } 

3.头文件

new一个file,选择C++header

自带宏定义：
#ifndef STUDENT_H_INCLUDED
#define STUDENT_H_INCLUDED

定义struct结构体

为什么要运算符重载：如果不重载运算符，则操作对象只能是基本数据类型，不能是自定义类型；则重载之后，对象可以为自定义类型。
重载输入输出运算符用友元函数。

#ifndef STUDENT_H_INCLUDED #define STUDENT_H_INCLUDED #include <iostream> #include <string> using namespace std; struct Student{      string name; int score; bool operator<(const Student &otherStudent){ //对“<”定义，返回值为bool？？ return score !=otherStudent.score?score > otherStudent.score : name < otherStudent.name ; //将<定义为>，则分数高的排在前面 //判断分数是否不等，若相等，则name小的排在前面 } friend ostream& operator<<(ostream &os,const Student &student){          os<<"Student: "<<student.name<<" "<<student.score<<endl; return os; } }; #endif // STUDENT_H_INCLUDED 

主函数的测试：

    Student s[4] = {{"D",90},{"C",96},{"B",80},{"A",80}}; //遇到姓名相同的，打印时按照给值的顺序；改进：在运算符重载时判断姓名 selectionSort( s , 4 ); for( int j = 0 ;j < 4; j++ )     cout << s[j]; //不用和上面一样每输出一个值打印一个空格  //因为对Stuent类的运算符已重载 再添空格是对重载后的结构再添空格     cout << endl; 

打印结果：