希尔排序增量序列的选法解决思路

希尔排序增量序列的选法

C/C++ code

#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感觉就是做了个循环移位

查看更多 下一篇