空隙插入排序实现

Question

我试图在C++中实现一个空隙插入排序，称为库排序。我理解这个概念，但是我很难将其从常规的旧插入排序中解脱出来。我不知道我会如何解释阵列中的空白。我一直在使用整数0来指定一个差距。我到目前为止的代码如下，这是一个工作插入排序修改高频。你会如何去实施一个图书馆排序？我浏览了20页谷歌，并没有看到任何编程语言的实际代码示例。

#include <iostream> 
#include <stdlib.h> 
#include <time.h> 
#include <vector> 
using namespace std; 

vector<int> librarySort(int arr[20]) 
{ 
int j,tmp; 
vector<int> array; 
for (int i=0;i<20;i++) 
{ 
    array.push_back(0); 
    array.push_back(arr[i]); 
} 
for (int i=0;i<40;i++) { cout << array[i] << ",";} 
cout << endl; 
for (int i = 1; i < 40; i++) 
{ 
    j = i; 
    while (j > 0 && array[j - 1] > array[j]) 
    { 
     tmp = array[j]; 
     array[j] = array[j - 1]; 
     array[j - 1] = tmp; 
     j--; 
    } 
} 
for (int i=0;i<40;i++) { cout << array[i] << ",";} 
return array; 
} 
int main() 
{ 
srand(time(0)); 
int array[20]= {0}; 
for (int i=0;i<20;i++) 
{ 
    int n=rand()%19+1; 
    tmp=array[i]; 
    array[i]=array[n]; 
    array[n]=tmp; 
} 
for (int i=0;i<20;i++) { cout << array[i] << ",";} 
cout << endl; 
librarySort(array); 
} 

Answer 1

Here你有一个完整的描述和实施。差距被定义为你不会使用的任何价值。如果你正在使用指针，NULL是一个不错的选择。
在一般情况下，您必须创建一个具有原始数据的辅助数组。在这种情况下：

#define MAX 20 
#define MAX2 100//The size of the gapped array must be bigger 
#define EMPTY -1//Use this constant instead of zeros. 
bool isEmpty(int index, int gappedArray[MAX2]) { 
    return gappedArray[index]>=0; 
} 
vector<int> libSort(int arr[MAX]) { 
    int aux[MAX]; 
    for(int i=0;i<MAX;i++) aux = i; 
    //Add your library sort algorithm here 
    //However instead of comparing arr[i] with arr[j], compare arr[aux[i]] with arr[aux[j]] 
    //Then, when you are going to insert sorted values, insert aux[pos], not arr[pos] 
} 

这里有图书馆排序伪代码：

Rebalance(Array S, Integer iniLen, Integer finLen) 
k = finLen-1 
step = finLen/iniLen 
for j=iniLen-1 to 0: 
    S[k] = S[j] 
    S[j] = NONE 
    k = k-step 
end for 
LibrarySort(Array A, Integer n, Float epsilon, Array S) 
    goal = 1 
    pos = 0 
    sLen = (Integer)(1+epsilon)*n 
    while pos<n://For each round do this: 
     for i=1 to goal://Insert 'goal' elements to the sorted array S 
      //Search a position to insert A[pos] 
      insPos = binarySearch(A[pos], S, sLen) 
      if not IS_EMPTY(S[insPos]): 
       //Move elements to the right or the left in order to free 
       //insPos 
       freeSpace(insPos, S, sLen) 
      end if 
      S[insPos] = A[pos]//Insert new element 
      pos = pos + 1 
      if pos>n://All elements have been inserted 
       return LibrarySort 
      end if 
     end for 
     prevLen = sLen 
     sLen = min((2+2*epsilon)*goal, (1+epsilon)*n) 
     //Rebalance array S 
     Rebalance(S, prevLen, sLen) 
     goal = goal * 2 
    end while