首先需要一个递减的步长gap，最后的步长必须是1。工作原理是首先对相隔较远的元素的所有内容排序，然后再使用同样的方法对相隔近些的元素的排序，以此类推。
（3）归并排序
把数据等分成两部分, 各自用归并排序排好后再合并，它在归并时耗费O(n)的空间。
3、对排序算法的总结
(1)若n较小(如n≤40)，可采用插入排序或选择排序。当记录规模较小时，插入排序较好；反之，因为选择移动的记录数少于插人，应选选择排序为宜。(2)若文件初始状态基本有序(指正序)，则应选用插人、冒泡或随机的快速排序为宜；(3)若n较大，则应采用时间复杂度为O(N×Log2(N))的排序方法：快速排序、堆排序或归并排序。
快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；快速排序不适合用于“几乎已排好序”或“几乎正好倒序”的数据。在此最坏情况下，时间复杂度为O(N2)。堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。归并排序是稳定的,而且适用于数据量特别大以至于无法在内存中容纳,需要通过外存来进行的外部排序。
Shell排序的时间复杂度在数学上没有解决，大致可以认为是O(n(1+￡)), 其中￡是介于0和1之间的常数。
（二）查找算法
1.顺序查找法
即从第一个元素顺序到最后一个元素依次与待查的值进行比较，如果相等，查找成功，否则继续比较，直到所有元素都比较过了，如果还没有匹配的值，查找失败。查找适用于数据量少、不要求已经排序的数据，它的时间复杂度为O(N)；
2.二分查找
又称折半查找，适用于数据量大、已经排序的数据，它的时间复杂度为O(Log2(N))。
