排序算法之希尔排序（ShellSort）

一、简介

希尔排序又名缩小增量排序，属于插入排序，是对直接插入排序算法的一种改进。其平均时间复杂度为 O(n^1.3)，最好情况下为O(n)，最差为O(n2).

二、算法思想及步骤:

1.  对排序序列按一定的步长（gap）进行分组。

2. 分别对每组按直接插入排序进行排序。

3. 按一定规则缩减步长（例如可用每次步长减半的方式，即gap=gap/2）。

4. 重复2、 3 步骤直至步长减到1，对排序序列按步长为1进行分组，对每一分组进行最后一次插入排序。

注意：希尔排序中，序列元素个数是奇数还是偶数并不影响排序，只要最后步长能缩减到1就可。

三、图例详解

待排序序列如下所示：元素数为10，我们取步长为gap=10/2=5。按gap划分的组如下所示：

分组后对每组进行第一趟排序，结果如下：

第二趟排序，我们取gap= gap/2= 5/2 = 2, 并且对每一分组分别进行直接插入排序，排序后结果如下：

最后一趟排序，取gap = gap / 2 = 2 /2 = 1

 

从上述排序过程中，我们可以看到，序列在排序之前，蓝色的“5” 排在红色的“5” 前面，但是在排序之后，他们的相对位置就反了。所以希尔排序是一种不稳定的排序算法。

四、算法实现（C++）

#include "stdafx.h" #include <iostream> #include <vector> using namespace std; //对每一组元素进行直接插入排序 void InsertSort(vector<int>& vec,int start, int end,int gap) { int i = 0; int element = vec[end]; for (i = start; i < end; i += gap) { if (vec[i] > element) { break; } } if (i < end) { int j = end - gap; for (; j >= i; j -= gap) { vec[end] = vec[j]; } vec[i] = element; } } void ShellSort(vector<int>& vec) { int gap = vec.size() / 2; while (gap >= 1) // 控制排序的趟数，当gap减到1时，为最后一趟排序 { //开始一趟排序 for (int i = 0; i+gap < vec.size(); i++) { for (int j = i; j < vec.size(); j+= gap) { InsertSort(vec,i,j,gap); } } //一趟排序结束后，不要忘记更新步长gap的值 gap /= 2; } } int _tmain(int argc, _TCHAR* argv[]) { vector<int> vec; vec.push_back(9); vec.push_back(1); vec.push_back(2); vec.push_back(5); vec.push_back(7); vec.push_back(4); vec.push_back(8); vec.push_back(6); vec.push_back(3); vec.push_back(5); ShellSort(vec); for (size_t i = 0; i < vec.size(); i++) { cout << vec[i] << " "; } cout << endl; system("pause"); return 0; }