个人简介
小公司研发总监，既当司令也当兵！
文章分类
相关博文
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
分类： 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)，与增量序列选择有关。
下面是一种实现（增序）：
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)，与增量序列选择有关。
下面是一种实现（增序）：
点击(此处)折叠或打开
-
void shellsort(int list[], int len)
-
{
-
int increment = len / 2;
-
-
int insertkey;
-
int cursor;
-
int i,j;
-
-
for (increment = len / 2; increment > 0; increment /= 2) //按长度2折法分组，直到增量为1
-
{
-
for (i = 0; i < increment; i) // 循环处理每一组
-
{
-
for (j = i increment; j < len; j = increment)// 每组内部执行插入排序
-
{
-
insertkey = list[j];
-
cursor = j - increment;
-
-
while (cursor >= i && list[cursor] > insertkey)
-
{
-
list[cursor increment] = list[cursor];
-
cursor -= increment;
-
}
-
list[cursor increment] = insertkey;
-
}
-
}
-
}
- }
给主人留下些什么吧！~~