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

更新時(shí)間：2013年12月25日 16:54:35 作者：

這篇文章主要介紹了直接插入排序與折半插入排序，有需要的朋友可以參考一下

首先看一下例子，將數(shù)據(jù)一個(gè)個(gè)的插入到一個(gè)列表中，插入后這個(gè)列表就排序好了

注意：這個(gè)列表是遞增的，而且內(nèi)存空間已分配好，只是沒(méi)有填充真正的數(shù)據(jù)，如下代碼：

復(fù)制代碼代碼如下:

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];/*數(shù)據(jù)后移*/
  }
  else
  {
   L->elem[j+1] = data;
   L->len++;
   break;
  }
}
return 0;
}

測(cè)試用例的代碼如下：

復(fù)制代碼代碼如下:

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

其他函數(shù)以及代碼請(qǐng)定義請(qǐng)參考：冒泡算法的改進(jìn)

直接插入排序

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

復(fù)制代碼代碼如下:

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]) /*第二個(gè)數(shù)據(jù)比第一個(gè)數(shù)據(jù)小*/
  {
   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) /*在>=退出當(dāng)前循環(huán)*/
   {
    L->elem[j+1] = L->elem[j];
   }
   L->elem[j+1] = nCompKey;
  }
}
return 0;
}

這里從第二個(gè)數(shù)據(jù)開(kāi)始，比較當(dāng)前的數(shù)據(jù)是否小于前面的一個(gè)數(shù)，如果小于前面一個(gè)數(shù)據(jù)，就將當(dāng)前數(shù)據(jù)插入到前面的隊(duì)列中，在插入到前面數(shù)據(jù)中的過(guò)程，要移動(dòng)數(shù)據(jù)

這里要注意時(shí)間的復(fù)雜度：

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

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

當(dāng)然還要考慮空間復(fù)雜度：其實(shí)這里使用了一個(gè)變量的存儲(chǔ)空間作為移動(dòng)數(shù)據(jù)的臨時(shí)空間

這里在移動(dòng)的過(guò)程中，可以減少代碼理解的復(fù)雜度，但會(huì)在每一個(gè)數(shù)據(jù)比較的過(guò)程中增加一次比較的次數(shù)，如下代碼：

復(fù)制代碼代碼如下:

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

在插入數(shù)據(jù)的過(guò)程中，其實(shí)前面的數(shù)據(jù)都已經(jīng)排序好了，這時(shí)候一個(gè)個(gè)的進(jìn)行查找，必定查找次數(shù)較多，如果采用折半查找算法可以減少次數(shù)，如下

復(fù)制代碼代碼如下:

/*折半插入排序算法*/
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;

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

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

具體什么原因，請(qǐng)看上面的注釋?zhuān)@里為什么用high+1，但是此時(shí)high與low的位置只相差一個(gè)位置，才會(huì)跳出while循環(huán)，請(qǐng)看下面的改進(jìn)

復(fù)制代碼代碼如下:

#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
...