基于順序表的插入排序（常規插入排序，二分插入排序，希爾排序）
這三種的都是插入排序算法的時間復雜度基本相似，但由于希爾排序不同于其他排序方式的思想，所以其時間復雜度會有所不同。

常規插入排序：O(n2);
二分插入排序：O(n2);減少了找到插入位置的時間，但還是要一位位進行插入！
希爾排序：O(n1.25);

數據結構定義及其初始化函數：
typedef struct SqNode{
int data;
}SqNode;

typedef struct Node{
SqNode *head;
int length;
}SqList;

int Init_SqList(SqList &L)
{
L.head = new SqNode [N];
L.length = 1;
if (L.head)
return OK;
else
return ERROR;
}
常規插入排序：

void Insert_sort(SqList &L) {int ii,j;for (ii = 2;ii < L.length;ii++){if (L.head[ii - 1].data > L.head[ii].data) //優化:設置監視哨的方法進行優化！！！ {L.head[0]= L.head[ii];L.head[ii] = L.head[ii - 1];for (j = ii - 1; L.head[j].data > L.head[0].data ;j--)L.head[j + 1] = L.head[j];L.head[j + 1] = L.head[0];}} }

二分插入排序：

void Bin_Insert_sort(SqList &L)//二分插入排序 {int left,mid,right;int ii,j;for (ii = 2;ii < L.length;ii++){if (L.head[ii - 1].data > L.head[ii].data) // 優化 {L.head[0] = L.head[ii];//二分法查找插入位置 left = 1;right = ii - 1;while (left <= right) //注意這里的控制條件 {mid = (left + right) / 2;if (L.head[0].data < L.head[mid].data)right = mid - 1;elseleft = mid + 1;}//for (j = ii - 1;j >= right + 1;j --)L.head[j + 1] = L.head[j]; L.head[j + 1] = L.head[0];}} }

希爾排序：

void Hill_Insert_sort(SqList &L,int dk) //希爾排序 {int ii,j;for (ii = dk + 1;ii < L.length;ii++){if (L.head[ii - dk].data > L.head[ii].data){L.head[0] = L.head[ii];L.head[ii] = L.head[ii - dk];for (j = ii - dk;j > 0 && L.head[j].data > L.head[0].data;j-=dk) //因為j有可能減小為負數所以L.head[j].data <= L.head[0].data 有可能不會發生，所以要添加判斷條件j < 0!!!L.head[j + dk] = L.head[j];L.head[j + dk] = L.head[0];//注意！！！ } } }

在實際調用時需要有外層循環來控制dk的值.

數據結構在考研中十分重要，所以我們應該熟練掌握相關代碼及其思想.

總結

以上是生活随笔為你收集整理的数据结构之基于顺序表的插入排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。