C语言希尔排序算法实现

jack1007

之前纠结半天，还是分开写好理解多了，先写直接插入排序函数，再用插入排序函数进行希尔分组排序。

1. #include <stdio.h>
   
2. 
   
3. void swap(int *a, int *b);
   
4. void print_arr(int *arr, int arr_len);
   
5. void shellsort(int *arr, int arr_len);
   
6. void insertion_sort(int *int_arr, int div_len, int arr_len);
   
7. 
   
8. int
   
9. main()
   
10. {
    
11.   int arr[] = {99, 56, 48, 93, 25, 32, 49, 88, 12, 74, 22, 62};
    
12.   int arr_len = sizeof(arr) / sizeof(arr[0]);
    
13.   print_arr(arr, arr_len);
    
14. 
    
15.   shellsort(arr, arr_len);
    
16.   print_arr(arr, arr_len);
    
17. 
    
18.   return 0;
    
19. }
    
20. 
    
21. void
    
22. insertion_sort(int *arr, int div_len, int arr_len)
    
23. {
    
24.   int i, j;
    
25.   for (i = div_len; i < arr_len; i+=div_len) {
    
26.     for (j = i; arr[j] < arr[j - div_len] && j > 0; j-=div_len) {
    
27.       swap(&arr[j - div_len], &arr[j]);
    
28.       }
    
29.     }
    
30. }
    
31. 
    
32. void
    
33. shellsort(int *arr, int arr_len)
    
34. {
    
35.   int div = arr_len / 2;
    
36.   while (div > 0) {
    
37.     insertion_sort(arr, div, arr_len);
    
38.     div = div / 2;
    
39.   }
    
40. }
    
41. 
    
42. void
    
43. swap(int *a, int *b)
    
44. {
    
45.   int tmp;
    
46.   tmp = *a;
    
47.   *a = *b;
    
48.   *b = tmp;
    
49. }
    
50. 
    
51. void
    
52. print_arr(int *arr, int arr_len)
    
53. {
    
54.   int i = 0;
    
55.   while (i < arr_len) {
    
56.     printf("%d ", arr[i]);
    
57.     i++;
    
58.   }
    
59.   printf("\n");
    
60. }

复制代码

lxyscls_cu

div = arr_len / 2;

你这种步进长度是很差的一种步进长度

其实希尔排序的很关键的部分就在于选择一种好的步进长度{:3_204:}

linux_c_py_php

反正最后一轮步长=1等于插入排序, 前面的步长随意了.