希尔排序也就是改进的插入排序

希尔排序首先就是找出一个间隔，在通过这个间隔来排序，依次往后加

比如间隔是4

第一次就排0,4,8,12,…

第二次就排1,5,9,13…

然后减小间隔，再重复上面的过程，最后一定会有一次间隔为1的时候。

  • 优点

    • 在间隔大的时候，排序次数少
    • 在间隔小的时候，排序距离近
    • 比普通插入效率高，但是不稳定。

大体中间内容就是选择排序，不过下标不在是i

而是gap【间隔】

这里就面临着间隔如何选择的问题

  • 二分，一半的一半的一半

  • Knuth序列

    • h=1，最后一次间隔为1
    • h=3*h+1，每运行一次就是一个新的间隔

找到最大的h然后依次递减，一直到1

最后我写copy的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<stdio.h>

//用于打印的函数
void print(int arr[],int size) {

	int i;
	/*printf("原始数组：");
	for (i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");*/


	printf("排序后数组：");
	for (i = 0; i < size; i++)
		printf("%d ,", arr[i]);
	printf("\n");
}

//用于交换的函数
void exchange(int a[], int i, int j)
//a是要交换的数组，i和j是要进行交换的位置
{
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}


//建立一个希尔排序的算法函数
void XiEr(int arr[], int size) {
	//arr[]是要排序的数组，size是该数组的长度
	
	//首先要用Knuth序列计算初始间隔值 用h来表示
	int h = 1;
	while (h < size / 3) {
		h = 3 * h + 1;//找到最大的间距。然后依次递减，最后递减到等于1
	}

	for (; h > 0; h=(h-1) / 3) {
		for (int i = h; i < size; i++) {
			for (int j = i; j > h; j-=h) {
				if (arr[j] < arr[j - h]) {
					exchange(arr, j, j - h);
				}
			}
		}
	}

}


//主函数

int main() {

	int arr[] = { 1,2,5,3,6,9,7,4,8,5,2,3,6,9,4,1,2,5,8,6,3,6,7,4,2,5,8,4 };
	int size = sizeof(arr) / sizeof(arr[0]);
	
	XiEr(arr, size);
	print(arr, size);


}

下面这个是用chatGPT写的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>

// 希尔排序函数
void shellSort(int array[], int size) {
    int gap, i, j, temp;

    // 使用Knuth序列计算初始间隔值
    gap = 1;
    while (gap < size / 3)
        gap = 3 * gap + 1;

    while (gap > 0) {
        // 使用插入排序对每个子数组进行排序
        for (i = gap; i < size; i++) {
            temp = array[i];
            j = i;

            while (j >= gap && array[j - gap] > temp) {
                array[j] = array[j - gap];
                j -= gap;
            }

            array[j] = temp;
        }

        // 缩小间隔值
        gap /= 3;
    }
}

// 测试代码
int main() {
    int array[] = {64, 25, 12, 22, 11};
    int size = sizeof(array) / sizeof(array[0]);
    int i;

    printf("原始数组：");
    for (i = 0; i < size; i++)
        printf("%d ", array[i]);
    printf("\n");

    shellSort(array, size);

    printf("排序后数组：");
    for (i = 0; i < size; i++)
        printf("%d ", array[i]);
    printf("\n");

    return 0;
}