剖析插入排序

浏览数：33 / 时间：2015年06月08日

插入排序---直接插入排序
int a[10];
for(int i=1;i<10;i++){
if(a[i] < a[i-1])
{
int j = i-1;
int t = a[i];
while(t<a[j] && j>=0)
{
a[j+1] = a[j];
j--;
}
a[j+1] = x;
}
}
时间复杂度：T(n)=O(n^2)

插入排序---希尔排序

首先应当理解希尔排序算法：
例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我们对每列进行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后变为：

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步长进行排序（此时就是简单的插入排序了）。

void print(int a[], int n, int i)
{
printf("%d:",i);
for(int j=0; j<8; j++)
{
printf("%-3d",a[j]);
}
}

void ShellInsertSort(int a[], int n, int dk)
{
for(int i = dk; i<n; i++)
{
if(a[i] < a[i-dk])
{
int j = i-dk;
int x = a[i];
a[i] = a[i-dk];
while(x < a[j] && j>=0)
{
a[j+dk] = a[j];
j -=dk;
}
a[j+dk] = x;
}
print(a,n,i);
}
}

void shellSort(int a[], int n)
{
int dk = n/2;
while( dk >=1 )
{
ShellInsertSort(a,n,dk);
dk /= 2;
}
}

int main()
{
int a[8] = {3,4,2,1,5,3,1,9};
shellSort(a,8);
print(a,8,8);
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

剖析插入排序