希尔排序及C语言实现
分类:
文章
•
2022-10-28 14:11:38
- #include <stdio.h>
-
- void shell_sort(int arr[], int size)
- {
- if (arr == NULL)
- return ;
- int h = 1; /* 关于步长,取值没有统一标准,必须小于size,最后一次步长要为1 */
-
- /* 计算首次步长 */
- while (h < size/3)
- h = 3*h + 1;
-
- int i, j, temp;
- while (h >= 1) {
- for (i = h; i < size; ++i) {
- /* 将a[i]插入到a[i-h]、a[i-2h]、a[i-3h]...中 */
- for (j = i; j >= h && (arr[j] < arr[j-h]); j -= h) {
- temp = arr[j];
- arr[j] = arr[j-h];
- arr[j-h] = temp;
- }
- }
-
- /* 每轮内循环后输出数组的现状 */
- int k;
- printf("the step=%d : ", h);
- for (k = 0; k < size; ++k) {
- printf("%d ", arr[k]);
- }
- printf("\n");
-
- /* 计算下一轮步长 */
- h = h / 3;
- }
-
- }
-
- int main()
- {
- int arr[] = {6, 5, 3, 1, 8, 7, 2, 4, 9, 0};
- int size = sizeof(arr) / sizeof(int);
-
- //sort
- shell_sort(arr, size);
-
- //print
- int i = 0;
- for (i; i < size; ++i) {
- printf("%d\n", arr[i]);
- }
-
- return 0;
- }