php网站漂浮广告代码,wordpress分类搜索,wordpress不能更新,华为手机网站建设策划方案【0】README
0#xff09;希尔排序是基于插入排序的。将插入排序算法 内for循环中的所有 1 改为增量就可以。。bingo。。 插入排序源码
1#xff09;本文旨在给出 希尔排序#xff08;缩小增量排序#xff09;之塞奇威克增量序列 的源码实现#xff1b;
2#xff09;为…【0】README
0希尔排序是基于插入排序的。将插入排序算法 内for循环中的所有 1 改为增量就可以。。bingo。。 插入排序源码
1本文旨在给出 希尔排序缩小增量排序之塞奇威克增量序列 的源码实现
2为什么要求 塞奇威克增量序列 reason1要知道 塞奇威克 提出了几种增量序列最坏运行时间为 O(N^4/3)平均运行时间为 O(N^7/6) 其提出的增量序列中的最好序列是 {1, 5, 19, 41, 109, ......}该序列中的项或者是 9*4^i - 9*2^i 1 或者是 4^i - 3*2^i 1 reason2基于塞奇威克增量序列的希尔排序缩小增量排序 要 快于 花费 O(NlogN) 的 堆排序 3本文末会给出 基于 塞奇威克增量序列 的 希尔排序源码实现希尔排序的基础知识参见
http://blog.csdn.net/pacosonswjtu/article/details/49660799 【1】下面给出求塞奇威克增量序列 的 分析和源码实现
1分析 2源码如下 #include stdio.h
#include math.h
// 对增量序列赋值 和 找出所需要的最大轮数.
// 如 Rebort Sedgewick(罗伯特·塞奇威克) 提出的 increment 9*4^i - 9*2^i 1 或 increment 4^i - 3*2^i 1;
// incrementSeq[] 起点从 0 开始.
int incrementSeqFunc(int* incrementSeq, int length)
{ int i, startup1 0 , startup2 2;for(i0; ilength; i){if(i%20){incrementSeq[i] 9*pow(4, startup1) - 9*pow(2, startup1) 1;startup1;}else{incrementSeq[i] pow(4, startup2) - 3*pow(2, startup2) 1;startup2;}if(incrementSeq[i] length){break;}}return i; // 排序轮数每轮都使用比上一轮缩小的增量序列
}void printArray(int data[], int size)
{int i;for(i 0; i size; i)printf(%d , data[i]);printf(\n);
}
#include p167_shell_sort.hint main()
{ int incrementSeq[255]; int length 600;int round;round incrementSeqFunc(incrementSeq, length);printArray(incrementSeq, round);
} 3打印结果 【2】基于塞奇威克增量序列 的 希尔排序源码
Attentionyou can also checkout the source code from https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter7/review/p167_shell_sort void shell_sort(int* array, int length)
{ int incrementSeq[255]; // 增量序列(startup 0).int i, j, roundincrementSeqFunc(incrementSeq, length);int increment, temp;for(; round1; round--){increment incrementSeq[round-1];for(i1*increment; ilength; iincrement) // 默认地,array[0*increment]有序所以从1*increment开始.{temp array[i]; // 第1个无序成员.for(ji-increment; j0; j-increment) // j 在有序部分进行滑动.{if(temp array[j]){array[jincrement] array[j];}else{break;}}array[jincrement] temp;}}
}
#include p167_shell_sort.hint main()
{ int array[] {100, 1000, 100, 10, 6, 2, 19, 25, 15, 55, 35, 5, 110, 120, 119};int length 15; shell_sort(array, length);printArray(array, length);
}
