淺析直接插入排序與折半插入排序

2020-01-26 15:39:10

字體：大中小

來源：轉載

供稿：網友

首先看一下例子，將數據一個個的插入到一個列表中，插入后這個列表就排序好了

注意：這個列表是遞增的，而且內存空間已分配好，只是沒有填充真正的數據，如下代碼：

復制代碼代碼如下:

int InsertSort(MergeType *L, int data)
{
int j;

if (!L->len)
{
L->elem[++L->len] = data;
return 0;
}

for (j = L->len-1; j >= 0; --j)
{
  if (data < L->elem[j])
  {
   L->elem[j+1] = L->elem[j];/*數據后移*/
  }
  else
  {
   L->elem[j+1] = data;
   L->len++;
   break;
  }
}
return 0;
}

測試用例的代碼如下：

復制代碼代碼如下:

#define LISTLEN 10
MergeType pList;
MergeType pT;

pList.elem = (int*)malloc(sizeof(int)*LISTLEN);
ScanfList(&pList);
pList.len = LISTLEN;
pList.size = LISTLEN;

pT.elem = (int*)malloc(sizeof(int)*LISTLEN);
pT.len = 0;
pT.size = LISTLEN;
memset(pT.elem, 0, LISTLEN*sizeof(int));

for (int i = 0; i < LISTLEN; i++ )
{
InsertSort(&pT, pList.elem[i]);
}

PrintList(&pT);

free(pList.elem);
free(pT.elem);
pList.elem = NULL;
pT.elem = NULL;

其他函數以及代碼請定義請參考：冒泡算法的改進

直接插入排序

核心思想：是將一個記錄插入到已排序好的有序表中，從中得到一個新的、記錄數增1的有序表，也就是說遞增的次序排列每一個數據，將每一個數據插入到前面已經排序好的位置中。看下面的代碼

復制代碼代碼如下:

int InsertSort(MergeType* L)
{
int i, j = 0;
int nCompKey;

if (!L->elem || !L->len) return -1;

if (L->elem && (L->len==1)) return 0;

for ( i = 1; i < L->len; i++) /*遞增的順序排列*/
{
  if (L->elem[i] < L->elem[i-1]) /*第二個數據比第一個數據小*/
  {
   nCompKey = L->elem[i];
   L->elem[i] = L->elem[i-1];

   //move elements back
   for (j = i-2; j >= 0 && nCompKey < L->elem[j]; --j) /*在>=退出當前循環*/
   {
    L->elem[j+1] = L->elem[j];
   }
   L->elem[j+1] = nCompKey;
  }
}
return 0;
}

這里從第二個數據開始，比較當前的數據是否小于前面的一個數，如果小于前面一個數據，就將當前數據插入到前面的隊列中，在插入到前面數據中的過程，要移動數據

這里要注意時間的復雜度：

總的比較次數=1+2+……+(i+1-2+1)+……+(n-2+1)= n*(n-1)/2= O(n^2)

總的移動次數=2+3+……+(2+i-1)+ …… + n = (n+2)*(n-1)/2=O(n^2)

當然還要考慮空間復雜度：其實這里使用了一個變量的存儲空間作為移動數據的臨時空間

這里在移動的過程中，可以減少代碼理解的復雜度，但會在每一個數據比較的過程中增加一次比較的次數，如下代碼：

復制代碼代碼如下:

 ...
 if (L->elem[i] < L->elem[i-1])  /*第二個數據比第一個數據小*/
 {
  nCompKey = L->elem[i];
  /*move elements back, compare count add once*/
  for (j = i-1; j >= 0 && L->elem[j] > nCompKey; --j) /*從較大的數往較小的數的方向*/
  {
   L->elem[j+1] = L->elem[j];
  }/*在>=退出當前循環*/
  L->elem[j+1] = nCompKey; /*此時val[j]<nCompKey，說明當前插入的位置應該在j之后*/
 }
 ...

在插入數據的過程中，其實前面的數據都已經排序好了，這時候一個個的進行查找，必定查找次數較多，如果采用折半查找算法可以減少次數，如下

復制代碼代碼如下:

/*折半插入排序算法*/
int BInsertSort(MergeType *L)
{
int i, j;
int low, high, mid;
int nCompKey;

for (i = 1; i <= L->len - 1; i++ )
{
  nCompKey = L->elem[i];
  low = 0;
  high = i - 1;

  /*當low=high時，此時不能判斷插入的位置是在low=high的
   *前面還是后面，會進入下面的判斷*/
  while(low <= high)
  {
   mid = (low + high)/2;
   if ( nCompKey > L->elem[mid] )
   {
    low = mid + 1;/*當(low=mid+1)>high的時候，跳出循環*/
   }
   else
   {
    high = mid -1;/*當(high=mid-1)<low的時候，跳出循環*/
   }
  }/*low>high的時候，退出循環*/

  /*移動nCompKey之前的所有數據，這里使用high+1是因為high<low
   *的時候，按理數據應該放在high的位置，但是此時high的位置可
   *能已經有排列好的數據或者不存在的位置,所以移動為后一個位置*/
  for (j = i-1; j >= high+1; j-- ) /*high是否可以使用low代替？？*/
  {
   L->elem[j+1] = L->elem[j];
  }
  /*當沒有元素的時候 high=-1*/
  L->elem[high+1] = nCompKey;
}
return 0;
}

具體什么原因，請看上面的注釋，這里為什么用high+1，但是此時high與low的位置只相差一個位置，才會跳出while循環，請看下面的改進

復制代碼代碼如下:

#if 0
  for (j = i-1; j >= high+1; j-- ) /*high或許可以使用low代替*/
  {
   L->elem[j+1] = L->elem[j]; 
  }
  L->elem[high+1] = nCompKey;
#else
  for (j = i-1; j >= low; j-- ) /*使用low代替high+1*/
  {
   L->elem[j+1] = L->elem[j]; 
  }
  L->elem[low] = nCompKey;
#endif
...