希尔排序算法 |flying0033

winston

希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

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

1. #ifndef SHELLSORT_H
2. #define SHELLSORT_H
3. template<class T> void ShellSort(T *a,int len) //希尔排序算法
4. {
5.         int gap,j;
6.         for(gap = len / 2;gap > 0;gap /= 2)
7.         {
8.                 for(j = gap;j < len;++j) //j从gap个元素开始
9.                 {
10.                         if(a[j] < a[j - gap]) //每个元素与自己组内的数据进行直接插入排序
11.                         {
12.                                 T temp = a[j];
13.                                 int k = j - gap;
14.                                 while(k >= 0 && a[k] > temp)
15.                                 {
16.                                         a[k + gap] = a[k];
17.                                         k -= gap;
18.                                 }
19.                                 a[k + gap] = temp;
20.                         }
21.                 }
22.         }
23. }
24. #endif //SHELLSORT_H

复制代码

测试代码:

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

复制代码

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