选择排序

本文主要回顾排序算法中的选择排序，主要有如下内容：
1.为什么要学习O( n^2 )的排序算法
2.一句白话说选择排序
3.选择排序的具体实现

---

为什么要学习O( n^2 )的排序算法

学习过算法的我们都知道，时间复杂度为O( n^2 )的算法多半不是最佳算法，那为什么我们也要学习并掌握这种类型的算法呢，其实这种类型算法一般都具有如下特点：

• 编码简单，易于实现，也就是我们很容易想到
• 此外可以在简单算法的基础上再做改进
• 特殊场景下，简单的排序算法更为有效
• 由简入难，从简单的排序算法思想再推演出复杂的排序算法

一句白话说选择排序

一句白话说选择排序：选择排序就是每次都从一堆元素中选出一个最小（大）的
详细一点就是：假设总共n个元素，第一趟从n个元素的数据序列中选出关键字最小/大的元素并放在最前/后位置，下一趟从n-1个元素中选出最小/大的元素并放在最前/后位置。以此类推，经过n-1趟完成排序。

选择排序的具体实现

• C语言实现

#include <stdio.h>


void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;

    return;
}

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

    return;
}

int main()
{
    int a[10] = {10,9,8,6,7,5,4,3,1,2};
    selectionSort(a, 10);
    for(int i = 0; i < 10; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

• C++实现

清单1：头文件

#ifndef SELECTIONSORT_STUDENT_H
#define SELECTIONSORT_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 // SELECTIONSORT_STUDENT_H

清单2：具体实现

#include <iostream>
#include <algorithm>
#include <string>
#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]);
     }

     return;
}


int main()
{
    int a[10] = {10,9,8,6,7,5,4,3,1,2};
    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 d[4] = {
    {"D",90}, 
    {"C", 100},
    {"Bob",95}, 
    {"A",95},
    };
    selectionSort(d, 4);
    for(int i = 0; i < 4; i++)
    {
        cout<<d[i];
    }
    cout<<endl;

    return 0;
}

上述C++代码中用了到运算符重载，简单回顾一下：
为什么要对运算符进行重载：
C++预定义中的运算符的操作对象只局限于基本的内置数据类型，但是对于我们自定义的类型（类）是没有办法操作的。但是大多时候我们需要对我们定义的类型进行类似的运算，这个时候就需要我们对这么运算符进行重新定义，赋予其新的功能，以满足自身的需求。
C++运算符重载的实质：
运算符重载的实质就是函数重载或函数多态。运算符重载是一种形式的C++多态。目的在于让人能够用同名的函数来完成不同的基本操作。要重载运算符，需要使用被称为运算符函数的特殊函数形式，运算符函数形式：operatorp（argument-list）//operator 后面的’p’为要重载的运算符符号。
即：

<返回类型说明符> operator <运算符符号>(<参数表>)  
{  
     <函数体>  
}  

可以看到使用了模板或者其他语言中的泛型后，这样的一个程序的通用性就非常强，前面的C语言实现只能针对一种类型的数据进行排序！

---

参考资料