2排序基础

[xinrong2019]

目录

[TOC]

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

• 基础
• 编码简单，易于实现，是一些简单情景的首选
• 在一些特殊情况下，简单的排序算法更有效
• 简单的排序算法思想衍生出复杂的排序算法
• 作为子过程，改进更复杂的排序算法

选择排序

每次在当前数组里选择最小的数，与当前第一个位置上的数交换，下一次选择数前，将当前数组的开始位置向后移一位，直到当前位置为最后一位。

基本思路

假设从小到大排序，在下面的数组里找到第一个最小的元素。

经过一轮遍历，找到1是最小的，将1和目前数组的第一个位置上的数8交换位置。

第二轮遍历，找第一个位置后最小的元素，此时是2

将2与第二个位置上的数交换

此时前两个位置已经按顺序排好

下面在从第三个位置开始，再依次遍历，一直往后找最小的元素，找到3。

将3和第三个位置上的数交换位置。

再从剩下的元素中找最下的元素，是4，4和第4个位置上的数交换位置。

再从剩下的元素中找最下的元素，是5。

将5和第5个位置上的数交换位置。

接着，剩下的元素中6最小，和第6个位置上的数交换位置。

然后，7是剩下的最小的数了，不需要动(自己和自己交换)

最后8.

所有文件

main.cpp

#include <iostream>
#include "Student.h"
#include "SortTestHelper.h"
using namespace std;

/**
 * 选择排序算法实现
 * @tparam T
 * @param arr
 * @param n
 */
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);
    SortTestHelper::printArray(a, 10);

    float b[4] = {4.4,3.3,2.2,1.1};
    selectionSort(b,4);
    SortTestHelper::printArray(b, 4);

    string c[4] = {"D","C","B","A"};
    selectionSort(c,4);
    SortTestHelper::printArray(c, 4);

    Student d[4] = {{"D",90},{"C",100},{"B",95},{"A",95}};
    selectionSort(d, 4);
    SortTestHelper::printArray(d, 4);
    return 0;
}

Student.h

//
// Created by kim on 2020-02-02.
//

#ifndef SELECTSORT_STUDENT_H
#define SELECTSORT_STUDENT_H

#include <iostream>
#include <string>

using namespace std;

struct Student{
    string name;
    int score;

    /**
     * 重载操作符小于号
     * @param otherStudent
     * @return
     */
    bool operator<(const Student &otherStudent){
        return score != otherStudent.score ? score > otherStudent.score : name < otherStudent.name;
    }

    /**
     * 友元函数重载输出操作符<<  <br/>
     * operator<< is a friend function to ostream and class Student<br/>
     * so operator<< has access to all members of ostream and class Student<br/>
     * 参见<a href="https://docs.microsoft.com/en-us/cpp/cpp/friend-cpp?view=vs-2019#class-members-as-friends">Class members as friends</a>
     *
     * @param os
     * @param student
     * @return
     */
    friend ostream& operator<<(ostream &os, const Student &student){
        os<<"Student: "<<student.name<<" "<<student.score<<endl;
        return os;
    }
};
#endif //SELECTSORT_STUDENT_H

友元函数参见微软文档

SortTestHelper.h

//
// Created by kim on 2020-02-02.
//自动生成测试用例
//

#ifndef SELECTSORT_SORTTESTHELPER_H
#define SELECTSORT_SORTTESTHELPER_H

#include <iostream>
using namespace std;

namespace SortTestHelper{
    /**
     * 生成有n个元素的随机数组，每个元素的随机范围为[rangeL,rangeR]
     * @param n
     * @param rangeL
     * @param rangeR
     * @return
     */
    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;
    }

    template<typename T>
    void printArray(T arr[], int n){
        for (int i = 0; i < n; ++i) {
            cout<<arr[i]<<" ";
        }
        cout<<endl;
    }

    /**
     * 测试算法正确性
     * @tparam T
     * @param arr
     * @param n
     * @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;
    }

    /**
     * 测试性能
     * @tparam T
     * @param sortName 排序算法名称，用于打印
     * @param sort 函数指针
     * @param arr 测试数据
     * @param n 数据大小
     */
    template<typename T>
    void testSort(string sortName, void(*sort)(T[], int), T arr[],  int n){
        //void(*sort)表示返回值，是一个函数指针
        //(T[], int)表示参数类型
        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 //SELECTSORT_SORTTESTHELPER_H

主要实现(重要)

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]);
    }
}

在一个项目里添加多个C/C++可执行文件

另外我是用Clion写的实验代码，贴一下Cmake列表文件，在一个项目里添加多个C/C++可执行文件。

cmake_minimum_required(VERSION 3.14)
project(SelectSort)

set(CMAKE_CXX_STANDARD 14)

add_executable(SelectSort main.cpp Student.h SortTestHelper.h)
add_executable(SortTestHelperMain SortTestHelperMain.cpp)

add_executable命令的第一个参数是name，代表编译后的可执行文件的文件名。后面的参数是源文件，支持多个。

add_executable(<name> [WIN32] [MACOSX_BUNDLE]
               [EXCLUDE_FROM_ALL]
               [source1] [source2 ...])

插入排序

从第一个位置开始遍历，经过n轮遍历，步长是1.

每次遍历的时候，将当前位置的数插入到他前面的元素中合适的位置。

基本思路

假如对下面的数组进行从小到大排序。

对于第一个位置上的数，不动。

然后第二个位置上的数，6，将它插入到它前面的数中合适的位置，比较6和8，6<8，所以6和8交换位置

遍历到第三个位置，2

将2和它前面的数依次比较，最终确认在如下位置。

然后遍历到第四个位置，3，将3依次和前面的元素比较，最终在如下位置。

后面以此类推。

关键代码

template<typename T>
void insertionSort(T arr[], int n){
    for (int i = 0; i < n; ++i) {
        //寻找元素arr[i]合适的插入位置
//        for (int j = i; j > 0; j--) {
//            if(arr[j] < arr[j-1]){
//                swap(arr[j],arr[j-1]);
//            }else{
//                break;
//            }
//        }
        //第二层循环有提前终止的机会，有可能不需要从头到尾遍历。通常比插入排序快
        for (int j = i; j > 0 && arr[j] < arr[j-1]; j--) {
            swap(arr[j],arr[j-1]);
        }
    }
}

上面的插入排序算法还可以优化空间，

• 交换有三次赋值操作和两次根据下标访问数组元素的时间，写在for循环中就要执行很多次
• 对比选择排序的内层循环，选择排序的内存循环每次循环最多只有一个赋值操作和一个比较操作。

插入排序的改进

基本思路

遍历数组，将当前位置的数先临时保存为e，将当前位置的数，依次和前i位比较，每次比较时，如果当前位置的数e比前一位小，就把前一位数向后移一位，直到当前位置的数比前一位数大并且，停止遍历，且该位置为合适的位置，存放e。

依然对如下数组从小到大排序。

首先，对于第一个位置数8依然保持不变，

遍历到第二个位置时，先把6复制一份，然后考虑6适不适合在当前位置。就是和它前面的数依次比较

由于6比8小，所以当前位置应该是8，所以，先将8往后移一位。

再考虑6是不是应该放在前一个位置

由于此时在第0个位置，不需要再比较，那么6就在该位置。把6放在这个位置。

接着遍历到第三个位置，2，将2复制一份。

将2和其前面位置的8比较，2<8，将8往后移一位。

再比较2和6的大小，2<6，此时再把6往后移一位

此时再往前没有数要比较了，所以2就在当前第0个位置，直接将第0个位置赋值为2。

再遍历到第4个位置，复制一份3

然后，依次比较3和8，3<8，8向后移一位，再比较3和6，3<6，6向后移一位。再比较3和2，3>2，所以3就在第二个位置，将3复制给第二个位置。

后面以此类推。

关键代码(重要)

template<typename T>
void insertionSort(T arr[], int n){
  //i表示当前位置；++i表示从前向后，每次步长1；i<n说明进入循环到条件
    for (int i = 0; i < n; ++i) {
        //寻找元素arr[i]合适的插入位置
        T e = arr[i];
        int j; // j 保存元素e应该插入的位置
        for (j = i; j > 0 && arr[j-1] > e ; j--) {//最好的情况，数组近乎有序，前一个比当前的数值小，不需要循环
            arr[j] = arr[j-1];//如果当前位置上的数比前一位小，将前一位数后移一位
        }
        arr[j] = e;
    }
}

冒泡排序

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

    bool swapped;

    do{
        swapped = false;
        for( int i = 1 ; i < n ; i ++ )
            if( arr[i-1] > arr[i] ){
                swap( arr[i-1] , arr[i] );
                swapped = true;

            }

        // 优化, 每一趟Bubble Sort都将最大的元素放在了最后的位置
        // 所以下一次排序, 最后的元素可以不再考虑
        n --;

    }while(swapped);
}

希尔排序

排序思路

希尔排序利用了gap间隔，经过间隔上的数，用插入排序排序

取完第一个间隔后，再往后罗一位取第二个间隔上的数，进行插入排序。

假如有15个数，分4组，即间隔为4，完成上述过程，最后得到一个近乎有序的数组。

然后依次按照间隔为2排序，最后按间隔为1排序。

间隔为1时，就是普通插入排序。

为什么比插入排序快

因为在间隔大的时候，进行比较插入，移动的次数少。

在间隔小的时候，移动的距离也小。

特点

跳着排不稳定，效率比插入排序高。

由于不稳定，所以不重要。但是思路需要理解。

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

    // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
    int h = 1;
    while( h < n/3 )
        h = 3 * h + 1;

    while( h >= 1 ){

        // h-sort the array
        for( int i = h ; i < n ; i ++ ){

            // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
            T e = arr[i];
            int j;
            for( j = i ; j >= h && e < arr[j-h] ; j -= h )
                arr[j] = arr[j-h];
            arr[j] = e;
        }

        h /= 3;
    }
}

[xinrong2019]

接希尔排序，

间隔为二和间隔为一分别排序

图片来自马士兵说：希尔排序算法-整点儿稍微复杂的

分析：

第一行是按4为间隔排序，分别排 1，5，9，10 6，12，13，15 2，8，11，14 3，4，7

第三行开始的三行，按照2为间隔排序，分别排 1，2，5，8，9，11，10，14 6，3，12，4，13，7，15

最后两行是按间隔为1进行插入排序