希尔排序和选择排序及计数排序的简单介绍

发布于:2025-07-13 ⋅ 阅读:(12) ⋅ 点赞:(0)

希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数gap,把待排序文件中所有数据分成几个组,所有距离为gap的数据分在同一组内,并对每一组内的数据进行排序。然后gap减减,重复上述分组和排序的工作。当到达gap=1时,所有数据在同一组内排好序(gap==1时就是上次讲的插入排序)。

希尔排序举例:

#include <stdio.h>
// 打印
void Printarry(int* arr, int n)
{
	assert(arr);
	for (int i = 0;i < n;i++)
	{
		printf("%d ", arr[i]);

	}
	printf("\n");
}
// 希尔排序
// 时间复杂度 O(N^1.3-N^2)
// gap越大,前面大的数据可以越快排到后面,后面小的数可以越快拍到前面,gap越大,越不接近有序
// gap越小越接近有序,如果gap==1其实就是直接插入排序,就有序了
void ShellSort(int* arr, int n)
{
	assert(arr);
	int gap = n;

	// gap>1相当于预排序,让数组接近有序
	// gap==1就相当于直接插入排序,保证有序
	while (gap > 1)
	{
		gap = gap / 3 + 1; // +1是保证了最后一次gap一定是1

		// 注意结束条件,防止造成越界访问(画图)
		for (int i = 0;i < n - gap;i++)  // 多趟并排
		{
            // 单趟排序
			int end = i;               // 当end==0时就是单趟排序,排间距为gap的那一趟
			int temp = arr[end + gap];  // 将新的排序数值存起来,方便每次比较大小
			while (end >= 0)   
			{
				if (temp < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = temp;  // 跳出循环后temp放到end+gap位置
		}

		// 打印每一个gap时的排序状态
		Printarry(arr, n);
	}
	
}

void TestShellSort() 
{
	int arr[] = { 3,1,4,2,8,4,9,6,0,7 };
	Printarry(arr, sizeof(arr) / sizeof(arr[0]));
 
	ShellSort(arr, sizeof(arr) / sizeof(arr[0]));
	Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}
 
int main()
{
	TestShellSort();
 
	return 0;
}

选择排序

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置(末尾位置),直到全部待排序的 数据元素排完 。

直接选择排序:

在元素集合arr[i]--arr[n-1]中选择最大(小)的数据 若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换 在剩余的array[i]--array[n-2](array[i+1]--array[n-1])集合中,重复上述步骤,直到集合剩余1个元素。

举例:利用双指方法,begin指向首元素,end指向末尾元素,找到最大值时maxi和end位置数据互换,最小值mini位置和begin位置数据互换。

当begin和maxi重叠时,mini位置的数据和begin位置的数据互换后要将mini的值给到maxi,在将maxi位置的数据和end位置的数据互换。

#include <stdio.h>
// 打印
void Printarry(int* arr, int n)
{
	assert(arr);
	for (int i = 0;i < n;i++)
	{
		printf("%d ", arr[i]);

	}
	printf("\n");
}
// 选择排序
// 空间复杂度为O(1)
// 时间复杂度为 O(N^2),最好的情况是接近有序比较n次即可,最坏的是不完全有序接近无顺序
void SelectSort(int* arr, int n)
{
	assert(arr);
	int begin = 0;
	int end = n - 1;
	//int mini = 0;
	//int maxi = 0;

	while (begin < end)
	{
		int mini = 0;
		int maxi = 0;
		maxi = mini = begin;
		// 在[begin,end]之间选出最大值和最小值
		for (int i = begin + 1;i <= end;++i)
		{
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}

			if (arr[i] < arr[mini])
			{
				mini = i;
			}
		}
		Swap(&arr[begin], &arr[mini]);

		// 如果maxi与begin位置重叠的话要修正maxi的位置
		if (begin == maxi)
			maxi = mini;
		Swap(&arr[end], &arr[maxi]);
		--end;
		++begin;
	}
}

void TestSelectSort()
{
	int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };
	SelectSort(arr, sizeof(arr) / sizeof(arr[0]));
	Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}
int main()
{
	TestShellSort();
 
	return 0;
}

计数排序

首先找到待排序数组的最大值和最小值,然后开辟一个空间temp数组,大小为最大值减去最小值加1;然后遍历数组,将数据出现的次数放到temp数组相对位置中;然后再遍历temp数组取出对应数据出现的次数,将该数据依次覆盖回原数组中。

注意:这个排序缺点就是浪费空间比如,待排序数组最小值为100,最大值为1000;那么要开辟0-1000个空间的数组,才能存放比如100出现10次,那么temp数组中下标100位置就存放10,这样就很浪费空间。我们在这里开辟900个空间的数组,将100出现的次数放到相对位置中,相对位置为:100-min。覆盖回原数组的时候再加上min即可。相对减少空间浪费。

举例子:

#include <stdio.h>
// 打印
void Printarry(int* arr, int n)
{
	assert(arr);
	for (int i = 0;i < n;i++)
	{
		printf("%d ", arr[i]);

	}
	printf("\n");
}
// 计数排序
// 时间复杂度O(N+range)
// 空间复杂度O(range)
void CountSort(int* arr, int n)
{
	// 找出最大最小值
	int min = arr[0];
	int max = arr[0];
	for (int i = 1;i < n;i++)
	{
		if (arr[i] > max)
			max = arr[i];
		if (arr[i] < min)
			min = arr[i];
	}
	// 创建计数的空间
	int range = max - min + 1;
	int* countArr = (int*)malloc(sizeof(int) * range);

	memset(countArr, 0, sizeof(int) * range); // 将数组元素置为0

	// 遍历数组将相同的数值出现的次数放到相对位置处:arr[i] - min
	for (int i = 0;i < n;i++)
	{
		countArr[arr[i] - min]++;
	}
	// 遍历countArr数组将某个数出现的次数,依次将这个数放回到原数组
	int index = 0;
	for (int i = 0;i < range;i++)
	{
		while (countArr[i]--)  // 控制数据出现的次数
		{
			arr[index++] = i + min;
		}
	}
}

void TestCountSort()
{
	int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };
	CountSort(arr, sizeof(arr) / sizeof(arr[0]));
	Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}
int main()
{
	TestCountSort();
 
	return 0;
}


网站公告

今日签到

点亮在社区的每一天
去签到