wordpress 转换appaso优化公司

　　希尔排序又称”缩小增量排序”，我们知道插入排序，插入排序的时间复杂度为Ｏ(n^2)。对于插入排序，当ｎ值较小时，效率会提升；当待排序列为＂基本有序1＂时，效率会提高，接近于Ｏ(n)。希尔排序正是对插入排序在这两点上做出优化的一种排序方法。
　　它的基本思想就是，将整个待排序列分割成若干个小的序列（由一个增量相隔）将其分别进行插入排序，然后缩小增量再次分割排序，直到整个元素基本有序时，在对全体进行排序（增量为１）。

　　对于数组arr[] = {5,6,7,3,2,4,1,3,1,4};
　　
　　第一趟，增量为sz/2 = 5
　　
　　
　　第二趟，增量为5/2 = 2
　　
　　
　　第三趟，增量为2/2 = 1，即将第二趟结果进行插入排序
　　

排序完成

代码如下：

#include<stdio.h>//sz数组总长度,n为组的起始位置,gap为的步长
void insertion_sort(int *arr,int sz,int n,int gap)
{int i,j,temp;for(i=n+gap; i<sz; i+=gap){if(arr[i] < arr[i-gap])//每个元素与组内元素插入排序{temp = arr[i];j = i-gap;while(j>=0 && temp<arr[j]){arr[j+gap] = arr[j];j -= gap;}arr[j+gap] = temp;}}
}void shell_sort(int *arr,int sz)//sz为待排数组长度
{int n,gap;//gap为步长,每次减少一半for(gap=sz/2; gap>0; gap/=2){for(n=0; n<gap; n++)//共gap个组,对每组进行插入排序insertion_sort(arr,sz,n,gap);}
}int main()
{int i;int arr[] = {5,6,7,3,2,4,1,3,1,4};int sz = sizeof(arr)/sizeof(arr[0]);shell_sort(arr,sz);for(i=0; i<sz; i++)printf("%d ",arr[i]);return 0;
}