论坛 › 算法研讨 › 希尔排序算法 |flying0033

winston 发表于 2011-12-15 14:00:26

希尔排序算法 |flying0033

希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高

#ifndef SHELLSORT_H
#define SHELLSORT_H
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 < a) //每个元素与自己组内的数据进行直接插入排序
                        {
                                T temp = a;
                                int k = j - gap;
                                while(k >= 0 && a > temp)
                                {
                                        a = a;
                                        k -= gap;
                                }
                                a = temp;
                        }
                }
        }
}
#endif //SHELLSORT_H

测试代码:#include "ShellSort.h"
#include <stdio.h>
int main()
{
        int a[] = {12,5,35,42,37,15,4,3,2,1,11,9,23};
        int len = sizeof(a) / sizeof(*a);
        ShellSort(a,len);
        printf("经过希尔排序后的数组序列:\n");
        for(int i = 0;i < len;++i)
                printf("%d ",a);
        printf("\n");
        return 0;
}

作者：flying0033 发表于2011-12-14 15:18:09 原文链接

查看完整版本: 希尔排序算法 |flying0033