选择排序法

image

#include<iostream>

using namespace std;

void selectionSort(int arr[], int n){
    //i从0开始，寻找[i,n]区间里的最小值的下标，与当前下标为i的值交换
    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;
    return 0;
}

1 2 3 4 5 6 7 8 9 10

为了使接受的类型更为广泛，可以使用template的方法，如下：

template<typename T>
void selectionSort(T arr[], int n)

同时测试如下输入：

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;

1.1 2.2 3.3 4.4
A B C D

当接受的是对象时，可以自定义排序类型，如下设计一个Student类，根据分数来排序：
首先写一个Student类的头文件Student.h:

#include<iostream>
#include<string>

using namespace std;

struct Student{

    string name;
    int score;
    //运算符重载返回布尔值
    bool operator<(const Student &otherStudent){
    //根据分数升序排列
        return score < otherStudent.score;
    }

    friend ostream& operator<<(ostream &os, const Student &student){

        os << "Student:" << student.name << "" << student.score << endl;
        return os;
    }
};

在主函数内接受实例，结果如下：

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;

Student:D 90
Student:B 95
Student:A 95
Student:C 100

进一步修改Student类的内容，当分数相同的时候，按照姓名的字符顺序排列：

bool operator<(const Student &otherStudent){

        return score != otherStudent.score ? score > otherStudent.score:name<otherStudent.name;

    }

此时的结果如下：

Student:C 100
Student:A 95
Student:B 95
Student:D 90

上面程序的局限性在于接受的数组是死的，数量和内容都有一定的限制，下面再创建一个生成随机的数组文件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);
        //使用new方法创建一个新的数组
        int *arr = new int[n];
        //随机种子进行设置，这里使用时间
        srand(time(NULL));
        for (int i = 0; i < n; i++)
            //生成指定范围的随机数
            arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
        return arr;
    }
    //打印函数
    template<typename T>
    void printArray(T arr[], int n){
        for (int i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << endl;

        return;
}   

主函数部分改成如下：

int main(){

    int n = 10000;
    int *arr = SortTestHelper::generateRandomArray(n, 0, n);
    selectionSort(arr, n);
    SortTestHelper::printArray(arr, n);
    //因为在SortTestHelper中使用了new方法创建了arr,在这里为了防止内存泄漏的问题，释放一下，当然不释放也不会报错
    delete[] arr;
}

输出的结果是10000个数进行升序排列。

下面进行测试算法的效率问题，最常用的方法便是测试算法运行所需要的时间长短，在SortHelper函数中添加测试时间的函数和测试是否排序成功的函数，如下：

    //测试排序是否成功
    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放在这个位置的原因有：一是测试的运行时间不能包括判断是否成功排序的时间，二是若没有成功排序，在打印之前程序自动中断
        assert(isSorted(arr, n));
        //CLOCKS_PER_SEC是在标准库中定义的一个宏，表示每秒钟运行的时钟周期的个数
        //上述clock函数返回的是运行的时钟周期，这样看来这样的算法则表示运行的时间，单位为秒
        cout << sortName << ":" << double(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;

        return;
    } 

主函数中相应部分变更：

/*selectionSort(arr, n);
SortTestHelper::printArray(arr, n);*/
SortTestHelper::testSort("Selection Sort", selectionSort, arr, n);

经过测试，当数组的元素数为一万的时候，运行的时间为0.201s；而当数组的元素数为16.067s。

分析来看，当数组元素数增长10倍的时候，运行的时间差不多增长100倍，也反映了该算法的时间复杂度是呈n的平方。

插入排序法

image

在主函数中定义插入排序的核心函数，如下：

template<typename T>
void insertionSort(T arr[], int n){
    for (int i = 1; i < n; i++){

        for (int j = i; j > 0; j--){
            if (arr[j] < arr[j - 1])
                swap(arr[j], arr[j - 1]);
            else
                break;
        }
    }
}

当然也可以对代码进行一定程度的简化：

template<typename T>
void insertionSort(T arr[], int n){
    for (int i = 1; i < n; i++){
        for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--){
                swap(arr[j], arr[j - 1]);
        }
    }
}

由此可以看出，插入排序的第二层循环当满足一定条件的时候是可以提前结束的，所以这也体现了插入排序比选择排序的优越性。

由于需要比较两种排序方法的优越性，而给定一个数组，排序的算法都是在原有的基础上进行覆盖排序，所以需要在测试帮助的头文件里定义一个数组复制的函数便于对该数组进行第二种排序方法的应用：

int* copyIntArry(int a[], int n){
        int* arr = new int[n];
        copy(a, a + n, arr);
        return arr;
}

同时主函数变更：

int main(){
    int n = 10000;
    int *arr = SortTestHelper::generateRandomArray(n, 0, n);
    int *arr2 = SortTestHelper::copyIntArry(arr, n);

    SortTestHelper::testSort("Insertion Sort", insertionSort, arr, n);
    SortTestHelper::testSort("Selection Sort", selectionSort, arr2, n);


    delete[] arr;
    delete[] arr2;
    return 0;
}

Insertion Sort:0.323s
Selection Sort:0.198s

这里的结果似乎违背了理论分析，但实际上程序中的swap交换操作本质上包含了三个基本的赋值操作，而插入算法的交换次数明显要比选择算法的交换次数要多，因此运行时间更长是可以理解的。
插入算法优化的过程如下，简述：从第二个数开始，首先复制一个相同的数，从当前位置的上一个位置开始，比较大小，若大的则将大者赋值给当前位置，继续向前比较，直到比自己小的数，将复制的数赋给当前位置。动图：

image

template<typename T>
void insertionSort(T arr[], int n){
    for (int i = 1; i < n; i++){
        T e = arr[i];
        int j;
        for (j = i; j>0 && arr[i - 1] > e; j--){
            arr[j] = arr[j - 1];
        }
        arr[j] = e;
    }
}

当将随机数组的范围就设置在0-3范围，即

int *arr = SortTestHelper::generateRnadomArray(n,0,3);

由于重复的数很多，所以最终插入排序的赋值次数将大大减少，经过运行一万个随机数进行排序的结果是

Insertion Sort:0.111s
Selection Sort:0.197s

之所以说插入排序在实际中应用更为广泛的原因就在于实际中的数据一般都是由一定的顺序性的，只是个别的元素处于乱序状态，例如系统自动生成的日志等，所以为此设计一个近似于正序的数列进行排列，来检验插入排序的复杂度：
在SortTestHelper.h中添加一个生成近似正序的数列以便于排序：

int *generateNearlyOrderedArray(int n, int swapTimes){
        int *arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = i;

        srand(time(NULL));
        for (int i = 0; i < swapTimes; i++){
            int posx = rand() % n;
            int posy = rand() % n;
            swap(arr[posx], arr[posy]);
        }

        return arr;
    }

相应地在主函数中更改：

int *arr = SortTestHelper::generateNearlyOrderedArray(n, 100);

经过运行后，结果的差异更为明显：

Insertion Sort:0.0003s
Selection Sort:0.195s