首页 > 代码库 > 处理海量数据的高级排序之——希尔排序（C++）
处理海量数据的高级排序之——希尔排序（C++）
希尔算法简介
常见排序算法一般按平均时间复杂度分为两类：
O(n^2)：冒泡排序、选择排序、插入排序
O(nlogn)：归并排序、快速排序、堆排序
简单排序时间复杂度一般为O(n^2)，如冒泡排序、选择排序、插入排序等
高级排序时间复杂度一般为O(nlogn)，如归并排序、快速排序、堆排序。
两类算法随着排序集合越大，效率差异越大，在数量规模1W以内的排序，两类算法都可以控制在毫秒级别内完成，但当数量规模达到10W以上后，简单排序往往需要以几秒、分甚至小时才能完成排序；而高级排序仍可以在很短时间内完成排序。
今天所讲的希尔排序是从插入排序进化而来的排序算法，也属于高级排序，只不过时间复杂度为O(n^1.5)，略逊于其他几种高级排序，但也远远优于O(n^2)的简单排序了。希尔排序没有明显的短板，不像归并排序需要大量的辅助空间，也不像快速排序在最坏的情况下和平均情况下执行效率差别比较大，且代码简单，易于实现。
一般在面对中等规模数量的排序时，可以优先使用希尔排序，当发现执行效率不理想时，再改用其他高级排序。
实际测试做了各个高级排序对大数据量排序的耗时对比（没错，冒泡排序就是拿出来搞笑的..），可以看到希尔排序的效率比其他几种O(nlogn)的高级排序差了几倍了，1W个数以下规模的排序这种差异还可以忽略不计的；但当数据规模超过10W以上时，可以很明显看到希尔排序效率跟其他高级排序差了很多。这种效率差距随着数据规模变大，会越来越大。
总结来说：希尔排序对中等大小规模数据表现良好，对规模非常大的数据排序不是最优选择。
算法稳定性：不稳定
基本概念
什么是增量？
增量也称步长。做个形象比喻：一个书架放着一排书，现在我们每数X本书就拿出一本，这个变量X就称之为增量。
希尔排序原理
教科书式表述：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
大白话表述：
仍然拿上述例子做比喻：一个书架放着一排书，现在从第一本书起每数X本书，就在那本书上贴红色贴纸，贴完红色贴纸后，再次从第二本书起每数X本书就贴上蓝色贴纸（跟之前颜色不同即可），重复贴纸过程，直到所有书都贴满贴纸。接着对有相同颜色贴纸的书做插入排序。然后撕掉所有贴纸后重新对书进行贴纸，这次则每数Y本书就贴纸（Y>X）,所有书贴满后再进行插入排序。重复贴纸排序、贴纸排序这个过程，直到最后每数1本书就贴纸（也就是每本书都贴同样颜色贴纸），再插入排序为止。
实现代码
#include "stdafx.h"#include <iostream>#include <ctime>using namespace std;int a[100000];#define BEGIN_RECORD \{ clock_t ____temp_begin_time___; ____temp_begin_time___=clock();#define END_RECORD(dtime) \dtime=float(clock()-____temp_begin_time___)/CLOCKS_PER_SEC;}/* 希尔插入排序过程 a - 待排序数组 s - 排序区域的起始边界 delta - 增量 len - 待排序数组长度*/void shellInsert(int a[], int s, int delta, int len){ int temp, i, j, k; for (i = s + delta; i < len; i += delta) { for(j = i - delta; j >= s; j -= delta) if(a[j] < a[i])break; temp = a[i]; for (k = i; k > j; k -= delta) { a[i] = a[i - delta]; } a[k + delta] = temp; }}/* 希尔排序 a - 待排序数组 len - 数组长度*/void shellSort(int a[], int len){ int temp; int delta; //增量 //Hibbard增量序列公式 delta = (len + 1)/ 2 - 1; while(delta > 0) //不断改变增量，对数组迭代分组进行直接插入排序，直至增量为1 { for (int i = 0; i < delta; i++) { shellInsert(a, i, delta, len); } delta = (delta + 1)/ 2 - 1; }}void shellSort2(int a[], int len){ int temp; int delta; //增量 //希尔增量序列公式 delta = len / 2; while(delta > 0) { for (int i = 0; i < delta; i++) { shellInsert(a, i, delta, len); } delta /= 2; }}void printArray(int a[], int length){ cout << "数组内容："; for(int i = 0; i < length; i++) { if(i == 0) cout << a[i]; else cout << "," << a[i]; } cout << endl;}int _tmain(int argc, _TCHAR* argv[]){ float tim; int i; for (i = 0; i < 1000000; i++) { a[i] = int(rand() % 100000); } cout << "10W个数的希尔排序：" << endl; for (i = 0; i < 1000000; i++) { a[i] = int(rand() % 100000); } BEGIN_RECORD shellSort2(a, sizeof(a)/sizeof(int)); END_RECORD(tim) cout << "希尔增量序列运行时间：" << tim << "s" << endl; for (i = 0; i < 1000000; i++) { a[i] = int(rand() % 100000); } BEGIN_RECORD shellSort(a, sizeof(a)/sizeof(int)); END_RECORD(tim) cout << "Hibbard增量序列运行时间：" << tim << "s" << endl; system("pause"); return 0;}
希尔排序的效率
希尔排序的增量序列是影响希尔排序效率的最关键因素，至今为止还没有一个最完美的增量序列公式。可究竟应该选取什么样的增量才是最好，目前还是一个数学难题。
看如下两个增量序列：
n/2、n/4、n/8...1
1、3、7...2^k-1
第一个序列称为希尔增量序列，使用希尔增量时，希尔排序在最坏情况下的时间复杂度为O(n*n)。
第二个序列称为Hibbard增量序列，使用Hibbard增量时，希尔排序在最坏情况下的时间复杂度为O(n^3/2)。
对10W个无序数分别以希尔增量序列、Hibbard增量序列进行希尔排序，耗时比较如图所示，在10W量级的排序，Hibbard增量序列比希尔增量序列的效率已经高了几倍。尽管Hibbard并不是最完美的增量序列，但表现已经非常不错，因此在实际应用中希尔排序多采用Hibbard增量序列。