// 直接插入排序
void straight_insert_sort(int num[], int len){
 int i,j,key;
 for(j=1;j<len;j++){
  key=num[j];
  i=j-1;
  while(i>=0&&num[i]>key){
   num[i+1]=num[i];
   i--;
  }
  num[i+1]=key;
 }
}

3 性能分析：

3.1 空間復(fù)雜度：如上代碼，使用了一個輔助單元key，空間復(fù)雜度為O(1)

3.2 時間復(fù)雜度：

3.2.1 最好情況：待排序記錄已經(jīng)是有序的，則一趟排序，關(guān)鍵字比較1次，記錄移動2次。則整個過程

比較次數(shù)為

201642392631559.gif (92×62)

記錄移動次數(shù)為

201642392724089.gif (99×62)

時間復(fù)雜度O(n)

3.2.2 最壞情況：待排序記錄已經(jīng)是逆序的，則一趟排序，關(guān)鍵字比較次數(shù)i次（從i-1到0），記錄移動（i+2）次。整個過程

比較次數(shù)為

201642392744849.gif (95×62)

記錄移動次數(shù)為

201642392801121.gif (165×62)

時間復(fù)雜度O(n^2)

3.2.3 平均時間復(fù)雜度：O(n^2)

3.3 穩(wěn)定性：穩(wěn)定

折半插入排序
1 排序思想：

直接排序的基礎(chǔ)上，將待排序的記錄Ri插入到已經(jīng)排好序的記錄R1，R2，……，R（N-1）中，由于記錄R1，R2，……，R（N-1）已經(jīng)排好序，所以在查找插入位置時可采用“折半查找”。

2 算法實(shí)現(xiàn)：

// 折半插入排序
void binary_insert_sort(int num[], int len){
 int i,j,key,low,high,mid;
 for(i=1;i<len;i++){
  key=num[i];
  low=0;
  high=i-1;
  mid=(low+high)/2;
  // 尋找插入點(diǎn)，最終插入點(diǎn)在low
  while(low<=high){
   if(key<num[mid])
    high=mid-1;
   else 
    low=mid+1;
   mid=(low+high)/2;
  }
  // 移動記錄
  for(j=i;j>low;j--){
   num[j]=num[j-1];
  }
  // 插入記錄
  num[low]=key;
 }
}

3 性能分析：

3.1 空間復(fù)雜度：如上代碼，使用了一個輔助單元key，空間復(fù)雜度為O(1)

3.2 時間復(fù)雜度：雖然折半查找減少了記錄比較次數(shù)，但沒有減少移動次數(shù)，因此時間復(fù)雜度同直接查找算法。

3.2.1 最好情況：時間復(fù)雜度O(n)

3.2.2 最壞情況：時間復(fù)雜度O(n^2)

3.2.3 平均時間復(fù)雜度：O(n^2)

3.3 穩(wěn)定性：穩(wěn)定

您可能感興趣的文章: