希尔排序实验报告

三、实验内容与要求

希尔排序是对直接插入排序的改进，提高了排序效率。

1、在参考程序中，对希尔排序的短发进行了简化，每次增量有gap=n/2得到，而并不一定满足除1之外的公因子条件。

Shell排序算法基本思想是：

2、设待排序元诩个数为n，第一增量取gap个组，在各组内进行直接插入排序，然后再取gap=gap/2作为第二增量，重复上述分组和排序工作，直至gap=1，即所有记录放在同一组中进行直接插入排序为止。

四、实验步骤

1、算法思路：先取一个正整数d1（d1＜n），把全部记录分成d1个组，所有距离为dl的倍数的记录看成是一组，然后在各组内进行插入排序；接着取d2（d2＜d1），重复上述分组和排序操作；直到di=1 (i＞＝1)，即所有记录成为一个组为止。希尔排序对增量序列的选择没有严格规定，一般选d1约为n／2，d2为d1／2，d3为d2／2，…，di＝1。

2、代码编程实现

五、实验代码

为更好地理解排序的过程，.这里我用了几个标准输出的语句，将数据交换的过程进行一个输出。

其中shellsort为原函数，而traceShellsort则为输出结果的函数

#include

#include

#define ARRAY_LENGTH 9

void shellsort(int v[], int n);

void arrayPrintf(int v[], int n);

void traceShellsort(int v[], int n);

int traceOut(int n, int gap, int i, int j, int isnewline);

int traceCount;

int main(void)

{

int arr[ARRAY_LENGTH] = { 12, 2, 20, 19, 28, 30, 12, 42, 35 };

printf("数组输出:tt");

arrayPrintf(arr, ARRAY_LENGTH);

/*sort the array by shell arithmetic*/

//shellsort(arr, ARRAY_LENGTH);

traceShellsort(arr, ARRAY_LENGTH);

putchar('n');

printf("交换显示数组:tt");

arrayPrintf(arr, ARRAY_LENGTH);

return EXIT_SUCCESS;

}

/*shellsort函数：按递增顺序对v[0]…v[n-1]进行排序*/

void shellsort(int v[], int n)

{

int gap, i, j, temp;

for (gap = n / 2; gap > 0; gap /= 2)

{

for (i = gap; i < n; i++)

{

for (j = i - gap; j >= 0 && v[j] > v[j + gap]; j -= gap)

{

temp = v[j];

v[j] = v[j + gap];

v[j + gap] = temp;

}

}

}

}

/*显示输出*/

void traceShellsort(int v[], int n)

{

int gap, i, j, temp;

//extern int traceCount;

traceCount = 1;

for (gap = n / 2; gap > 0; gap /= 2)

{

for (i = gap; i < n; i++)

{

for (j = i - gap; traceOut(n, gap, i, j, !(j >= 0 && v[j] > v[j

+ gap])) && j >= 0 && v[j] > v[j + gap]; j -= gap)

{

temp = v[j];

v[j] = v[j + gap];

v[j + gap] = temp;

arrayPrintf(v, n);

}

}

}

}

/*用于显示交换过程*/

int traceOut(int n, int gap, int i, int j, int isnewline)

{

printf("%2d. n=%d gap=%d i=%d j=%2d %c", traceCount++, n, gap, i, j,

isnewline ? 'n' : ' ');

return 1;

}

/*用于输出一组数组*/

void arrayPrintf(int v[], int n)

{

int i;

for (i = 0; i < n; i++)

{

printf("%d ", v[i]);

}

putchar('n');

}

五、实验记录

数组输出: 12 2 20 19 28 30 12 42 35

1. n=9 gap=4 i=4 j=0 2. n=9 gap=4 i=5 j=1 3. n=9 gap=4 i=6 j=2

12 2 12 19 28 30 20 42 35

4. n=9 gap=4 i=6 j=-2 5. n=9 gap=4 i=7 j=3 6. n=9 gap=4 i=8 j=4

7. n=9 gap=2 i=2 j=0 8. n=9 gap=2 i=3 j=1 9. n=9 gap=2 i=4 j=2

10. n=9 gap=2 i=5 j=3 11. n=9 gap=2 i=6 j=4

12 2 12 19 20 30 28 42 35

12. n=9 gap=2 i=6 j=2 13. n=9 gap=2 i=7 j=5 14. n=9 gap=2 i=8 j=6

15. n=9 gap=1 i=1 j=0

2 12 12 19 20 30 28 42 35

16. n=9 gap=1 i=1 j=-1 17. n=9 gap=1 i=2 j=1 18. n=9 gap=1 i=3 j=2

19. n=9 gap=1 i=4 j=3 20. n=9 gap=1 i=5 j=4 21. n=9 gap=1 i=6 j=5

2 12 12 19 20 28 30 42 35

22. n=9 gap=1 i=6 j=4 23. n=9 gap=1 i=7 j=6 24. n=9 gap=1 i=8 j=7

2 12 12 19 20 28 30 35 42

25. n=9 gap=1 i=8 j=6

交换显示数组: 2 12 12 19 20 28 30 35 42

六、实验体会

通过过这次实验使我懂得了理论与实际相结合 是很重要的，只有理论知识是远远不够的， 是很重要的，只有理论知识是远远不够的，只有把所 学的理论知识与实践相结合起来， 从理论中得出结论， 学的理论知识与实践相结合起来，

从理论中得出结论，才能真正提高自己的实际动手能力和独立思考的能力。同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，也得到新的理解。