两种应该掌握的排序方法--------1.shell Sort

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

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

http://zh.wikipedia.org/zh/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95

http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.7.1.1.htm

希尔排序 O(n^1.25)

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

基数排序O(n)

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

而且希尔排序实现简单。

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

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

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

希尔排序的wiki中列出的表 http://en.wikipedia.org/wiki/Shellsort

最近的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 <string>
#include <vector>
#include <iostream>
#include <algorithm> //just for sort() and binary_search()

using namespace std;

//method 1  数组方式 ok
void 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 ok
void shellsort1_2(vector<int> &squeue_)
{
    vector<int>::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 ok
void shellsort1_3(vector<string> &squeue_)
{
    vector<string>::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<string> &gaps)
{
    size_t gap = 0;
    size_t j = 0;
    string temp("");
    size_t count = gaps.size();

    for (vector<string>::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 
", index++, *(int*)a, *(int*)b);

    for (int i = 0; i < 9; i++)
    {
        printf("%d ",list[i]);
    }
    printf("
");

    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<int> iVec(i_List, i_List + count);//数组的begin 到end赋值到这个vector中，函数原型是 vector<_Iter>(_Iter_First,_Iter_Last);
    

    //--------string 字符   ,关于中文，unicode，要指定编码格式，
    vector<string> 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<int>
    shellsort1_2(iVec);

    //method 3  vector<string>
    shellsort1_3(str_Vec);
    
    //method 4  vector<string>
    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;
}

模板的版本 =》来自基本排序算法之1——希尔排序shellsort

/*
 * 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<typename T>
void shellsort(T a[],int n1,int inc[],int n2)
{
    for(int i=0;i<n2;++i)
    {
        for(int j=inc[i];j<n1;++j)
        {
            T tmp = a[j];
            int k;
            for(k=j;k>=inc[i];k-=inc[i])
            {
                if(tmp<a[k-inc[i]])
                    a[k]=a[k-inc[i]];
                else
                    break;
            }
            a[k]=tmp;
        }
    }
}