C++模板插入排序

红太狼 2022-08-21 00:19 51阅读 0赞

研一春季选修的算法设计与分析，虽然本科也学过，除了自己掌握的熟练程度以外，毕竟算法也博大精深，借此机会好好脑补一下吧。算法都是基于**《算法导论》（第2版）**中的伪代码。。

# C++模板插入排序 #

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。  
**`插入排序的基本参数`**  
数据结构 数组  
最差时间复杂度 O(n2)  
最优时间复杂度 O(n)  
平均时间复杂度 O(n2)  
最差空间复杂度 总共O(n) ，需要辅助空间O(1)

以上内容摘自**维基百科**，我自己的理解是：

在插入排序中，数组中`array[0 ~ i-1]`的子序列是有序的，`key=array[i]`是即将要插入有序序列的数，`array[i+1 ~ len-1]`子序列则是剩下待插入的无序序列。  
插入排序就像是打扑克的过程，最开始手中没有牌，我们从无序的牌堆里面摸牌，每次摸一张都要插入到手中的牌组中时手中的牌组有序。

# 代码 #

我打算把几个经典排序算法都写到`MySort`名称空间，并用模板表示：

/*MySort.h*/
    #ifndef MYSORT_H_
    #define MYSORT_H_
    #include <iostream>
    namespace MySort{
        template<typename T>
        void InsertSort(T *arr, size_t n)
        {
            typedef typename T value_type;
            for (auto i = 1; i < n; i++)//抽牌过程(0~i-1表示手中牌有序)
            {
                value_type key = *(arr + i);//抽上来的牌
                auto j = i - 1;
                while (j >= 0 && key < *(arr + j))//开始从手中最大的那张牌开始比较
                {
                    *(arr + j + 1) = *(arr + j);
                    --j;
                }
                *(arr + j + 1) = key;//把扑克牌插入有序序列中
            }
        }//InsertSort
    }//namespace MySort
    #endif

测试程序：

/*main.cpp*/
    #include <iostream>
    #include "MySort.h"
    using namespace std;
    int main()
    {
        double b[] = { 5.6, 3.9, 4.1, 4.8};
        MySort::InsertSort<double>(b, sizeof(b) / sizeof(double));
        for (int i = 0; i < sizeof(b) / sizeof(double); i++)
        {
            cout << b[i] << " ";
        }
        cout << endl;
        system("PAUSE");
        return 0;
    }