选择排序

 

 

选择排序算法：

void selectionSort(int 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] ); } }

 

自定义结构体：

#ifndef INC_02_SELECTION_SORT_USING_TEMPLATE_STUDENT_H #define INC_02_SELECTION_SORT_USING_TEMPLATE_STUDENT_H #include <iostream> #include <string> using namespace std; struct Student{ string name; int score; bool operator<(const Student& otherStudent){ return score != otherStudent.score ? score > otherStudent.score : name < otherStudent.name; } friend ostream& operator<<(ostream &os, const Student &student){ os<<"Student: "<<student.name<<" "<<student.score<<endl; return os; } }; #endif //INC_02_SELECTION_SORT_USING_TEMPLATE_STUDENT_H

 

 

使用模板函数：

#include <iostream> #include "Student.h" 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] = {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; // 测试模板函数，传入自定义结构体Student数组 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; return 0; }

 

SortTestHelper添加对算法效率的衡量： template<typename T> bool isSorted(T arr[], int n) {//是否被正确的排序 for (int i = 0; i < n - 1; i++) if (arr[i] > arr[i + 1]) return false; return true; } template<typename T> void testSort(const string &sortName, void (*sort)(T[], int), T arr[], int n) {//通过指定函数的名称、测试算法函数的地址、测试的数组、长度对数组进行时间的判断 clock_t startTime = clock(); sort(arr, n); clock_t endTime = clock(); assert(isSorted(arr, n)); cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl; return; }

 

测试：

int main() { int n = 10000; int *arr = SortTestHelper::generateRandomArray(n,0,n); SortTestHelper::testSort("Selection Sort", selectionSort, arr, n); delete[] arr; return 0; }

 

 

转载于:https://www.cnblogs.com/lzb0803/p/9043323.html