数据结构(C语言)希尔排序

希尔排序:直接插入排序越有序越快的特点是希尔排序的一个理论基础
算法描述:间隔式分组,利用直接插入排序,缩小分组再排序,直到缩为一组
不稳定:因为有跳跃式的交换数据
时间复杂度O(n1.3~n1.5)

#include<stdio.h>
//一趟希尔排序
void Shell(int *arr,int len,int gap)
{
	int i, j;
	for (i = gap; i < len; i++)//是i++
	{
		int a = arr[i];
		for (j = i-gap; j >= 0; j-=gap)
		{
			if (arr[j] > a)
			{
				arr[j + gap] = arr[j];
			}
			else
			{
				break;
			}
		}
		arr[j + gap] = a;
	}
}

void ShellSort(int* arr, int len)
{
	int d[] = { 5,3,1 };
	for (int i = 0; i < sizeof(d) / sizeof(d[0]); i++)
	{
		Shell(arr, len, d[i]);
	}
}
int main()
{
	int arr[] = { 5,2,6,9,8,7,5,6,2,1,0,1,2,3,6,5,4 };
	ShellSort(arr, sizeof(arr) / sizeof(arr[0]));
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
		printf("%d  ", arr[i]);
	//0  1  1  2  2  2  3  4  5  5  5  6  6  6  7  8  9
}
上一篇:题解 UVA103 Stacking Boxes


下一篇:数组