经典排序算法-----shell排序（C语言实现）
算法表述：
shell排序实际上是一种直接插入排序推广，其基本原理为其先将一组数分成若干组；此处应该注意，分组的方式不能几个几个紧挨着分组，而是采用每次所分组数均为素数且最后一次分组为1的方法，采用分组的好处是，在每次排序完后都是将小的数尽量往前面赶，大的数尽量往后面赶，最后一次排序直接采用直接插入排序。运用到了直接插入排序越有序有快的特性。
算法执行过程分析：
例如：12、5、9、34、6、8、33、56、89、0、7、4、22、55、77 具体步骤：
代码实现：
void Shell(int *arr,int len,int gap)
{
for(int i = gap;i < len;i++)
{
int temp = arr[i];
int j = 0;
for(j = i-gap;j >= 0;j-=gap)
{
if(arr[j] > temp)
{
arr[j+gap] = arr[j];
}
else
{
break;
}
}
arr[j+gap] = temp;
}
}
void Shell_Sort(int *arr,int len)
{
int drr[] = {5,3,1}; //drr[]为分的组数，这里5，3，1不固定，但必须相互为素数，且最后数为1
int lend = sizeof(drr)/sizeof(drr[0]);
for(int i = 0;i < lend;i++)
{
Shell(arr,len,drr[i]);
}
}
总结：
-
最好情况下时间复杂度为：O(n)；最坏情况下时间复杂度为：O(n^2) 空间复杂度：O(1) 稳定性：不稳定排序
下一篇：
数据结构-散列表 哈希表