Shell Sort

Brief book tutorial
https://www.jianshu.com/p/d730ae586cf3
Inside gap It's half every time , So finally we can achieve gap = 1, But if only gap = gap/2 Switch to gap = gap/3 You can't , such as gap = 2, Retake gap = gap/3, here gap = 0, Will stop sorting . The following code shows a method

Code ：

#include <stdio.h>

void InsertSort(int k[], int n)
{
    
	int i, j, temp;
	int gap = n;

	for(gap = gap/3 + 1;gap>=1;gap /=3)
	{
    
		for( i=gap; i < n; i++ )
		{
    
			if( k[i] < k[i-gap] )
			{
    
				temp = k[i];

				for( j=i-gap; k[j] > temp && j>=0 ; j-=gap )
				{
    
					k[j+gap] = k[j];
				}

				k[j+gap] = temp;
			}
		}
	}
}

int main()
{
    
	int i, a[10] = {
    5, 2, 6, 0, 3, 9, 1, 7, 4, 8};

	InsertSort(a, 10);

	printf(" The result of sorting is ：");
	for( i=0; i < 10; i++ )
	{
    
		printf("%d", a[i]);
	}
	printf("\n\n");

	return 0;
}