MyException - 我的异常网
当前位置:我的异常网» C语言 » 希尔排序增量序列的选法,该怎么处理

希尔排序增量序列的选法,该怎么处理

www.MyException.Cn  网友分享于:2013-02-18  浏览:20次
希尔排序增量序列的选法

#include "stdafx.h"
#include <iostream>
using namespace std;

/*
**功能:通过希尔排序非递减排一个数组
**参数:A指向数组首元素的指针,数组元素的个数n, 希尔排序的增量dk
**返回值:无返回值
*/
void ShellInsert(int *A, int n, int dk)
{
int temp = 0;
int j;
for (int i = 0; i + dk < n; ++i)
{
if (A[i] > A[i+dk])
{
temp = A[i];
for ( j = i; (j + dk < n) && (j < n); j += dk)
{
A[j] = A[j + dk];
}

A[j] = temp;
}
}

}
//dlta指向增量序列的首元素
void ShellSort(int *A, int n, int *dlta, int t)
{
for (int k = 0; k < t; ++k)
ShellInsert(A, n, dlta[k]);
return;
}

int _tmain(int argc, _TCHAR* argv[])
{
int a[10] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
int dlta[5] = { 9,5, 3, 2, 1};
ShellSort(a, 10, dlta, 4);
for (int i = 0; i < 10; ++i)
cout << a[i] << endl;
return 0;
}

若增量序列{ 9,5, 3, 2, 1}; 结果为 (4,27,13,38,49,49,55,65,97,76)
若增量序列{ 5, 3, 2, 1}; 结果为(4,27,38,49,49,65,76,13,55,97)
我也单步调试了,写的算法没错!但是如果再让它经过几次调整的话会成功的。
可是这种增量序列最大只能取到9,。
我想问一下有什么别的增量序列可以让它正确的排出来?



------解决方案--------------------
理论上希尔排序的时间复杂度是小于其他的插入排序的,只是所取的“增量”序列是未定的,是一个复杂的数学难题。
------解决方案--------------------
算法错了吧,最终只要增量为1的话,是一定可以排出来的。

对于每一个增量,你都要做一个完整排序的,你的算法貌似没有。你的ShellInsert中第二个for感觉就是做了个循环移位

文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有