先了解下什么都有什么排序算法 

https://en.wikipedia.org/wiki/Sorting_algorithm

 

 

 

O(n^1.25)  

排序 （Binary tree sort） — O(n log n)期望时间; O(n²)最坏时间; 需要 O(n) 額外空間

 O(n)

 

 

总结：若是数据量特别大的话，希尔排序会比快速排序慢点，但若是中小数据的比较，希尔排序更快速。

而且希尔排序实现简单。

 

有两种排序我们应该掌握：

一个是希尔排序（小量数据），

一个是二叉排序树排序（又称为二分查找法、快速排序）（大量数据）

 

希尔排序的wiki中列出的表   

最近的Marcin Ciura's gap sequence的伪代码如下：

Using Marcin Ciura's gap sequence, with an inner insertion sort.

# Sort an array a[0...n-1].gaps = [701, 301, 132, 57, 23, 10, 4, 1] foreach (gap in gaps){
         # Do an insertion sort for each gap size.    for (i = gap; i < n; i += 1)    {
             temp = a[i]        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)        {
                 a[j] = a[j - gap]        }        a[j] = temp    } }

http://sun.aei.polsl.pl/~mciura/publikacje/shellsort.pdf 他的文档中列出了从10~1亿 的数据量的时间复杂度，而且有实验数据和图表。

下面是自己写的代码shellsort1_1至1_3是增量为count/2，   shellsort2_1至2_2增量为1

 

 

 

#include "stdafx.h"#include 
     
      #include 
      
       #include 
       
        #include 
        
          //just for sort() and binary_search()using namespace std;//method 1  数组方式 okvoid shellsort1_1(int *data, size_t size){    for (int gap = size / 2; gap > 0; gap /= 2)        for (size_t i = gap; i < size; ++i)          {             int Temp = data[i];             int j = 0;             for( j = i -gap; j >= 0 && data[j] > Temp; j -=gap)             {                data[j+gap] = data[j];                  }               data[j+gap] = Temp;         }}//method 2 okvoid shellsort1_2(vector
         
           &squeue_){    vector
          
           ::size_type size = squeue_.size(); for (int gap = size / 2; gap > 0; gap /= 2) for (size_t i = gap; i < size; ++i) { int j = 0; int temp = squeue_[i]; // data[i]; for( j = i -gap; j >= 0 && squeue_[j] > temp; j -=gap) { squeue_[j+gap] = squeue_[j]; } squeue_[j+gap] = temp;//squeue_[i]; }}//method 3 okvoid shellsort1_3(vector
           
             &squeue_){ vector
            
             ::size_type size = squeue_.size(); for (int gap = size / 2; gap > 0; gap /= 2) for (size_t i = gap; i < size; ++i) { int j = 0; string temp = squeue_[i]; for( j = i -gap; j >= 0 && squeue_[j] > temp; j -=gap) { squeue_[j+gap] = squeue_[j]; } squeue_[j+gap] = temp;//squeue_[i]; }}//method 4 ok void shellsort2(vector
             
               &gaps){ size_t gap = 0; size_t j = 0; string temp(""); size_t count = gaps.size(); for (vector
              
               ::iterator it = gaps.begin(); it != gaps.end(); ++it, gap +=1)//for_each (gap in gaps) { // Do an insertion sort for each gap size. for (size_t i = gap ; i < count; i += 1) { temp = gaps[i]; for (j = i; j >= gap && gaps[j - gap] > temp; j -= gap) { gaps[j] = gaps[j - gap]; } gaps[j] = temp; } }} //c 库的sort int index = 1; int list[9] = { 5, 2, 3, 9, 4, 6, 7, 8, 1}; int callbackFunc_Compare(const void* a , const void *b) {     printf("index = %d,   a= %d, b = %d \n", index++, *(int*)a, *(int*)b);     for (int i = 0; i < 9; i++)     {         printf("%d ",list[i]);     }     printf("\n");     return *(int*)a - *(int*)b; } int _tmain(int argc, _TCHAR* argv[]){ //--------int int i_List[] ={ 13, 14 ,94, 33, 82, 25, 59, 2, 65, 23, 185, 1, 156, 34}; int count = sizeof(i_List)/4; //除以4，因为一个int占4字节，最好别用这种形式，获取个数，用vector吧！ vector
               
                 iVec(i_List, i_List + count);//数组的begin 到end赋值到这个vector中，函数原型是 vector<_Iter>(_Iter_First,_Iter_Last); //--------string 字符 ,关于中文，unicode，要指定编码格式， vector
                
                  str_Vec(0),str_Vec2(0); str_Vec.push_back("M1"); str_Vec.push_back("N1"); str_Vec.push_back("B1"); str_Vec.push_back("V1"); str_Vec.push_back("C1"); str_Vec.push_back("X1"); str_Vec.push_back("Z1"); str_Vec.push_back("A1"); str_Vec.push_back("A100"); str_Vec.push_back("A102"); str_Vec.push_back("A109"); str_Vec2 = str_Vec; //method 1 数组 shellsort1_1(i_List, count); //method 2 vector
                 
                   shellsort1_2(iVec); //method 3 vector
                  
                    shellsort1_3(str_Vec); //method 4 vector
                   
                     shellsort2(str_Vec);　　//利用sort(),最简单，因为是模版所以很简单-----另我们可以重载sort自己做compare（）方法！ std::sort(iVec.begin(), iVec.end()); std::sort(str_Vec2.begin(), str_Vec2.end()); 　　//c库利用回调 　　qsort(list, 9, sizeof(list[0]), callbackFunc_Compare );    //二分查找 std::binary_search(iVec.begin(), iVec.end(),34); //http://www.cplusplus.com/reference/algorithm/binary_search/ return 0;}
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

 

 

模板的版本  =》来自 

/* * a[] is an array to be sorted * n1 is the T array length * inc[] is the array to indecate the increasement * n2 is the inc array length */template
     
      void shellsort(T a[],int n1,int inc[],int n2){    for(int i=0;i
      
       =inc[i];k-=inc[i])            {                if(tmp