C语言植物大战数据结构希尔排序算法

C语言植物大战数据结构希尔排序算法

什么是希尔排序

希尔排序是一种基于插入排序的排序算法，也叫做“缩小增量排序”。和插入排序不同的是，希尔排序的插入排序是对一定间隔的元素进行插入排序，而不是对数组中相邻的元素进行排序。

希尔排序的流程和方法

希尔排序的主要流程是根据元素间的间隔d，分组进行插入排序，依次减小d值。最后当d=1的时候，再按照插入排序的方法对整个数组进行一次排序。希尔排序的时间复杂度为O(n^(3/2))。

下面是代码块，演示希尔排序的方法实现：

void shellSort(int arr[], int n) 
{ 
    for (int gap = n / 2; gap > 0; gap /= 2) { 
        for (int i = gap; i < n; i += 1) { 
            int temp = arr[i]; 
            int j; 
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) 
                arr[j] = arr[j - gap]; 

            arr[j] = temp; 
        } 
    } 
} 

希尔排序的示例

下面用两个示例来进一步说明希尔排序的过程。

示例一：

假设待排序数组为：7 5 3 2 8 1 9 6 4

首先，将数列按照下标间隔d分成若干组，假设d=4，我们将数组拆分成下面这些分组：

7 8

5 1

3 9

2 6

4

然后对每个分组进行插入排序，插入排序之后数组变为：

4 1

5 6

3 8

2 9

7

然后将间隔缩小一半，假设d=2，我们将数组拆分成下面这些分组：

4 3 7

1 8

5 2 9

6

然后对每个分组进行插入排序，插入排序之后数组变为：

4 1 2

3 8 9

7 5 6

然后将间隔缩小为1，进行插入排序，最终得到排序后的数组：

1 2 3 4 5 6 7 8 9

示例二：

假设待排序数组为：66 34 33 45 24 23 12 10 7

首先，将数列按照下标间隔d分成若干组，假设d=5，我们将数组拆分成下面这些分组：

66 23

34 12

33 10

45 7

24

然后对每个分组进行插入排序，插入排序之后数组变为：

24 23

34 7

33 10

45 12

66

然后将间隔缩小一半，假设d=2，我们将数组拆分成下面这些分组：

24 33 66

23 12 34

7 10 45

然后对每个分组进行插入排序，插入排序之后数组变为：

7 10 34

23 12 45

24 33 66

然后将间隔缩小为1，进行插入排序，最终得到排序后的数组：

7 10 12 23 24 33 34 45 66

总结

希尔排序是一种比较简单的排序算法，其主要是通过对数组进行分组，然后对每个分组进行插入排序，最终在缩小间隔的过程中，使整个数组有序。希尔排序的时间复杂度是O(n^(3/2))，比起选择排序和冒泡排序等算法有较大的优越性。