C++11多线程希尔排序

        用惯了Qt的QThread，爱之恨之。Qt的“信号与槽“模型，当然比纯C++用起来更顺手，对象的跨线程通信也很自然。另一面，用QThread创建 一个线程却不如C便捷。要么需要继承QThread，而后重载run函数，在其中实现逻辑功能。要么需要继承QObject类，在该类中实现逻辑功能，而 后该类的对象调用moveToThread(QThread &thrd)，把该对象移动到新线程空间。C++11的thread却很方便。
        突然发现我大概要从Qt回归C++了。对C++的孤陋寡闻，大概是拜Qt所赐吧。它太强大了，以至于无需去了解其他东西。

        复习数据结构，发现希尔排序、快速排序先天为多线程而生。希尔排序很直观，每趟排序中各个子列放在各自的线程里执行，下一趟依赖上一趟的结果，随趟数增多 并发度减小。快排要灵活一些，数据集被不断的二分，可以使越来越多的线程参与排序。所以，希尔排序从N个线程递减至1个线程，快排从1个线程递增至N个线 程，N为处理器core总数。
        粗略用C++11的Thread类实现了一下希尔排序。快排，大概需要先实现个线程池，方便分发任务。

        Thread支持lambda函数，这可真是方便到家了。

1、简陋地做一个类把数组按线性映射成N个子列，书写上方便一些：

#ifndef SHELLARRAY_H
#define SHELLARRAY_H

#include <exception>
#include <string>
#include <sstream>
typedef std::string string;
#include <QDebug>

class ShellSortException:public std::exception{
    public :
        ShellSortException(string msg){m_sMsg = msg;}
        const char* what(){return m_sMsg.data();}
        ~ShellSortException(){}
    private:
        string m_sMsg;
};

void inline throwException(const string &errMsg){
    std::stringstream errstm;
    errstm << "err:" << errMsg << " @" << __FILE__ << ":"
           <<__LINE__;
    throw ShellSortException(errstm.str());
}

/*
 * ShellArray  ----  A rough but convenient  array class which is able to 
 *                          reflect a numerical array to several subset.
 * Note: this is an incomplete class which cann't be used in program, 
 * & maybe it will be consummated with thread-safe, copy, shadow copy ,etc later.
*/

template<class Type>
class ShellArray
{
public:
    explicit ShellArray():m_nUpIdx(0){
    }
    bool initialize(Type *data,int size,int idx=0,int period=1){
        if(nullptr == data || size < 0 || period < 0 || idx < 0){
            throwException("Invalid source data information!");
        }
        m_ptData = data;
        m_nOffset = idx;
        m_nPeriod = period;

        m_nUpIdx = size / period - 1;
        if(idx < size % period)
            m_nUpIdx += 1;
        m_nSize = m_nUpIdx + 1;
        return true;
    }
   Type &operator [](int n){
        if(n > m_nUpIdx)
            throw ShellSortException("err: index over upper limit!");
        return m_ptData[n * m_nPeriod + m_nOffset];
    }
   int size(){
       return (m_nUpIdx + 1);
   }
private:
    int m_nOffset;
    int m_nUpIdx;
    int m_nPeriod;
    int m_nSize;
    Type *m_ptData;
};
#endif // SHELLARRAY_H

2、希尔排序的多线程实现：

#ifndef SHELLSORT_H
#define SHELLSORT_H

#include <thread>
#include <vector>
typedef std::thread thread;
#include "shellarray.h"

#define CORE_CNT 4
#define MULTITHREAD_THRESHOLD 10

template<class Type>
class ShellSort final
{
public:
    explicit ShellSort(Type *data ,int size);
    int sort();
    static int insertSort(ShellArray<Type> &dArr,int n);
private:
    Type *m_ptData;
    int m_nSize;
    int m_nThreadsCnt;
};

template <class Type>
ShellSort<Type>::ShellSort(Type *data,int size){
    if(nullptr == data || size < 0){
        throw ShellSortException("err: ShellSort with a invalid data pointer or a invalid size!");
    }
    if(size < MULTITHREAD_THRESHOLD)
        m_nThreadsCnt = 1;
    else
        m_nThreadsCnt = CORE_CNT;
    m_nSize = size;
    m_ptData = data;
}

template <class Type>
 int ShellSort<Type>::sort(){
    /* There are so many data and more than one cores that we'd
     * better use multi-thread mode.
     */
     std::vector<std::thread*> tmpVector;
     int step = 1;
     while(m_nThreadsCnt > 1){
        for(int i = 0; i < m_nThreadsCnt; ++i){
            std::thread *tThread = new std::thread([=](){
                ShellArray<Type> tmpShArr;
                tmpShArr.initialize(this->m_ptData,
                                    this->m_nSize,
                                    i,
                                    this->m_nThreadsCnt);
                this->insertSort(tmpShArr,tmpShArr.size());
            });
            tmpVector.push_back(tThread);
        }
        for(auto &i : tmpVector){
            i->join();
            delete i;
        }
        tmpVector.clear();
        m_nThreadsCnt -= step;
        ++step;
    }
     ShellArray<Type> tArray;
     tArray.initialize(m_ptData,m_nSize);
     insertSort(tArray,tArray.size());
     return 0;
}

template<class Type>
int ShellSort<Type>::insertSort(ShellArray<Type> &dArr, int n){
    try{
    Type tmp;
    int j = 0;
    for(int i = 1; i < n; ++i ){
        tmp = dArr[i];
        j = i - 1;
        while(j >= 0 && tmp < dArr[j]){
            dArr[j+1] = dArr[j];
            --j;
        }
        dArr[j+1] = tmp;
    }
    }catch(std::exception &e){
        string _str = e.what();
        qDebug() << _str.data();
    }
    return 0;
}

#endif // SHELLSORT_H

3、测试：

#include <QDebug>
#include "shellsort.h"

int main(int argc, char *argv[])
{
    int arr[88888];
    for(int i = 0; i < 88888; ++i)
        arr[i] = 88888-i;
    ShellArray<int> sarr;
    sarr.initialize(&arr[0],88888);

    try{
    ShellSort<int> ss(&arr[0],88888);
     ss.sort();
     std::stringstream strstm;
    for(int i = 0; i < 88888; ++i)
        strstm << arr[i] << " ";
    qDebug() << strstm.str().data();
    }catch(ShellSortException &e){
        qDebug() << e.what();
    }

    return 0;
}