【数据结构入门】排序算法之三路划分与非比较排序

文章目录

前言

一、三路划分优化

1.1. 基本思想

1.2. 实现步骤

1.3. 优点

1.4 代码实现

二、非比较排序

2.1 计数排序

2.1.1基本思想

2.1.2具体步骤

2.1.3算法特性

2.1.4算法实现

2.2 基数排序

2.2.1基本思想

2.2.2具体步骤

2.2.3 基数排序的方法

2.2.4算法特性

2.2.5算法实现

 2.2.6 应用场景

三、算法复杂度及稳定性分析

总结

前言

前文(【数据结构入门】排序算法之交换排序与归并排序)提到了，快速排序在遇到数据大量重复的时候算法效率会极大的降低，这是由于分治思想不能很好的发挥他的作用，那么本篇博客会根据这种情况，介绍三路划分法优化快速排序，解决这个问题。

非比较排序是一类不依赖于元素间直接比较大小的排序算法。非比较排序算法主要包括计数排序、桶排序和基数排序等。下面将会介绍计数排序和基数排序。

一、三路划分优化

三路划分是一种在排序算法中常用的技术，特别是在处理包含大量重复数据的数组时，它可以显著提高排序效率。这种技术通过选择一个关键字（或称为基准值），然后将数组中的数据分为三部分：小于关键字的、等于关键字的和大于关键字的。

1.1. 基本思想

在快速排序的基础上，三路划分将数组分为三个部分，即小于基准值的部分、等于基准值的部分和大于基准值的部分。这样做的目的是减少递归排序的次数，特别是当数组中存在大量重复数据时，可以显著提高排序效率。

1.2. 实现步骤

1. 选择基准值：通常选择数组的第一个元素作为基准值，但也可以使用其他策略，如三数取中或随机数选取，以避免在某些特殊情况下（如数组已经有序）导致的性能退化。
2. 设置指针：设置三个指针，分别指向数组的起始位置（left）、当前处理位置（cur，初始值为left+1）和结束位置（right）。
3. 遍历数组：从cur开始遍历数组，根据当前元素与基准值的大小关系，执行以下操作：
   • 如果当前元素小于基准值，将其与left指向的元素交换，并将left和cur都向右移动一位。
   • 如果当前元素大于基准值，将其与right指向的元素交换，但只将right向左移动一位（因为交换过来的元素还需要与基准值比较）。
   • 如果当前元素等于基准值，只需将cur向右移动一位。
4. 递归排序：当cur大于right时，遍历结束。此时，数组被划分为三个部分，分别对小于基准值的部分和大于基准值的部分进行递归排序。注意，等于基准值的部分已经就位，无需再次排序。

伪代码整理：   

1.a[cur] < key , 交换left 和 cur 数据， left++, cur++;

2.a[cur] == key, cur++;

3.a[cur] > key, 交换cur 和 right数据， right++；

4.cur > right 结束

1.3. 优点

• 提高排序效率：特别是当数组中存在大量重复数据时，三路划分可以显著减少递归排序的次数，从而提高排序效率。
• 减少内存交换：通过减少不必要的元素交换，可以降低排序过程中的内存开销。

1.4 代码实现

void QuickSortPlus(int* a, int left, int right)
{
	//递归结束条件
	if (left >= right)
	{
		return;
	}
	//三数取中
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
	{
		Swap(&a[left], &a[midi]);
	}

	//记录begin, end 位置
	int begin = left;
	int cur = left + 1;
	int end = right;

	int key = a[begin];
	int keyi = begin;

	while (cur <= right)
	{
		if (a[cur] < key)
		{
			Swap(&a[left], &a[cur]);
			left++;
			cur++;
		}
		else if (a[cur] > key)
		{
			Swap(&a[cur], &a[right]);
			right--;
		}
		else //a[cur] == key
		{
			cur++;
		}
	}

	//小区间优化 -- 小区间使用插入排序
	//这个数字不能太大，否则没有意义
	if ((end - begin + 1) > 10)
	{
		//[begin, left-1] [left, right] [right+1, end]

		QuickSort(a, begin, left - 1);
		QuickSort(a, right+1, end);
	}
	else
	{
		InsertSort(a + left, right - left + 1);
	}
}

二、非比较排序

这类算法通过利用数据的某些特性或构建特定的数据结构来实现排序，通常具有较高的时间效率，在某些特定情况下甚至可以达到线性时间复杂度。

2.1 计数排序

计数排序（Counting Sort）是一种非比较型整数排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

2.1.1基本思想

对于每一个输入的元素x，确定小于x的元素个数，这样即可把x直接放到它在最终排序数组中的位置。

2.1.2具体步骤

1. 统计：统计数组中每个值为i的元素出现的次数，存入数组C的第i项。
2. 累加：累加数组C中的值，C[i]现在包含实际位置为i的元素的个数。

最后，反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1。

2.1.3算法特性

• 1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
• 2. 时间复杂度：O(MAX(N,范围))
• 3. 空间复杂度：O(范围)
• 4. 稳定性：稳定
• 5. 

2.1.4算法实现

void CountSort(int* a, int n)
{
	//找范围
	int min = a[0], max = a[0];

	for (int i = 0; i < n; ++i)
	{
		if (a[i] < min)
		{
			min = a[i];
		}
		if (a[i] > max)
		{
			max = a[i];
		}
	}

	int range = max - min + 1;
	int* countA = (int*)calloc(range, sizeof(int));//初始化为0
	if (countA == NULL)
	{
		perror("malloc fail");
		return;
	}

	//计数
	for (int i = 0; i < n; i++)
	{
		countA[a[i]-min]++;
	}
	// 排序
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (countA[i]--)
		{
			a[j++] = min + i;
		}
	}
	free(countA);
	return;
}

2.2 基数排序

基数排序（Radix Sort）是一种非比较型整数排序算法，它的工作原理是按照数字的每一位来分配和收集元素。这种排序方式通常用于排序数字（尽管它也可以用于排序其他类型的数据，比如字符串）。

2.2.1基本思想

将所有待比较的数字统一为相同的位数长度，位数较短的数字前面补零。然后，从最低位开始，依次进行一次分配和收集，直至排序完成。

2.2.2具体步骤

2.2.3 基数排序的方法

基数排序可以采用两种方法进行排序：

1. 最低位优先（Least Significant Digit first，简称LSD）法：先从最低位开始排序，再对更高位进行排序，依次重复，直到最高位排序完成。
2. 最高位优先（Most Significant Digit first，简称MSD）法：先按最高位排序分组，同一组中记录，关键码相等，再对各组按次高位排序分成子组，之后，对后面的位数继续这样的排序分组，直到最低位。再将各组连接起来，便得到一个有序序列

2.2.4算法特性

1. 稳定性：基数排序是一种稳定的排序算法，即具备相同值的元素，在排序后保持它们原有的相对顺序。
2. 时间复杂度：基数排序的时间复杂度是O(nk)，其中n是排序数组的长度，k是数字的最大位数。在某些情况下，其效率高于其他稳定性排序法。
3. 空间复杂度：由于需要额外的空间来创建“桶”，其空间复杂度大概是O(n+k)

2.2.5算法实现

根据排序时先进后出的特点，使用队列来辅助排序。

int GetKey(int value, int k)
{
	int key = 0;
	while (k >= 0)
	{
		key = value % 10;
		value /= 10;
		--k;
	}
	return key;
}

void Distribute(int* a, int left, int right, int k, Queue* Qu[10])
{
	for (int i = left; i <= right; ++i)
	{
		int key = GetKey(a[i], k);
		//入队 ,写错了
		QueuePush(Qu[key], a[i]);		
	}
}

void Collect(int* a, Queue* Qu[10])
{
	int k = 0;
	for (int i = 0; i < RADIX; i++)
	{
		while (!QueueEmpty(Qu[i]))
		{
			a[k++] = QueueFront(Qu[i]);
			QueuePop(Qu[i]);
		}
	}
}

//基数排序，先进先出用队列
void RadixSort(int* a, int left, int right)
{
	Queue q0, q1, q2, q3, q4, q5, q6, q7, q8, q9;
	//初始化
	QueueInit(&q0);
	QueueInit(&q1);
	QueueInit(&q2);
	QueueInit(&q3);
	QueueInit(&q4);
	QueueInit(&q5);
	QueueInit(&q6);
	QueueInit(&q7);
	QueueInit(&q8);
	QueueInit(&q9);
	//建数组
	Queue* Qu[10] = {&q0 ,&q1, &q2, &q3, &q4, &q5, &q6, &q7, &q8, &q9 };

	for (int i = 0; i < K; i++)
	{
		//分发数据
		Distribute(a, left, right, i, Qu);
		//回收数据
		Collect(a, Qu);
	}

	QueueDestory(&q0);
	QueueDestory(&q1);
	QueueDestory(&q2);
	QueueDestory(&q3);
	QueueDestory(&q4);
	QueueDestory(&q5);
	QueueDestory(&q6);
	QueueDestory(&q7);
	QueueDestory(&q8);
	QueueDestory(&q9);
}

 2.2.6 应用场景

基数排序最初被设计用于整数排序，因为它们具有易于定义位的特征（例如，个位、十位、百位等）。然而，基数排序也可以扩展用于任何可以被分成较小部分的数据类型，并且这些部分可以被独立排序。例如，字符串可以看作由字符组成的序列，可以对字符串集合使用基数排序，例如按字典顺序排列单词。此外，定长字符串（如电话号码、日期等）也可以通过每个字符的ASCII值进行排序。

三、算法复杂度及稳定性分析

总结

计数排序的优点在于它是稳定的排序算法，并且当输入的数据范围k不是很大时，它的时间复杂度为O(n+k)，其中n是数组的长度，k是输入的最大值。这使得它在某些特定情况下非常高效。然而，如果k很大，那么就需要大量的额外空间来存储计数数组。

总之，计数排序是一种在特定条件下非常高效的排序算法，但它并不适用于所有情况。

基数排序是一种高效的非比较型排序算法，特别适用于整数和字符串等可以分割成独立部分的数据类型。它通过按位分配和收集元素来实现排序，具有稳定性和较高的时间效率。然而，其性能也依赖于数据的分布和基数的选择。