这篇文章主要介绍了希尔排序算法的C语言实现示例,希尔排序可以看作为一种高级的插入排序,需要的朋友可以参考下
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序（冒泡排序或插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。
一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用i += step_size而不是i++）。
C语言实现示例
#include #include #include #define LEN 10 typedef int dataType; //初始化数组，赋值整数随机数 void initArr(dataType arr[], int len); //希尔排序 void shellSort(dataType arr[], int len); //交换两个数 void swap(dataType &x,dataType &y); //打印数组元素 void print(dataType arr[], int len); int main() { dataType arr[LEN]; initArr(arr,LEN); printf("================希尔排序================"); //输出排序前的数组元素 printf("\n排序前数组元素:"); print(arr,LEN); shellSort(arr,LEN); printf("\n排序后数组元素:"); print(arr,LEN); printf("\n"); return 0; } //初始化数组，赋值整数随机数 void initArr(dataType arr[], int len) { int i = 0; srand((unsigned)time(NULL)); for(i = 0; i <len; i++) arr[i] = rand(); } //希尔排序 void shellSort(dataType arr[], int len) { int h = 0; int i = 0; int j = 0; //设置步长 for(h = 1; h <len; h = 3 * h + 1) ; while(h) { h /= 3; if(h <1) break;来源gaodaima#com搞(代@码网 for(i = h; i = h; j-=h) { if(arr[j-h] 以上就是希尔排序算法的C语言实现示例的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：希尔排序算法的C语言实现示例
转载请注明原文链接：希尔排序算法的C语言实现示例
