简谈算法之希尔排序

michael_llh

简谈算法之希尔排序 [复制链接]

        希尔排序是一种插入排序，是我们之前说到的直接插入排序的升级版本，改进版，它是一种不稳定的排序方式。（稳定的意思就是说一个序列中如果有两个或者两个以上的相同的数据，那么经过排序之后他们的相对位置保持不变的话那么他就是一个稳定排序）。希尔排序实质是一个分组插入的方法，通过取一个增量，进行两个数据的排序，一直到增量为1，则整个排序结束，大概的一个过程如下：

       一般的话最开始的时候我们选择的增量大小为整个序列的一般，然后每次都减半，知道这个增量减小到1即完成排序过程。

       我们具体来说明一下：

       比如我们有10个数字：

45, 87 ,562, 56, 632, 12 ,78, 58, 41, 69

       那么对于增量的话我们第一次得到的是10/2 = 5，第一次的增量为5，那么也就是说从第一个数字开始我们会跳过一个增量5，然后和增量为5的这个位置的数字进行结合。也就是说这个时候我们会分成5组，5组分别是：

(45 , 12) (87 , 78) (562 , 58) (56 , 41) (632 , 69)

       然后对比这五个分组中的数值，如果左边的比右边来的大，那么进行交换即可。所以我们最终得到的5组的结果是：

(12 , 45) (78 , 87) (58 , 562) (41 , 56) (69 , 632)

       那么最终经过第一次排序我们最终得到的数组的结果是：

12, 78, 58, 41, 69, 45, 87, 562, 56, 632

       第二趟的话我们进行重新计算增量，我们上次得到的增量是5，所以减半的话得到的就是2，所以我们从增量2开始第二趟的计算，这个时候我们的分组就是从第一个开始数两个，然后和相邻的第二个进行配对，依次完成整个配对过程。最终如下：

(12 , 58, 69, 87, 56) (78, 41, 45, 562, 632)

       然后就是在这两组中进行一个排序，最终的排序结果如下：

(12 , 56, 58, 69, 87) (41, 45, 78, 562, 632)

       那么经历过第二趟我们看下最终的排序结果：

12, 41, 56, 45, 58, 78, 69, 562, 87, 632

       第三趟的时候我们的增量就是1了，这个时候就是最后一次的排序了，也是对整个数据进行排序，这个时候已经是接近有序的状态了，最终排序后得到最后的结果：

12 41 45 56 58 69 78 87 562 632

我们总结一下这个排序流程：

(1)将所有的N个数据进行分组，分成了n/2个数据序列，第1个数据和第n/2+1个数据组成一队，后面依次。

(2)一次循环使每一个序列对排好顺序

(3)然后变成n/4个序列，再次进行排序

(4)不断重复上述的过程，直到序列减少为一个，也就完成了整个排序过程。

这就是一个希尔排序的过程，我们现在看下如何具体的实现这个程序：

1. #include <iostream>
   
2. 
   
3. using namespace std;
   
4. 
   
5. void ShellSort(int a[] ,int len)
   
6. {
   
7.     int i, j, h;
   
8.     int r, temp;
   
9.     int x = 0;
   
10. 
    
11.     // 这里就是判断每次的序列个数，最终的结束条件就是r=1，也就是序列只有一个
    
12.     // r这里代表的就增量，也等同于序列的个数
    
13.     for(r = len/2; r>=1; r/=2)
    
14.     {
    
15.         // 然后对序列内的元素进行排序
    
16.         for(i=r; i<len; i++)
    
17.         {
    
18.             temp = a[i];
    
19.             j = i-r;
    
20.             // 对元素大小进行判断排序
    
21.             while(j>=0 && temp<a[j])
    
22.             {
    
23.                 a[j+r] = a[j];
    
24.                 j-=r;
    
25.             }
    
26.             a[j+r] = temp;
    
27.         }
    
28.     }
    
29. }
    
30. int main()
    
31. {
    
32.     int a[] = {45, 87 ,562, 56, 632, 12 ,78, 58, 41, 69 };
    
33.     ShellSort(a, 10);
    
34.     for(int i=0; i<sizeof(a)/sizeof(a[0]); i++)
    
35.         cout << a[i] << ' ';
    
36.     cout << endl;
    
37.     return 0;
    
38. }
    

复制代码

johnrey

如果最后一趟要对全序列排序，那么这个算法又有啥意义呢？毕竟对计算机而言，不管你是没排序，还是接近有序，做的过程都是一样的

michael_llh

johnrey 发表于 2017-1-9 07:43
如果最后一趟要对全序列排序，那么这个算法又有啥意义呢？毕竟对计算机而言，不管你是没排序，还是接近有序 ...

各个算法在它出现的时间点总是有它的创新所在，可能现在没有很多实用，但是现在也是一个学习的过程，简谈算法也就是为了学习这些所有的算法，具体实际的应用没有考虑