1、希尔排序:插入排序的改进版，希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

void HighSort::shellSort(vector<int> & data) {

   if(data.size()<=1)

       return;

   for (int div=data.size()/2; div>=1; div/=2) {

       for (int i=div; i<data.size(); ++i) {

           for (int j=i; (data[j]<data[j-div])&&j>=0; j-=div) {

               swap(data[j],data[j-div]);

           }

       }

   }

}

希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n2)，而Hibbard增量的希尔排序的时间复杂度为O(

  

2、桶排序：工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。

void bucketSort(vector<int> &data) {

   if (data.size() <= 1)

       return;

   int digits = numofDigits(data);

   vector<vector<int> > b(10,vector<int>(data.size()+1,0));

   for (int i=1; i<=digits; ++i) {

       distributeElement(data,b,i);

       collectElement(data,b);

       for (int ii=0; ii<b.size(); ++ii) {

           for (int jj=0; jj<b[ii].size(); ++jj)

               b[ii][jj]=0;

       }

   }

}

int numofDigits(vector<int> & data) {

    int largest = data[0];

    for (int i=1; i<data.size(); ++i) {

        if (data[i] > largest)

            largest = data[i];

    }

    int digits = 0;

    while (largest) {

        digits++;

        largest /= 10;

    }

    return digits;

}

void distributeElement(vector<int> &data, vector<vector<int> > &b, int digits) {

   int divisor = 10;

   for (int i=1; i<digits; ++i) {

       divisor *= 10;

   }

   for (int i=0; i<data.size(); ++i) {

       int numOfDigist = (data[i]%divisor - data[i]%(divisor/10)) / (divisor/10);

       int num = ++ b[numOfDigist][0];

       b[numOfDigist][num] = data[i];

   }

}

void collectElement(vector<int> &data, vector<vector<int> > &b) {

    int k=0;

    for (int i=0; i<10; ++i) {

        for (int j=1; j<=b[i][0]; ++j) {

            data[k++] = b[i][j];

        }

    }

}

这个桶排序就是先按个位排序，然后按十位，不断往上，就是选了好几轮桶，每一轮的桶都是某一位上的数字是0，1，...9.
这种桶的选择其实就是基数排序。

3、基数排序

见桶排序。