Go语言希尔排序希尔排序 java( 三 )

int count;
count=sizeof(data)/sizeof(int);
printf("原数组: ");
printData(data,count);
shell(data,count);
printf("\n最后的排序结果: ");
printData(data,count);
return 0;
}
谁知道什么叫“谢尔排序”（也叫“希尔排序”）希尔排序
日期：2005-5-25 10:45:55来源:编辑：175
它的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
在希尔排序中，子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。如在第一趟排序时的增量为7，即将相隔为7的元素编成一组进行直接插入排序。第二趟排序时的增量为3，增量进一步缩小。由于在这两趟的插入排序中在子序列中逆序的关键字是跳跃式地移动，从而使得在进行最后一趟增量为1的插入排序时，序列已基本有序，只要作少量比较和移动即可完成排序，因此希尔排序的时间复杂度较直接插入排序低。
下面用算法语言描述的希尔排序:
希尔排序中增量序列的选取是一个复杂的问题，涉及到一些数学上尚未解决的难题。我们不想加以详细讨论。到目前仅得出部分结论：如当增量序列为d[k]=2t-k+l -1时，希尔排序的运行时间为O(n3/2)，其中1≤k≤t≤└log2(n＋1)┘ 。增量序列还可以有各种取法, 如d[k]=2t-k，（d=…,9,5,3,2,1）。但请注意：应使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须等于1 。
希尔排序图解流程图.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px}排序算法是《数据结构与算法》中最基本Go语言希尔排序的算法之一。排序算法可以分为内部排序和外部排序Go语言希尔排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是希尔排序算法：
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率Go语言希尔排序；但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位Go语言希尔排序；

Go语言希尔排序 希尔排序 java( 三 )

Go语言希尔排序希尔排序 java( 三 )