Algorithm -- Selection Sort

川长思鸟来 2022-06-02 11:21 180阅读 0赞

Student.h

#ifndef SELECTIONSORT_STUDENT_H
    #define SELECTIONSORT_STUDENT_H
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    struct Student{
    
        string name;
        int score;
    
        // 重载小于运算法,定义Student之间的比较方式
        // 如果分数相等，则按照名字的字母序排序
        // 如果分数不等，则分数高的靠前
        bool operator<(const Student& otherStudent){
            return score != otherStudent.score ?
                   score > otherStudent.score : name < otherStudent.name;
        }
    
        // 重载<<符号, 定义Student实例的打印输出方式
        // * 很多同学看到这里的C++语法, 头就大了, 甚至还有同学表示要重新学习C++语言
        // * 对于这个课程, 大可不必。C++语言并不是这个课程的重点,
        // * 大家也完全可以使用自己的方式书写代码, 最终只要能够打印出结果就好了, 比如设置一个成员函数, 叫做show()...
        // * 推荐大家阅读我在问答区向大家分享的一个学习心得: 【学习心得分享】请大家抓大放小，不要纠结于C++语言的语法细节
        // * 链接: http://coding.imooc.com/learn/questiondetail/4100.html
        friend ostream& operator<<(ostream &os, const Student &student){
    
            os<<"Student: "<<student.name<<" "<<student.score<<endl;
            return os;
        }
    };
    
    #endif //SELECTIONSORT_STUDENT_H

SortTestHelper.h

#ifndef SELECTIONSORT_SORTTESTHELPER_H
    #define SELECTIONSORT_SORTTESTHELPER_H
    
    #include <iostream>
    #include <ctime>
    #include <cassert>
    
    using namespace std;
    
    
    namespace SortTestHelper {
    
        // 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
        int *generateRandomArray(int n, int rangeL, int rangeR) {
    
            assert(rangeL <= rangeR);
    
            int *arr = new int[n];
    
            srand(time(NULL));
            for (int i = 0; i < n; i++)
                arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
            return arr;
        }
    
        // 打印arr数组的所有内容
        template<typename T>
        void printArray(T arr[], int n) {
    
            for (int i = 0; i < n; i++)
                cout << arr[i] << " ";
            cout << endl;
    
            return;
        }
    
        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(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;
        }
    
    };
    #endif //SELECTIONSORT_SORTTESTHELPER_H

main.cpp

#include <iostream>
    #include <algorithm>
    #include "Student.h"
    #include "SortTestHelper.h"
    
    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]);
        }
    
    }
    
    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", "B", "C", "A"}; selectionSort(c, 4); for (int i = 0; i < 4; i++) cout << c[i] << " "; cout << endl; 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; int N = 10000; int *arr = SortTestHelper::generateRandomArray(N, 0, N); selectionSort(arr, N); SortTestHelper::printArray(arr,N);*/
    
        int N = 100000;
        int *arr = SortTestHelper::generateRandomArray(N, 0, N);
        SortTestHelper::testSort("Selection Sort", selectionSort, arr, N);
        delete[] arr;
    
        return 0;
    }