首页 > 代码库 > 处理海量数据的高级排序之——希尔排序(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;}
View Code

 

希尔排序的效率                                                                                                                              
希尔排序的增量序列是影响希尔排序效率的最关键因素,至今为止还没有一个最完美的增量序列公式。可究竟应该选取什么样的增量才是最好,目前还是一个数学难题。

看如下两个增量序列:

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增量序列。