- void ShellSort(int a[],int left,int right);
- // 对 a[left]到 a[right]从小到大排序
- void ShellSort(int a[],int left,int right)
- {
- int len = right - left +1;
- int gap,i,j,temp;
- //Shell 提出的增量选取规则 n/2,n/4,...,2,1
- for(gap=len/2;gap>0;gap/=2)
- for(i=left+gap;i<=right;i++)
- for(j=i-gap;j>=left && a[j]>a[j+gap];j-=gap){ //a[j]和 a[j+gap]为一个子序列
- temp = a[j]; /* 当 j-=gap 后的子序列 a[j],a[j+gap]已经处理则 */
- a[j] = a[j+gap]; /*j-=gap 仅是为了让其退出本次循环, 进而选取下一个子列 */
- a[j+gap] = temp;
- }
- }
- /* 算法分析:
- time-complexity: 与增量的选取有关, shell 选取增量规则时间复杂度为 O(n2),
- 帕佩尔诺夫 (Papernov) 和斯塔舍维奇 (Stasevich) 提出的 2 的 k 次方 + 1,...,65,33,17,9,5,3,1
- 其中 k 为大于等于 1 的整数, 2 的 k 次方 + 1 小于待排序列的长度, 此时时间复杂度为 O(n1.5 次方)
- space-complexity: O(1);
- 算法不稳定.
- */
来源: http://www.bubuko.com/infodetail-2566068.html