Chinaunix首页 | 论坛 | 博客
  • 博客访问: 664384
  • 博文数量: 141
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1114
  • 用 户 组: 普通用户
  • 注册时间: 2014-03-17 14:32
个人简介

小公司研发总监,即当司令也当兵!

文章分类

全部博文(141)

分类: LINUX

2016-02-16 17:06:11

SHELL排序是直接插入法排序的一种改建,直接插入法一趟只处理一个数,其他数的信息未被处理。
SHELL排序的核心思想是:
(1)把待排序列分为n个组,每个组内部执行一次插入排序;
(2)减小n值,重新分组,每组内部执行一次插入排序;直到n=1,执行插入排序后完成。

例如,待排序列:
1    9    2    7    35    0    3    8 (长度8)

第一轮:
按常见的序列长度2折法分组,第一次分为 4组( 8 / 2 )
1, 35  ——  1, 35
9, 0    ——  0, 9
2, 3    ——  2, 3
7, 8    ——  7, 8
第一轮分组,执行插入排序后:
1    0    2    7     35    9    3    8

第二轮:
第二轮分组为2(4 / 2)
1, 2, 35, 3  ——  1, 2, 3, 35
0, 7, 9, 8 —— 0, 7, 8, 9
第二轮分组,执行插入排序后:
1    0    2    7    3    8    35    9

第三轮:
第三分组为1 (2 / 2)
1, 0, 2, 7, 3, 8, 35, 9  ——  0, 1, 2, 3, 7, 8, 9, 35

SHELL排序是一种不稳定的排序算法,文献表明其时间复杂度受增量序列的影响明显大于其他因素,最坏的情况是o(n2),好的情况在o(n1.3),与增量序列选择有关
下面是一种实现(增序):


点击(此处)折叠或打开

  1. void shellSort(int list[], int len)
  2. {
  3.     int increment = len / 2;

  4.     int insertKey;
  5.     int cursor;
  6.     int i,j;

  7.     for (increment = len / 2; increment > 0; increment /= 2) //按长度2折法分组,直到增量为1
  8.     {
  9.         for (i = 0; i < increment; i++) // 循环处理每一组
  10.         {
  11.             for (j = i + increment; j < len; j += increment)// 每组内部执行插入排序
  12.             {
  13.                 insertKey = list[j];
  14.                 cursor = j - increment;

  15.                 while (cursor >= i && list[cursor] > insertKey)
  16.                 {
  17.                     list[cursor + increment] = list[cursor];
  18.                     cursor -= increment;
  19.                 }
  20.                 list[cursor + increment] = insertKey;
  21.             }
  22.         }
  23.     }
  24. }


阅读(2371) | 评论(0) | 转发(0) |
0

上一篇:直接插入法排序

下一篇:选择排序

给主人留下些什么吧!~~