空隙插入排序實現

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