高效排序——希尔排序

川长思鸟来 2021-12-11 00:15 168阅读 0赞

希尔排序是一种高性能的排序算法 ，其核心思想在于：

1.将数组分割为若干子数组，对每个子数组进行简单算法排序（如插入，梳排序均可）；

2.将排序后的子序列合并，继续重复步骤1；

直到所分的数组为1组。，算法结束。

那么上述中，如何分组呢？分组方式见《C++数据结构与算法》393页最下面的划分方式，当然对于希尔排序而言，目前并没有一种理论上最优的划分方式，书上提供的是一种较为优秀的划分方式。

下面直接上代码：

1 # include"iostream"
      2 # include "vector"
      3 # include "ctime"
      4 # include "cstdlib"  // 如果我们想通过随机数来验证我们的想法。应该预先给vecot分配内存
      5 # include "cmath"
      6 
      7 using namespace std;
      8 void insert_sort(vector<int> & );
      9 void ChooseSort(vector<int> &);
     10 void BubbleSort(vector<int> &);
     11 void CombSort(vector<int> & );
     12 void ShellSort(vector<int> &);
     13 int main()
     14 {
     15     const int MAX_NUMBER = 10000;//生成的随机数的个数
     16     const int MIN_VALUE = 1;   //随机数值的下界
     17     const int MAX_VALUE = 30000;//随机数值的上界
     18     vector<int> a;
     19     a.reserve(MAX_NUMBER);//预先分配内存你，预防迭代器的失效。否则内存搬移，迭代器容易失效
     20 
     21     // 采用控制台输入的方式 
     22     //int temp;
     23     //while (cin >> temp)
     24     //{
     25     //    a.push_back(temp);
     26     //    if (cin.get() == '\n') //注意这种用法，用的很多。
     27     //    {
     28     //        break;
     29     //    }
     30     //}
     31 
     32     //采用随机数生成法。
     33     srand((unsigned)time(NULL));//根据时钟生成不同的种子，保证每次运行程序产生不同的随机数
     34     for (int i = 1; i <= MAX_NUMBER; i++)
     35     {
     36         int temp;
     37         temp = (rand() % (MAX_VALUE - MIN_VALUE + 1)) + MIN_VALUE;//生成[MIN_VALUE，MAX_VALUE]之间的整数随机数
     38         a.push_back(temp);
     39     }
     40     //cout << "The initial order: ";    数据量太大，不适合输出
     41     //vector<int>::iterator ia = a.begin();
     42     //for (; ia != a.end(); ia++)
     43     //{
     44     //    cout << *ia << " ";
     45     //}
     46     //cout << endl;
     47     vector<int> b(a);
     48     vector<int> c(a);
     49     vector<int> d(a);
     50     vector<int> e(a);
     51     //show the initial order of the vector
     52     //cout << "The initial order before Sorting : ";
     53     //vector<int> ::iterator ia = a.begin();
     54     //for (; ia != a.end(); ia++)
     55     //{
     56     //cout << *ia << " ";
     57     //}
     58     //cout << endl;
     59     // 插入排序测试
     60     clock_t start, finish;
     61     double runtime;
     62     start = clock();
     63     insert_sort(a);
     64     finish = clock();
     65     runtime = (double)(finish - start) / CLOCKS_PER_SEC;
     66     cout << "The time of Insert Sort algorithm is：" << runtime << "s" << endl;
     67     // 选择排序测试
     68     start = clock();
     69     ChooseSort(b);
     70     finish = clock();
     71     runtime = (double)(finish - start) / CLOCKS_PER_SEC;
     72     cout << "The time of Choose Sort algorithm is：" << runtime << "s" << endl;
     73     // 冒泡排序测试
     74     start = clock();
     75     BubbleSort(c);
     76     finish = clock();
     77     runtime = (double)(finish - start) / CLOCKS_PER_SEC;
     78     cout << "The time of Bubble Sort algorithm is：" << runtime << "s" << endl;
     79     // 梳排序测试
     80     start = clock();
     81     CombSort(d);
     82     finish = clock();
     83     runtime = (double)(finish - start) / CLOCKS_PER_SEC;
     84     cout << "The time of Comb Sort algorithm is：" << runtime << "s" << endl;
     85     //希尔排序
     86     start = clock();
     87     ShellSort(e);
     88     finish = clock();
     89     runtime = (double)(finish - start) / CLOCKS_PER_SEC;
     90     cout << "The time of Shell Sort algorithm is：" << runtime << "s" << endl;
     91     system("pause");
     92     return 0;
     93 }
     94 //插入排序
     95 void insert_sort(vector<int> & sort_a)  ///注意，采用vector<int> 是可以作为参数进行传递的,那么是否可以作为返回类型使用呢？
     96 {
     97     int a_size ,temp;
     98     a_size = sort_a.size();
     99     for (int i = 1,j; i < a_size; i++)//注意，将j放在这里声明，不要放在下一个循环中声明，否则会造成多次声明？（但是作用域没变，多次声明应该被禁止，所以没有多次声明？）
    100     {
    101         temp = sort_a[i];
    102         for (j = i; (j > 0) && (sort_a[j - 1] > temp); j--)//这里先后顺序的差别，导致了数组的越界，
    103         {   
    104             sort_a[j] = sort_a[j-1];
    105         }
    106         sort_a[j] = temp;
    107     }
    108     //return sort_a;//说明可以将vector<int> 本身作为函数的返回值使用,但是需要清楚的是：返回的时候，内存实际上发生了局部变量复制，所以是否考虑返回引用？？？
    109 }
    110 //选择排序
    111 void ChooseSort(vector<int> & sort_a)
    112 {
    113     int a_size,MinNum;
    114     a_size = sort_a.size();
    115     for (int i = 0, j; i < a_size; i++)
    116     {
    117         int Loc = i;
    118         MinNum = sort_a[i];//本质是随机迭代器的使用
    119         //temp = sort_a[i];
    120         for (j = i+1; j < a_size; j++)
    121         { 
    122             if (sort_a[j] < MinNum)
    123             {
    124                 MinNum = sort_a[j];
    125                 Loc = j;
    126             }
    127         }
    128         //sort_a[i] = MinNum;//用于交换，但是本身自带的函数可以实现
    129         //sort_a[Loc] = temp;
    130         if (i != Loc)
    131         {
    132             swap(sort_a[i], sort_a[Loc]);//vector自带的东西
    133         }
    134     }
    135 }
    136 //冒泡排序
    137 void BubbleSort(vector<int> & sort_a)
    138 {
    139     int a_size;
    140     a_size = sort_a.size();
    141     for (int j = 0; j < a_size-1; j++)
    142     {
    143         for (int i = 0; i < a_size - 1-j; i++)
    144         {
    145             if (sort_a[i]>sort_a[i + 1])
    146                  swap(sort_a[i], sort_a[i + 1]);
    147         }
    148     }
    149 }
    150 //梳排序
    151 void CombSort(vector<int> & sort_a)
    152 {
    153     int step,j,k;
    154     step = sort_a.size();
    155     while ((step = int(step / 1.3)) >0)
    156     {
    157         for (j = sort_a.size() - 1; j >= step; j--)
    158         {
    159             k = j - step;
    160             if (sort_a[j] < sort_a[k])
    161             {
    162                 swap(sort_a[j], sort_a[k]);
    163             }
    164         }
    165     }
    166 }
    167 
    168 //希尔排序
    169 void ShellSort(vector<int> & sort_a)
    170 {
    171     int a_size;
    172     a_size = sort_a.size();//得到数组大小
    173     vector<int> ht;
    174     ht.resize(floor(log(a_size)/log(3)));//为增量数组预先分配空间
    175     ht[0] =1;//为何这样会出错？？？预分配空间后为何不能使用随机访问的机制？？？
    176     for (int i = 1; i<=ht.size()-1; i++)
    177     {
    178         ht[i] = 3 * ht[i - 1] + 1;
    179     }
    180     int ht_size = ht.size();
    181     vector<int> new_a;
    182     new_a.resize(a_size);
    183     for (int count = ht.size(), temp; count >= 1; count--)
    184     {
    185         temp = ht[count - 1];//temp的值决定了当前会被分成多少组
    186         //vector<int>a_divide;
    187         vector<vector<int>> aMatrix(temp, vector<int>(ceil(a_size / (1.0*temp))));//定义一个二维数组,
    188         for ( int i = 0; i < temp; i++)
    189         {
    190             int j;
    191             for (j = 0; (i + j*temp) < a_size; j++)
    192             {
    193                 aMatrix[i][j] = sort_a[i + j*temp];//将应该分为同一组的数据挑选出来    
    195             }
    196             if (ceil(a_size / (1.0*temp))>j)
    197             {
    198                 aMatrix[i][j] = 33333;//用于解决有0的问题
    199             }
    200            ;//问题是，本身有些空间存在0，这样写，将本身没有的0元素也进行了排序
    201         }
    202         //截止到这里，程序是没有问题的，也就是大部分是正确的，但是下面存在的问题是：数组中的0怎么办
    203         for(int k = 0, q = 0; k < ceil(a_size / (1.0*temp)); k++)
    204         {
    205             for (int p = 0; p < temp; p++)
    206             {
    207                 sort_a[q] = aMatrix[p][k];
    208                 q = q + 1;
    209                 if (q >= a_size)
    210                     break;
    211             }
    212             if (q >= a_size)
    213                 break;
    214         }
    215     }
    216         
    217 }

实际上，上述给出很多排序算法的代码。

169-215行为希尔排序算法的实现，对算法的各个部分进行解读：

179行以前，求解每次分组的次数；

200行以前，将同一组的数据提取出来，组成一个矩阵，每行表示同一组的，不同行表示不同分组，对每行的数据采取梳排序

200行以后，将输入向量更新为矩阵列向量的拼接值

重复迭代，直到h =1；

针对希尔排序，其主要思想是一种分治的思想，给出上述排序算法效率的对比：

![1288560-20190605193944357-1542475938.png][]

该次测试中，随机数的个数为10000个，从结果中可以看出，希尔排序效率最高，但其和梳排序的效率较为接近（思考原因）

在手撸希尔排序算法的过程中，遇到了很多c++中的问题，在此给出以下说明：

ht.resize(floor(log(a_size)/log(3)));这句代码的本意是给数组ht预分配空间，开始使用的是ht.reserve()，但发现这样写，在调试的时候，导致ht[0] =1;出错，这说明并没有达到我们想要的结果。百度了下，发现：

![1288560-20190605194723359-1396551087.png][]

可见，使用reserve（）并不会改变vector的大小,并不会和我们想的那样在内存中开辟出一片空间给vector。因此，若我们需要开辟一块可用空间，应该用resize（）。那reserve()的作用是什么呢？（悬而未决）

vector<vector<int>> aMatrix(temp, vector<int>(ceil(a_size / (1.0*temp))));定义了一个temp×ceil(a_size / (1.0*temp))大小的二维数组aMatrix，注意这是使用vector定义的二维数组，需要注意的是vector允许这种嵌套定义。

另一个点在于CombSort(aMatrix\[i\])，CombSort的形参形式为数组引用，但这里传递是一个1维指针，说明某种意义上两者可以相互转换。但这个本质上说明了一个二维数组，只取一维其实就是一个指针。

转载于:https://www.cnblogs.com/shaonianpi/p/10981632.html

[1288560-20190605193944357-1542475938.png]: /images/20211210/6675fc469a664ae58933146dacc8d2f0.png
[1288560-20190605194723359-1396551087.png]: /images/20211210/f0524a5efbb14663b9a168307ffe2234.png