本文主要是介绍数据结构与算法——谢尔排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
谢尔排序就是每隔一段距离的一个子序列进行插入排序；间隔是从大到小发生改变。谢尔排序也称为缩减增量排序。
比如数据序列v: 81 94 11 96 12 35 17 95 28 58 41 75 15 (序列个数为13)
增量序列是：h1, h2, h3, ......, hk
谢尔增量序列是：hk=N/2, hk-1=hk/2, .....(N是序列的数据个数)
Hibbard增量序列：{1, 3, ..., 2^k-1}
Sedgewick增量序列：{1, 5, 19, 41, 109..}该序列中的项或者是9*4^i - 9*2^i + 1或者是4^i - 3*2^i + 1;
间隔6的子序列是：
1、
排序之前v: 81 94 11 96 12 35 17 95 28 58 41 75 15
81， 17， 15 -----》子序列插入排序之后是-----》15， 17， 81
排序之后v: 15 94 11 58 12 35 17 95 28 96 41 75 81
2、
排序之前v: 15 94 11 58 12 35 17 95 28 96 41 75 81
94， 95 -----》子序列插入排序之后是-----》94， 95
排序之后v: 15 94 11 58 12 35 17 95 28 96 41 75 81
3、
排序之前v: 15 94 11 58 12 35 17 95 28 96 41 75 81
11， 28 -----》子序列插入排序之后是-----》11， 28
排序之后v: 15 94 11 58 12 35 17 95 28 96 41 75 81
4、
排序之前v: 15 94 11 58 12 35 17 95 28 96 41 75 81
58， 96 -----》子序列插入排序之后是-----》 58， 96
排序之后v: 15 94 11 58 12 35 17 95 28 96 41 75 81
5、
排序之前v: 15 94 11 58 12 35 17 95 28 96 41 75 81
12， 41 -----》子序列插入排序之后是-----》 12， 41
排序之后v: 15 94 11 58 12 35 17 95 28 96 41 75 81
6、
排序之前v: 15 94 11 58 12 35 17 95 28 96 41 75 81
35， 75 -----》子序列插入排序之后是-----》 35， 75
排序之后v: 15 94 11 58 12 35 17 95 28 96 41 75 81
所有的间隔为6的子序列排序之后的序列输出是：v: 15 94 11 58 12 35 17 95 28 96 41 75 81
（见输出结果6: 15 94 11 58 12 35 17 95 28 96 41 75 81）：
间隔3的子序列是：
1、
排序之前v: 15 94 11 58 12 35 17 95 28 96 41 75 81
15， 58， 17， 96， 81 -----》子序列插入排序之后是-----》15， 17， 58， 81， 96
排序之后v: 15 94 11 17 12 35 58 95 28 81 41 75 96
2、
排序之前v: 15 94 11 17 12 35 58 95 28 81 41 75 96
94， 12， 95， 41 -----》子序列插入排序之后是-----》12， 41， 94， 95
排序之后v: 15 12 11 17 41 35 58 94 28 81 95 75 96
3、
排序之前v: 15 12 11 17 41 35 58 94 28 81 95 75 96
11， 35， 28， 75 -----》子序列插入排序之后是-----》11， 28， 35， 75
排序之后v: 15 12 11 17 41 28 58 94 35 81 95 75 96
（其实到这一步的时候，这个已经是间隔为3这种情况下最后的输出结果了。
见输出结果3: 15 12 11 17 41 28 58 94 35 81 95 75 96）
间隔1的子序列是：
v:15 12 11 17 41 28 58 94 35 81 95 75 96
此时其实就相当于是直接对v进行一次插入排序。
排序输出结果是：
v: 11 12 15 17 28 35 41 58 75 81 94 95 96
运行输出结果：
v: 81 94 11 96 12 35 17 95 28 58 41 75 15
6: 15 94 11 58 12 35 17 95 28 96 41 75 81
3: 15 12 11 17 41 28 58 94 35 81 95 75 96
1: 11 12 15 17 28 35 41 58 75 81 94 95 96
v: 11 12 15 17 28 35 41 58 75 81 94 95 96
用谢尔增量实现谢尔排序的源代码：
/*************************************************************************> File Name: shellsort.cpp> Author: > Mail: > Created Time: 2016年01月08日 星期五 22时16分24秒************************************************************************/#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;int main()
{vector<int> v;v.push_back(81);v.push_back(94);v.push_back(11);v.push_back(96);v.push_back(12);v.push_back(35);v.push_back(17);v.push_back(95);v.push_back(28);v.push_back(58);v.push_back(41);v.push_back(75);v.push_back(15);cout << "v: ";copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));cout << endl;for (int gap = v.size()/2; gap > 0; gap /= 2){//增量序列for (int i = gap; i < v.size(); ++i){//对间隔为gap的子序列进行插入排序int tmp = v[i];int j = i;for ( ; j >= gap && tmp < v[j-gap]; j -= gap)v[j] = v[j-gap];v[j] = tmp;}cout << gap << ": ";copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));cout << endl;}cout << "v: ";copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));cout << endl;return 0;
}
这篇关于数据结构与算法——谢尔排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
