有没有可能利用2分搜索，取代常规插入排序中的线性查找插入。
这样的话，可以把时间代价由 O（n^2） 改进至 O（nlgn）。

大家说说看法！

不仅2分搜索，那串已经排好的序列，你想几分搜索都可以。。

莫非还可以三分搜索？这样有价值吗？

虽然可以，但是有个问题，插入要移位，所以还是要花费O(n)的时间代价。
这样一来，2分搜索不就没意义了？

不知道我表达清楚没有。！！！

希尔排序不就已经分组了嘛 ...分几组已经等价于几分法了吧, 不过时间复杂度好像是 O((log₂n)²)

顺序搜索和二分搜索都要移位啊，移位需要消耗的资源是相同的，那对于有序的数列，自然首选二分查找。

ps: 分治策略中当然最好用的还是二分法，多分肯定没什么意思撒。

又想了想，不能实现。

看来插入排序只能O(n^2)了。

following is what i used to answer a poster's question in algorithms forum.

It will not compile for you, since you don't have my namespace file. But you may be able to extract some useful info from it.

#include <iostream>
#include \"hjns.h\"
#include <vector>
using namespace std;


/**
This implementation has O(n^2) comparsions and moves.
Sample output:
-100 68 -82 76 -87 -77 93 -30 96 8 15 -94 0 100 -83 100 98 98 26 0
-100 -94 -87 -83 -82 -77 -30 0 0 8 15 26 68 76 93 96 98 98 100 100
number of comparisons is 87
number of moves is 63
Press any key to continue . . .

There exists O(n lg^2 n) shellsort algorithm.
See Pratt, V (1979). Shellsort and sorting networks
(Outstanding dissertations in the computer sciences).
Garland. ISBN 0-824-04406-1.  (This was originally presented
as the author's Ph.D. thesis, Stanford University, 1971) 
*/
void shellsort(int* a, int size, int& numComparisons, int& numMoves);
void shellsort(int* a, int size);
int main(int argc, char** argv)
{
    //const int kSize = 19;
    //int a[kSize];
    //int numComparisons;
    //int numMoves;

    //hj::number::randoma(a, kSize);
    //hj::print(a, DIM(a));

    //vector<int> vi(a, a+kSize);
    //sort(vi.begin(), vi.end());
    //hj::print(vi);
    //shellsort(a, DIM(a), numComparisons, numMoves);
    //hj::print(a, DIM(a));
    //cout<<\"number of comparisons is \"<<numComparisons<<endl;
    //cout<<\"number of moves is \"<<numMoves<<endl;
    bool res;
    for(int i=0; i<1000; ++i)
    {
        res = hj::algorithm::checkSorting(i, shellsort, false);
        if(res)
            ;
        else
        {
            cout<<\"i=\"<<i<<\", error\n\";
        }
    }
    return 0;
}
void shellsort(int* a, int size, int& numComparisons, int& numMoves)
{
    int i;
    int j;
    int key;
    int increment = (int) (size / 2.0);
    numComparisons = 0;
    numMoves = 0;
    while (increment>0)
    {
        for (i=increment; i < size; i+=increment)
        {
            j = i;
            key = a[j];
            // search the insertion point
            while ( j >= increment && a[j-increment] > key )
            {
                a[j] = a[j - increment];                
                j  -= increment;
                ++numMoves; // we moved items
                ++numComparisons; // we compared items
            }
            a[j] = key; // insert it
            // adjust number of comparsions. This is the case
            // in which j >= increment but a[j-increment] <= key.
            // In this case, we compare once (and only once) and
            // exit the while loop above.
            if(j>=increment)
                ++numComparisons;
        }

        increment = (int) (increment /2.5 );
        // this is not necessary, but will save one loop
        if (increment == 2) 
            increment = 1;
    }
}

void shellsort(int* a, int size)
{
    int i;
    int j;
    int key;
    int increment = size/2;
    while (increment>0)
    {
        for (i=increment; i < size; i+=increment)
        {
            j = i;
            key = a[j];
            // search the insertion point
            while ( j >= increment && a[j-increment] > key )
            {
                a[j] = a[j - increment];                
                j  -= increment;
            }
            a[j] = key; // insert it
        }
        increment /= 2;
        // this is not necessary, but will save one loop
        if (increment == 2) 
            increment = 1;
    }
}