数据结构-归并排序与基数排序

目录

归并排序

概念

递归写法

非递归写法

归并性能

基数排序

概念

实现

基数性能 

---

归并排序

概念

   归并的含义是将两个或者两个以上已经有序的子序列合并成一个新的有序的序列。

   归并排序的基本思想是分治法，也就是先让子序列有序，再将子序列合并成有序的序列，类似二叉树的后序遍历。

   假设待排序的元素有n个，可以将这n个元素视为n个长度为一的子序列，然后两两归并，得到n/2个有序子序列。之后继续两两归并直到合并成长度为n的有序序列为止；上述这种两两归并的方法叫做二路归并排序。

递归写法

   归并排序的递归写法类似二叉树的后序遍历，先将划分好的子区间归并排序好，再将划分好的子区间进行二路归并。

   这里的归并是将元素归并到辅助数组中，待归并一趟完成之后需要将归并好的元素拷贝回原数组。 

void _MergeSort(SortData* a, int begin, int end, SortData* support)
{
	if (begin >= end)
	{
		return;
	}
 
	int mid = (begin + end) / 2;
	_MergeSort(a, begin, mid,support);
	_MergeSort(a, mid+1, end, support);
 
	int left1 = begin;
	int right1 = mid;
	int left2 = mid+1;
	int right2 = end;
 
	int i = begin;
 
	while (left1 <= right1 && left2 <= right2)
	{
		if (a[left1] < a[left2])
		{
			support[i++] = a[left1];
			left1++;
		}
		else
		{
			support[i++] = a[left2];
			left2++;
		}
	}
 
	while (left1 <= right1)
	{
		support[i++] = a[left1++];
	}
 
	while (left2 <= right2)
	{
		support[i++] = a[left2++];
	}
 
	memcpy(a + begin, support + begin, (end - begin + 1) * sizeof(SortData));
}

非递归写法

将子区间分成若干份，依次两两归并，每归并一次子区间长度变为原来两个子区间长度的和，子区间的数量减半。不过在此期间需要检查子区间的合法性，与递归写法一样需要等大的赋值数组。

// 1:
void MergeSortNonR(SortData* a, int n)
{
	SortData* support = (SortData*)malloc(sizeof(SortData) * n);
 
	if (support==NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
 
	int gap = 1;
	while (gap < n)
	{
		
		for (int i = 0; i < n; i += 2*gap)
		{
			int left1 = i;
			int right1 = i + gap - 1;
			int left2 = i + gap;
			int right2 = i + 2 * gap - 1;
 
			if (right1 >= n||left2>=n)
			{
				break;
			}
			else if (right2>=n)
			{
				right2 = n - 1;
			}
 
			int k = left1;
 
			int size = right2 - left1 + 1;
 
			while (left1 <= right1 && left2 <= right2)
			{
				if (a[left1] < a[left2])
				{
					support[k++] = a[left1++];
				}
				else
				{
					support[k++] = a[left2++];
				}
			}
 
			while (left1 <= right1)
			{
				support[k++] = a[left1++];
			}
 
			while (left2 <= right2)
			{
				support[k++] = a[left2++];
			}
 
			memcpy(a+i, support+i, size * sizeof(SortData));
		}
 
		gap *= 2;
	}
 
	free(support);
}
 
// 2:
void MergeSortNonR(SortData* a, int n)
{
	SortData* support = (SortData*)malloc(sizeof(SortData) * n);
 
	if (!support)
	{
		perror("malloc fail");
		return;
	}
 
	int gap = 1;
	while (gap < n)
	{
		
		for (int i = 0; i < n; i += 2*gap)
		{
			int left1 = i;
			int right1 = i + gap - 1;
			int left2 = i + gap;
			int right2 = i + 2 * gap - 1;
 
			if (right1 >= n)
			{
				right1 = n - 1;
 
				left2 = n;
				right2 = n - 1;
			}
			else if(left2>=n)
			{
				left2 = n;
				right2 = n - 1;
			}
			else if (right2>=0)
			{
				right2 = n - 1;
			}
 
			int k = left1;
 
			while (left1 <= right1 && left2 <= right2)
			{
				if (a[left1] < a[left2])
				{
					support[k++] = a[left1];
					left1++;
				}
				else
				{
					support[k++] = a[left2];
					left2++;
				}
			}
 
			while (left1 <= right1)
			{
				support[k++] = a[left1++];
			}
 
			while (left2 <= right2)
			{
				support[k++] = a[left2++];
			}
 
		}
 
		memcpy(a, support, n * sizeof(SortData));
 
		gap *= 2;
	}
 
	free(support);
}

归并性能

• 空间复杂度：O（N）
• 时间复杂度：O（N * log 2 N）
• 稳定性：稳定

基数排序

概念

   基数排序是一种很特别的排序，它不基于比较与移动进行排序，而是基于多个关键字的大小进行排序。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。

   为实现多关键字排序，通常有两种方法：第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD）法，按关键字权重递增依次进行排序，最后形成一个有序序列。

   在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为两类(①内部排序，是指在排序期间元素全部存放在内存中的排序；②外部排序，是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。

   一般情况下，内部排序算法在执行过程中都要进行两种操作：比较和移动。通过比较两个关键字的大小，确定对应元素的前后关系，然后通过移动元素以达到有序。当然，并非所有的内部排序算法都要基于比较操作，基数排序就不基于比较。（内部排序算法的性能取决于算法的时间复杂度和空间复杂度，而时间复杂度一般是由比较和移动的次数决定的。

实现

// 基数排序
#define K 3
#define RADIX 10
 
Queue Q[RADIX];
 
int GetKey(SortData data, int k)
{
	int key = 0;
	while (k>=0)
	{
		key = data % 10;
		data /= 10;
		k--;
	}
 
	return key;
}
 
void Distribute(SortData* a, int n, int k) // 分发
{
	for (int i = 0; i < n; i++)
	{
		QueuePush(&Q[GetKey(a[i], k)], a[i]);
	}
}
 
//void Collect(SortData* a) // 回收---升序
//{
//	int k = 0;
//
//	for (int i = 0; i < RADIX; i++)
//	{
//		while (!QueueEmpty(&Q[i]))
//		{
//			a[k++] = QueueFront(&Q[i]);
//			QueuePop(&Q[i]);
//		}
//	}
//}
 
void Collect(SortData* a) // 回收---降序
{
	int k = 0;
 
	for (int i = RADIX-1; i>=0; i--)
	{
		while (!QueueEmpty(&Q[i]))
		{
			a[k++] = QueueFront(&Q[i]);
			QueuePop(&Q[i]);
		}
	}
}
 
void RadixSort(SortData* a, int n)
{
	for (int i = 0; i < K; i++)
	{
		// 分发数据
		Distribute(a, n, i);
 
		// 回收数据
		Collect(a);
	}
}

 

基数性能

• 空间复杂度：O（N）
• 时间复杂度：O（N*M）N为分配与回收的，M为分配与回收的趟数也就是根据多少个关键字进行排序
• 稳定性：稳定