计数排序&&归并排序(递归版本&&非递归版本)

发布时间:2024年01月17日

1.计数排序

????????计数排序是一种非比较排序算法,其核心思想是通过统计每个元素出现的次数,然后根据统计结果将元素按照顺序放置在输出数组中。

以下是计数排序的逻辑思想(C语言版):

1. 首先,遍历待排序的数组,找到数组中的最大值max,确定计数数组的大小为max+1。

2. 创建一个大小为max+1的计数数组count,并初始化为0。

3. 遍历待排序的数组,将每个元素的值作为计数数组count的索引,并将对应索引位置的值

加1,表示该元素出现的次数。

4. 对计数数组count进行累加操作,使得每个索引位置的值表示小于等于该索引的元素个数。

5. 统计完次数之后就往原数组内覆盖回写

????????计数排序是一种就地排序算法,这意味着它不需要任何额外的空间来对数据进行排序。它也是一个稳定的排序算法,这意味着输入中相等元素的顺序在输出中得以保留。

????????计数排序是一种十分高效的排序,时间复杂度为O(n + k),其中n是列表中元素的数量,k是列表中任何元素的最大值。计数排序的空间复杂度为O(k)。

? ? ? ? 计数排序是不适合分散的数据,更适合集中的数据;不适合浮点数,字符串,结构体数据排序,只适合整数。

eg:如果有一组数据是从1000开始的连续的数据,那么是不是就意味着前面1000个空间就浪费了,如何解决?

? ? ? ? 我是数据是多少就映射到哪个位置上,这种映射叫做绝对映射,这可能会导致大量空间的浪费,大多情况下我们都是使用相对映射的方法。(相对最小值)我们在使用计数排序前,可以先找到改组数据的最小值和最大值,这就是该组数据的范围,这样就可以有效的节省空间了。

代码:

// 计数排序
// 时间:O(N+range)
// 空间:O(range)
void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
    //确定范围
	for (int i = 1; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];

		if (a[i] > max)
			max = a[i];
	}

	int range = max - min + 1;
	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
	{
		printf("calloc fail\n");
		return;
	}

	// 统计次数
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;//使得下标从0开始
	}

	// 排序
	int i = 0;
	for (int j = 0; j < range; j++)
	{
		while (count[j]--)
		{
			a[i++] = j + min;//回到原数组范围
		}
	}
}

2.归并排序?

递归版本
基本思想:
归并排序( MERGE-SORT )是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法( Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并排序核心步骤:

它将待排序的数组递归地分成两个子数组,然后对这两个子数组分别进行排序,最后将两个有序的子数组合并成一个有序的数组。

递归版本的归并排序的具体步骤如下:

1. 将待排序的数组分成两个子数组,每个子数组的大小为 n/2。

2. 对这两个子数组分别进行递归排序。

3. 将两个有序的子数组合并成一个有序的数组。

合并两个有序的子数组可以通过以下步骤实现:

1. 创建一个新的数组,用于存储合并后的结果。

2. 将两个子数组中的元素依次比较,将较小的元素放入新的数组中。

3. 重复步骤 2,直到两个子数组中的所有元素都被放入新的数组中。

下面是归并排序的递归版本的算法步骤:

1. **分解**:将待排序的数组分成两个子数组,通过计算数组的中间位置来实现。可以使用递归将左右两个子数组继续分解,直到子数组的大小为1。

2. **排序**:对分解得到的子数组进行排序,可以通过递归调用归并排序函数来实现。

3. **合并**:将排序好的两个子数组合并成一个有序的数组。比较两个子数组的第一个元素,将较小的元素放入结果数组中,并将相应子数组的指针向后移动,重复这个过程直到其中一个子数组为空,然后将另一个子数组中剩余的元素直接放入结果数组中。

递归版本的归并排序的关键在于递归地将数组分解为较小的子数组,并在合并阶段将它们逐步合并成一个有序的数组。这个过程会一直递归下去,直到子数组的大小为1,即只有一个元素,此时可以认为它已经是有序的。

下面归并排序递归版本的实现代码:

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;

	int mid = (begin + end) / 2;
	// [begin, mid][mid+1, end]
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid+1, end, tmp);

	// [begin, mid][mid+1, end]归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}

	while(begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}

	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
}

非递归版本

递归的思想是把数组分到一个数据认为它有序,然后才开始归并。非递归的思想就是可以一开始就是认为单个数据有序,开分组归并。

这里我们引出gap变量,gap表示每组的数据个数

我们还是通过划分区间的方法来理清逻辑,[begin1,end1] [begin2,end2]两组一归并。

end1为什么是i+gap-1?因为我们访问的是下标,所有我们要减去1

int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;

该如何控制gap?

gap的变化趋势是每次扩大2倍,gap*=2。只要gap<n,那么循环就继续。

该怎么去控制归并循环?

首先i+=2*gap,因为每次要跳过两组数据,那么i的结束条件就可以是i<n


注意:没归并完一组就将这组的数据拷贝回原数组,而不是将所有组归并完后,再将整个数组拷贝回原数组。(稍后解释原因)。

初步代码:

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	int gap = 1;
	while (gap < n)
	{
		
		for (int i= 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			int j = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}

			memcpy(a + i, tmp + i, sizeof(int) * 2*gap);
		}

		printf("\n");

		gap *= 2;
	}


	free(tmp);
}
int main()
{
	int a[8] = { 8,7,6,5,4,3,2,1 };
	MergeSortNonR(a, 8);
	for (int i = 0; i < 8; i++)
	{
		printf("%d ", a[i] );
	}
}

运行结果:

但我们的数组个数不是2^n时,排序就出现错误了,这是为什么呢?

我们通过打印每组gap的分组情况发现gap为2,4,8时,都出现了越界情况,我们并没有那么多数据,因为我们都是按整数倍去算的,每次都会为我你们补齐,如何解决?

我们先看begin1,begin1是i,它不可能越界,其它的都可能越界。

如果end1越界, 那么证明后面就没有数据,就不需要越界了,接直接break。

如果begin2越界了,end2,那也可以证明后面没有数据了,直接break。

如果end2越界了,那么证明前面都是好的,end2是补齐到了整数倍所以导致越界了,那么只要将end2修正到n就好了。

这里的拷贝也是要进行修改的,因为拷贝也是按照整数倍去拷贝的,要改成(end2-i+1)左闭右闭,减完后要加1。

修改后的代码:

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	int gap = 1;
	while (gap < n)
	{
		//printf("gap:%2d->", gap);
		for (size_t i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			// [begin1, end1][begin2, end2] 归并
			//printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2);

			// 边界的处理
			if (end1 >= n || begin2 >= n)
			{
				break;
			}

			if (end2 >= n)
			{
				end2 = n - 1;
			}

			//printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2);

			int j = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}

			memcpy(a + i, tmp + i, sizeof(int) * (end2-i+1));
		}

		printf("\n");

		gap *= 2;
	}


	free(tmp);
}

运行结果:

填前面的坑:为什么要归并一组拷贝一组,而不是等拷贝完了,拷贝整个数组?

因为会出现越界的情况,当遇到越界的情况,因为只有一组已经是有序的了,直接break就好了,就不需要进入tmp数组了,如果break了,却又整组的进行迭代数据,那么在最后一组的位置进入tmp数组就有可能出现随机值,再拷贝回原数组那么就会把最后一组正确的数据给覆盖掉了。

文章来源:https://blog.csdn.net/2301_76618602/article/details/135621344
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。