xyjzsh

插入排序vs希尔排序

什么是插入排序?
在插入排序法中,将检查数组中的每个元素,将它插入排序中的元素的适当位置,当最后一个元素插入到它适当的位置时,这个数组就排好序了。例如,

假如我们要对一个有5个元素的数组进行升序排列,假设第一个元素的值被假定为已排好序了,那么我们将第2个元素插入到已排序好的数组中的适当位置上,使得数组应该是排序好的。依次类推,将第3个插入到到已排序好的数组中的适当位置,使得插入后数组仍然是排序好的,。。。。。。
下面是一个插入排序的Demo:
int tarArr[]={10,1,35,12,7,17,66,6,56,26};
int size = sizeof(tarArr)/sizeof(tarArr[0]);

void insertSort(void)
{
    
int i=0,j=0;
    
for(i=1;i<size;i++)
    
{
        
int nextValue = tarArr[i];
        
for(j=i-1;j>=0;j--)
        
{
            
if(nextValue<tarArr[j])
                tarArr[j
+1]=tarArr[j];
            
else
            
{
                
break;
            }

        }

        tarArr[j
+1]=nextValue;
    }

}

下面来介绍一下希尔排序:
希尔排序就是将要排序的数据先分成如果组,对每一组实行插入排序。
代码如下:
int tarArr[]={10,1,35,12,7,17,66,6,56,26};
int size = sizeof(tarArr)/sizeof(tarArr[0]);

void shellSort(void)
{
    
int gap =0,i=0,j=0;
    
for(gap = size/2;gap>0;gap/=2)
    
{
        
for(i=gap;i<size;i+=gap)
        
{
            
int nextValue = tarArr[i];
            
for(j=i-gap;j>=0;j-=gap)
            
{
                
if(nextValue<tarArr[j])
                    tarArr[j
+gap] = tarArr[j];
                
else
                
{
                    
break;
                }


            }

            tarArr[j
+gap] = nextValue;
        }

    }

}

posted on 2011-02-23 17:44 呆人 阅读(340) 评论(0)  编辑 收藏 引用 所属分类: 算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年1月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜