[求助][讨论]插入排序的改进 - 编程论坛

#2

maoguoqing2007-07-21 13:05

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

#3

aipb20072007-07-21 13:59

回复：（maoguoqing）不仅2分搜索，那串已经排好的序列...

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

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

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

#4

一番宝瓶2007-07-21 15:50

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

#5

maoguoqing2007-07-21 17:33

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

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

#6

aipb20072007-07-23 18:28

又想了想，不能实现。

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

#7

HJin2007-07-24 04:02

回复：（aipb2007）又想了想，不能实现[em35]。看来插...

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;
    }
}