希尔排序

基本思想:

       先将整个待排序列分割为若干个子序列(不是“逐段分割”,而是将相隔某个“增量”的记录组成一个子序列),分别进行直接插入排序,这样重复几次(增量不断减小 一般是取前一次一半),待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。

        增量:把整个数据,分成几个小组,一般为素数。

图解:

代码实现:

void Shell(int arr[], int len, int dk)
{
	int i, j;
	int temp;
	for (i = dk; i < len; ++i)
	{
		temp = arr[i];
		for (j = i - dk; j >= 0 && arr[j] > temp; j -= dk)
		{
			arr[j + dk] = arr[j];
		}
		arr[j + dk] = temp;
	}
}

void ShellSort(int arr[], int arrlen, int dka[], int dkalen)//dka增量
{
	for (int i = 0; i < dkalen; ++i)
	{
		Shell(arr, arrlen, dka[i]);
	}
}
void show(int arr[], int len)
{
	for (int i = 0; i < len; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

int main()
{
	/*int arr1[300000];
	for (int i = 0; i < 200000; ++i)
	{
		arr1[i] = rand() % 100000;
	}*/

	int arr[] = {4,1,15,123,1,123,15,156,456,41,231,5,63,4};
	int arrlen = sizeof(arr) / sizeof(arr[0]);
	int dka[] = { 5,3,1 };
	int dkalen = sizeof(dka) / sizeof(dka[0]);
	ShellSort(arr, arrlen, dka, dkalen);
	show(arr, arrlen);
	return 0;
}

总结:

时间复杂度:平均O(n1.3),最好O(n),最坏O(n2)

空间复杂度:O(1)

不稳定的排序算法

原文链接:加载失败,请重新获取