当前位置: 首页 > 网站开发 > 正文

希尔排序

1 星2 星3 星4 星5 星 (暂无评分)
Loading ... Loading ...
baidu_share

希尔排序(Shell Sort)又称为缩小增量排序,输入插入排序算法,是对直接排序算法的一种改进。本文介绍希尔排序算法。

对于插入排序算法来说,如果原来的数据就是有序的,那么数据就不需要移动,而插入排序算法的效率主要消耗在数据的移动中。因此可知:如果数据的本身就是有序的或者本身基本有序,那么效率就会得到提高。

希尔排序的基本思想是:将需要排序的序列划分成为若干个较小的子序列,对子序列进行插入排序,通过则插入排序能够使得原来序列成为基本有序。这样通过对较小的序列进行插入排序,然后对基本有序的数列进行插入排序,能够提高插入排序算法的效率。

在希尔排序中首先解决的是子序列的选择问题。对于子序列的构成不是简单的分段,而是采取相隔某个增量的数据组成一个序列。增量一般的选择原则是:取上一个增量的一半作为此次序列的划分增量。首次选择序列长度的一半为增量。

先假如:数组的长度为10,数组元素为:25、19、6、58、34、10、7、98、160、0

整个希尔排序的算法过程如下如所示:

1345900871_6145
上图是原始数据和第一次选择的增量 d = 5。本次排序的结果如下图:
1345900899_1825
上图是第一次排序的结果,本次选择增量为 d=2。 本次排序的结果如下图:
1345900956_9477
当d=1 是进行最后一次排序,本次排序相当于冒泡排序的某一次循环。最终结果如下:
1345900995_3202

在实际使用过程中,带排序的数据肯定不是只有十个,但是上述是希尔排序的思想。其实希尔排序只是插入排序的一种优化。
C++实现希尔排序的代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>  
using namespace std;  
 
 
void shell_sort(int array[] , int length)  
{  
    int i , j , temp;  
    int d = length/2;       // 设置希尔排序的初始增量  
 
    while(d >= 1)  
    {  
        for(i = d ; i < length ; ++i)  
        {  
            temp = array[i];  
            j = i - d;       // 步长为d的前面一个位置  
            while(j >= 0 && array[j] > temp)        // 从后往前进行插入排序  
            {  
                array[j + d] = array[j];  
                j -= d;  
            }  
            array[j + d] = temp;     // 找到了插入位置  
        }  
        d /= 2;  
    }  
}  
 
int main(void)  
{  
    int i , a[]={25,19,6,58,34,10,7,98,160,0};  
    shell_sort(a , 10);  
    for(i = 0 ; i < 10 ; ++i)  
        cout<<a[i]<<" ";  
    cout<<endl;  
    system("pause");  
    return 0;  
}  
 
 
// 模板  
template<class T> void ShellSort(T *a,int len) //希尔排序算法  
{  
    int gap , j;  
    for(gap = len / 2 ; gap > 0 ; gap /= 2)  
    {  
        for(j = gap;j < len ; ++j) //j从gap个元素开始  
        {  
            if(a[j] < a[j - gap]) //每个元素与自己组内的数据进行直接插入排序  
            {  
                T temp = a[j];  
                int k = j - gap;  
                while(k >= 0 && a[k] > temp)  
                {  
                    a[k + gap] = a[k];  
                    k -= gap;  
                }  
                a[k + gap] = temp;  
            }  
        }  
    }  
}

本文固定链接: http://www.chepoo.com/shell-sort.html | IT技术精华网

【上一篇】
【下一篇】

希尔排序:等您坐沙发呢!

发表评论