0

您好，我被要求通过使用二进制搜索而不是线性来改进插入排序。问题是，由于数据比较，现在最好的情况是 O(n log n) 而不是 O(n)，这使得程序在某些情况下即使不慢也相等。这是我的二进制插入排序代码：

void InsertionSort(int data[], int size)
{
    int index = -1;
    for(int i = 1,temp,j;i<size;i++)
    {
        temp = data[i];//DM O(N)
        int high = i,low = 0,mid;//DM O(N)
        while(low <= high)//DC O(nlogn)
        {
            mid = (low + high) /2;
            if(temp < data[mid])
            {
                high = mid - 1;
                index = mid;
            }

            else if (temp > data[mid])
            {
                low = mid + 1;      
            }

            else if(data[mid] == temp)
            {
                index = mid;
                break; 
            } 

        }
        for(j = i;j > index;j--)
        {
            data[j] = data[j-1];//DC Worst Case O(n*n) but the exact is summation of n(n+1) / 2 nad best case o(1)
        }
        data[j] = temp;//DM O(n)
    }   
}
4

3 回答 3

0

您可以从偏向于最佳情况的阶段开始您的二分搜索。不是直接去(low+high)/2，而是从位置开始i-1，然后i-2，然后i-4，i-8， ... i-16，i-32直到找到更小的元素，或者直到i-whatever低于low。然后继续进行普通的二分查找。

请注意，这种优化是有代价的。最好的情况——排序或几乎排序的数据——需要 O(N) 时间，但相对于简单的二进制搜索版本，平均情况和最坏情况会慢一些。

void InsertionSort (int data[], int size)
{
    int i, j, high, low, mid, hop;
    int temp;

    for (i=1; i<size; i++)
    {
        temp = data[i];

        high = i;
        low = 0;
        hop = 1;

        do
        {
            mid = high - hop;
            hop <<= 1;

            if (temp < data[mid])
                high = mid;
            else
                low = mid + 1;
        }
        while (low+hop <= high);

        while (low != high)
        {
            mid = (low + high) / 2;

            if (temp < data[mid])
                high = mid;
            else
                low = mid + 1;
        }

        for(j=i; j>low; j--)
            data[j] = data[j-1];

        data[j] = temp;
    }   
}

另请注意，high是分配的mid，而不是mid+1。where 的情况与 wheretemp==data[mid]的情况完全相同temp>data[mid]。这是为了保持插入排序的良好性质：它是一种稳定的排序。不过，对普通整数进行排序没有区别。

于 2013-03-04T21:23:48.137 回答
0

这是我的二进制插入排序与普通插入排序的比较。我的基准时间是决定性的。二进制版本更快。

#include <iostream>

#define NB_VALUE 1000
#define VALUE_RANGE 200

class Profiler
{
    
    std::chrono::time_point<std::chrono::high_resolution_clock> initTime;
    const char *m_name;
    public:
    Profiler(const char *name = nullptr): initTime(std::chrono::high_resolution_clock::now()), m_name(name){}
    ~Profiler()
    {
        if(m_name)
             std::cout << m_name << " ";
        auto begin = std::chrono::time_point_cast<std::chrono::microseconds>(initTime).time_since_epoch();
        auto now = std::chrono::time_point_cast<std::chrono::microseconds>(std::chrono::high_resolution_clock::now()).time_since_epoch();
        
        auto duration = now - begin;
        double millisecond = duration.count() * 0.001;
        std::cout << millisecond << " ms\n";
    }
};

template <class T>
void swap(T &t1, T &t2)
{
    T tmp = t1;
    t1 = t2;
    t2 = tmp;
}

template<class T>
int binaryFindIndexOfSmallestBiggerOrEqual(T array[], unsigned int begin, unsigned int end, T value)
{
      int delta = end - begin;
      if(delta < 0)
           return -1;
    
    if(delta == 0)
    {
          if(array[end] > value)
                return end;
             else
                return -1;
    }
    
    int midIndex = begin + delta / 2;
    
    if(  array[midIndex] < value )
    {
           return binaryFindIndexOfSmallestBiggerOrEqual(array, midIndex+1, end, value);
    }
    else
    {
        if(midIndex == 0 || array[midIndex -1] <= value)
            return midIndex;
        else
            return binaryFindIndexOfSmallestBiggerOrEqual(array, begin, midIndex - 1, value);
    }   
}

template <class T>
void binaryInsertionSort(T array[], unsigned int begin, unsigned int end)
{
    if(end <= begin)
        return;
        
    int sortedUpTo = begin;
    int insertionIndex;
    while(sortedUpTo < end)
    {
        if(array[sortedUpTo] < array[sortedUpTo + 1])
            insertionIndex = -1; 
        else
             insertionIndex = binaryFindIndexOfSmallestBiggerOrEqual(array, begin, sortedUpTo, array[sortedUpTo + 1]);

        if(insertionIndex != -1)
        {
            T tmp = array[sortedUpTo + 1];
            memmove(array + (insertionIndex + 1), array + (insertionIndex), sizeof(T)*(sortedUpTo - insertionIndex + 1));
            array[insertionIndex] = tmp;
        }
        ++sortedUpTo;
    }
}   

template <class T>
void insertionSort(T array[], unsigned int begin, unsigned int end)
{
    for (int i = begin + 1; i <= end; ++i)
    {
        for (int j = i; j > begin + 1; --j)
        {
            if (array[j - 1] > array[j])
                swap(array[j - 1], array[j]);
            else
                break;
        }
    }
}

int main(int argc, char **argv)
{
     int arrayToSort[NB_VALUE];
    
//******** RANDOM CASE *********
    for (int i = 0; i < NB_VALUE; ++i)
      arrayToSort[i] = rand() % (VALUE_RANGE + 1) * 2 - VALUE_RANGE;
    
    Profiler *p = new Profiler();
    binaryInsertionSort(arrayToSort, 0, NB_VALUE - 1);
    delete p;
    //Timer : 0.119ms
    
    for (int i = 0; i < NB_VALUE; ++i)
    arrayToSort[i] = rand() % (VALUE_RANGE + 1) * 2 - VALUE_RANGE;
    
    p = new Profiler();
    insertionSort(arrayToSort, 0, NB_VALUE - 1);
    delete p;
    //Timer : 1 989ms
    
//********* ALREADY SORTED CASE ************
   for (int i = 0; i < NB_VALUE; ++i)
    arrayToSort[i] = i;
    
    p = new Profiler();
    binaryInsertionSort(arrayToSort, 0, NB_VALUE - 1);
    delete p;
    //Timer : 0.003ms
  
    for (int i = 0; i < NB_VALUE; ++i)
    arrayToSort[i] = i;
    
    p = new Profiler();
    insertionSort(arrayToSort, 0, NB_VALUE - 1);
    delete p;
    //Timer : 0.004ms
    
//********* REVERSED ORDER CASE ************
   for (int i = 0; i < NB_VALUE; ++i)
    arrayToSort[i] = NB_VALUE - 1;
    
    p = new Profiler();
    binaryInsertionSort(arrayToSort, 0, NB_VALUE - 1);
    delete p;
    //Timer : 0.046ms
  
    for (int i = 0; i < NB_VALUE; ++i)
    arrayToSort[i] = NB_VALUE - i;
    
    p = new Profiler();
    insertionSort(arrayToSort, 0, NB_VALUE - 1);
    delete p;
    //Timer : 3 878ms
    
    return 1;
}
于 2021-02-14T04:35:11.523 回答
-1

您还可以替换最后一个 else :else if(data[mid] == temp)用 simple else ，因为如果前两个不正确，很明显这是正确的......

于 2013-03-03T14:50:02.030 回答