查找和排序算法

shell排序

1、基本思想

希尔排序(Shell's sort)又称为“缩小增量排序”，本质上它也是一种插入排序，但在时间效率上较直接插入排序、折半插入排序等有较大的该机。

从对直接插入排序的分析可知，其算法时间复杂度为O(n2)，但是如果待排序记录序列为“正序”时，其时间复杂度可以提高到O(n)。由此设想，如果待排序记录序列“基本有序”时，则直接插入排序的效率就可以大大提高；从另一方面来看，由于直接插入排序算法简短，则在n值很小时效率也比较高。希尔（shell）排序正是从这两点分析出发对直接插入排序进行改进得到的一种插入排序方法。

基本思想是：先将整个待排序记录分割成为若干子序列分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。

 

2、排序源码

void shellsort(int array[],int n){

 int gap,i,j,temp;

　　　　//外层循环用来分割子序列

　　　　for(gap=n/2;gap>0;gap/=2) 

　　　　{

　　　　　　　　//内层的两个循环对每一个子序列同时做直接插入排序

　　　　　　　　for(i=gap;i<n;i++)

　　　　　　　　　　　　for(j=i-gap;j>=0&&array[j]>array[j+gap];j-=gap)

　　　　　　　　　　　　{

　　　　　　　　　　　　　　　　temp=array[j];

　　　　　　　　　　　　　　　　array[j]=array[j+gap];

　　　　　　　　　　　　　　　　array[j+gap]=temp;

　　　　　　　　　　　　}

　　　　}

}