[数据结构] 万字解析排序算法

2024-08-09 13:21:16 浏览数 (1)
快速排序

快速排序（Quick Sort）是一种高效的排序算法，它利用分治法将一个数组分成两个子数组，然后递归地对这两个子数组进行排序。在快速排序的每一趟排序中，核心步骤是单趟循环，这一步骤将数组分成两分，一部分的所有元素都小于等于一个特定的“基准值”（pivot），另一部分的所有元素都大于基准值。

双指针法

快速排序逻辑如下GIF：

由此可得，快速排序的单次逻辑代码实现为：

代码语言：javascript复制
if (left >= right)
	{
		return;
	}

	int keyi = left;
	int begin = left;
	int end = right;

	while (begin < end)
	{
		// 左边找大
		// a[end] >= a[keyi] 防止两个位置相同时一直交换，陷入无限循环
		while (begin < end && a[end] >= a[keyi])
		{
			--end;
		}

		// 右边找小
		while (begin < end && a[begin] <= a[keyi])
		{
			  begin;
		}

		/*if (begin < end)
		{
			Swap(&a[begin], &a[end]);
		}*/

		Swap(&a[begin], &a[end]);

	}

	Swap(&a[keyi], &a[begin]);

设置最左边为keyi，开始从左边向右找比keyi大的数据，从右边向左找比keyi小的数据，执行逻辑：右边先进行向左查找小数据，找到后停留在小数据位置，左边再向右查找大数据，找到后停留。交换找到的两个位置的数据，继续循环查找然后交换。当两个指针指向位置相同时将相遇位置与keyi位置交换（此时的相遇位置一定是比keyi小的数据）。

通过分治的思想来进行分组排序。在单趟排序后keyi作为中间值换到了两个指针上一轮相遇位置，从keyi位置二分数组，将两个数组的最左边元素设置为keyi，继续进行循环，继续分治，如此最后即达到了整体顺序的目的。

整体排序过程整理
选择基准值（Pivot）

快速排序的第一步是从数组中选择一个基准值（pivot）。基准值的选择可以有多种策略，例如选择第一个元素、最后一个元素、中间的元素，或者随机选择。基准值的选择会影响算法的性能，但不会影响其正确性。

单趟划分（Partitioning）

在单趟划分过程中，数组中的元素被重新排序，使得基准值左边的所有元素都小于等于基准值，右边的所有元素都大于等于基准值。这个过程可以描述如下：

  1. 初始化指针：设定两个指针 begin 和 end，分别从数组的两端开始。
  2. 寻找逆序对：从右向左移动 end 指针，直到找到一个小于基准值的元素；从左向右移动 begin 指针，直到找到一个大于基准值的元素。
  3. 交换元素：交换这两个指针指向的元素。
  4. 重复：重复上述过程，直到 begin 和 end 相遇。

此时，基准值应插入到数组中间某个位置，使得其左边的元素全都小于等于它，右边的元素全都大于等于它。

递归分治（Divide and Conquer）

单趟划分完成后，基准值被放置到其最终位置，且数组被分为两部分。然后，对这两部分递归地进行快速排序：

  1. 对左部分排序：对基准值左边的子数组递归调用快速排序。
  2. 对右部分排序：对基准值右边的子数组递归调用快速排序。

递归的终止条件是子数组的大小为零或一，即 left >= right。

终止条件

递归过程最终会将所有子数组排序完成，此时整个数组已经排序完成。

合并

快速排序本质上不需要显式的合并步骤，因为在递归的每个步骤中，基准值的左右子数组已经各自有序，整个数组的排序结果自然也就完成了。

整体代码实现
代码语言：javascript复制
 // 简单快排
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int keyi = left;
	int begin = left;
	int end = right;

	while (begin < end)
	{
		// 左边找大
		// a[end] >= a[keyi] 防止两个位置相同时一直交换，陷入无限循环
		while (begin < end && a[end] >= a[keyi])
		{
			--end;
		}

		// 右边找小
		while (begin < end && a[begin] <= a[keyi])
		{
			  begin;
		}

		/*if (begin < end)
		{
			Swap(&a[begin], &a[end]);
		}*/

		Swap(&a[begin], &a[end]);

	}

	Swap(&a[keyi], &a[begin]);

	// 现在的begin位置是之前的keyi位置的数据，所以更新
	keyi = begin;

	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi   1, right);
}
为什么相遇位置一定是小值？
情况 1: 右指针j找到了小于key的元素

  1. 右指针j移动：从右向左移动，找到第一个小于key的元素，停下。
  2. 左指针i移动：接着，左指针i从左向右移动，找到第一个大于key的元素，停下。
    • 如果i < j，交换i和j指向的元素，然后继续移动两个指针。
    • 如果i >= j，停止移动，进行下一步操作。

在此情况下，当两个指针相遇（i == j）时，此位置的元素是最后一个j找到的小于key的值。因为j停在了小于key的元素上，而i在移动过程中没有再向右移动（因为i >= j），因此相遇位置的元素一定小于等于key。

情况 2: 右指针j没有找到小于key的元素

  1. 右指针j移动：从右向左移动，直到与key相遇（即j移动到数组的开始位置）。
  2. 左指针i移动：如果j已经与key相遇，那么i也会在开始位置停下。

在这种情况下，j没有找到任何小于key的元素，意味着所有元素都大于等于key。因此，当i和j相遇时，他们都在数组的起始位置，这时key自己与自己交换，整个数组可能是已经排序的或者所有元素都相等。

总结

在快速排序的每一次循环中，无论哪种情况，当i和j相遇时，这个位置的元素都是小于等于key的。这是因为j指针的职责是找到小于key的元素，并在找到后停下。如果j在没有找到小于key的元素前就与i相遇，那么说明这部分元素都大于等于key，相遇点自然也是小于等于key（在情况2中，key与自己交换）。这样，基准元素key可以在每轮循环结束时与相遇点的元素交换，确保key左边的元素不大于它，右边的元素不小于它，完成一次分区操作。

挖坑法

代码语言：javascript复制
int Partition(int* arr, int low, int high) {
    int pivot = arr[low];  // 选择第一个元素作为基准值
    while (low < high) {
        while (low < high && arr[high] >= pivot) {
            high--;
        }
        arr[low] = arr[high];  // 用比基准小的记录替换低位记录

        while (low < high && arr[low] <= pivot) {
            low  ;
        }
        arr[high] = arr[low];  // 用比基准大的记录替换高位记录
    }
    arr[low] = pivot;  // 基准值归位
    return low;  // 返回基准值的位置
}

void QuickSort(int* arr, int low, int high) {
    if (low < high) {
        int pivotPos = Partition(arr, low, high);  // 划分操作，将数组分为两部分
        QuickSort(arr, low, pivotPos - 1);  // 递归处理左子序列
        QuickSort(arr, pivotPos   1, high);  // 递归处理右子序列
    }
}
挖坑法的基本逻辑

  1. 选择基准值：从待排序数组中选择一个基准值，通常选择第一个元素作为基准值。
  2. 挖坑填数：通过一趟排序将待排序数组分割成独立的两部分，分别是比基准值小的元素和比基准值大的元素。这一过程中，使用挖坑的方式进行元素交换，即通过不断移动元素，将基准值挖成一个坑，然后通过交换操作，将小于基准值的元素填入这个坑中。
  3. 递归处理：对左右两部分分别递归进行上述操作，直到整个序列有序。
为什么最后的坑位一定是key这个中间值

在挖坑法中，最后的坑位置放置基准值（key）的过程保证了左侧的元素均小于等于基准值，右侧的元素均大于等于基准值。这是因为挖坑填数过程中，每次我们都是先从右侧开始查找小于基准值的元素，然后填入左侧的坑中，接着从左侧开始查找大于基准值的元素，填入右侧的坑中，直到左右指针相遇。 当左右指针相遇时，这个位置的元素一定是小于等于基准值的，因为最后一次填坑操作是从右侧填入左侧的坑，然后左右指针相遇。由于左指针在遇到右指针之前只移动到小于等于基准值的位置，所以最后的坑位置一定是中间值，即小于等于基准值的元素。 因此，挖坑法保证了基准值放置在最终排序后的正确位置，同时确保了左右两侧的元素满足快速排序的要求，实现了快速排序的划分过程。

前后指针法

代码语言：javascript复制
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	int keyi = left;

	int prev = left;
	int cur = prev   1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] &&   prev != cur)
			Swap(&a[prev], &a[cur]);

		cur  ;
	}

	Swap(&a[prev], &a[keyi]);

	keyi = prev;

	// [left, keyi-1] keyi [keyi 1, right]
	QuickSortt(a, left, keyi - 1);
	QuickSort(a, keyi   1, right);
}
前后指针法的基本逻辑

  1. 基准值选取：
    • 通过三数取中的方法选择基准值，将数组中的左端、右端和中间位置的元素进行比较，选取中间值作为基准值。
    • 将选取的基准值与数组中的第一个元素交换，以便后续比较。
  2. 前后指针交换：
    • 使用前后指针方法，前指针prev初始指向基准值，后指针cur初始指向基准值的下一个位置。
    • cur用来找比基准值小的值，cur作为比基准值大的数据前的分割指针。
    • 每次cur先走：
      • 当cur指向大于基准值时，prev先不走，cur继续向后走。
      • 当cur指向小于基准值时，prev向后走一次，并与cur交换位置（由于上一轮cur遇到大的会直接走，prev会停留，所以prev 1一定是比基准值大的数据）。
    • 持续循环，当a[cur] < a[keyi]时，将cur指向的元素与prev后一个位置的元素交换，同时prev向后移动一位。
    • 继续移动cur指针，直到遍历完整个数组，cur指向数组最后一个数据后即循环结束。
  3. 基准值归位：
    • 单趟循环结束后，此时的prev指向的一定是比基准值小的数值，所以将基准值a[keyi]与a[prev]交换，将基准值放置在正确的位置。
  4. 递归处理：
    • 基准值被换到上一趟最后prev的位置，作为中间值，用基准值将数组分为左右两部分，分别为[left, keyi-1]和[keyi 1, right]，对这两部分分别进行递归快速排序。
    • 递归结束条件是left >= right，即子数组只有一个元素或为空时结束递归。

递归优化：三数取中与小区间优化

三数取中 （Median of Three）
原因

三数取中的原因在于快速排序的性能与枢轴选择密切相关。如果选择的枢轴能够将数组均匀地分为两部分，递归的层次会减少，从而提高效率。而极端的枢轴选择会导致递归深度增加，进而导致性能下降。

**极端情况：**如果排序的是一个有序的序列（left一直是当前分组最小值），每一次从右往左找小时都会到left，这样的话每一次分区间也是从最左侧开始，会造成递归深度过深，可能造成栈溢出。

image.pngimage.png
优化点

在选择枢轴（pivot）时，使用三数取中方法，即选择数组的左端点、右端点和中点三个元素中的中间值作为枢轴。这一策略主要有以下优化点：

  1. 减少极端情况的概率： 传统的快速排序如果总是选择最左或最右的元素作为枢轴，当数组已经接近有序时，可能导致最坏情况下的时间复杂度退化为 O(n2) O(n^2) O(n2)。三数取中减少了这种情况发生的概率，因为它避免了极端的最小或最大元素作为枢轴。
  2. 更均匀的划分： 通过选择中间值，三数取中方法倾向于产生更均匀的划分，进而减少递归深度，保持算法的时间复杂度在 O(nlog⁡n) O(n log n) O(nlogn) 范围内。
代码语言：javascript复制
int GetMidi(int* a, int left, int right)
{
	int midi = (left   right) / 2;

	if (a[left] < a[midi])
	{
		if (a[midi] < a[right])
		{
			return midi;
		}
		else if (a[right] > a[left])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else // a[midi]< a[left] 
	{
		if (a[midi] > a[right])
		{
			return midi;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

优化后整体代码为：

代码语言：javascript复制
void GetMidQuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	int begin = left;
	int end = right;

	while (begin < end)
	{
		// 左边找大
		// a[end] >= a[keyi] 防止两个位置相同时一直交换，陷入无限循环
		while (begin < end && a[end] >= a[keyi])
		{
			--end;
		}

		// 右边找小
		while (begin < end && a[begin] <= a[keyi])
		{
			  begin;
		}

		/*if (begin < end)
		{
			Swap(&a[begin], &a[end]);
		}*/

		Swap(&a[begin], &a[end]);

	}

	Swap(&a[keyi], &a[begin]);

	// 现在的begin位置是之前的keyi位置的数据，所以更新
	keyi = begin;

	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi   1, right);
}
小区间优化
原因

小区间优化的原因在于，虽然快速排序平均情况下是高效的，但在处理非常小的数组时，插入排序的常数因子更低，且其性能可能优于快速排序。通过将小区间交给插入排序处理，减少了快速排序的递归调用次数和开销，同时利用插入排序的低开销特性提升了整体性能。

优化点

在处理小区间（例如长度小于10的数组片段）时，快速排序使用插入排序代替继续递归。插入排序在小数组上往往更高效，这是因为：

  1. 减少递归开销： 递归的开销包括函数调用、栈空间的使用等。当区间足够小时，这些开销可能比排序本身更耗时。插入排序的实现简单，没有递归开销。
  2. 插入排序在小数据量时的效率： 插入排序对于小数据量的排序效率高于其他复杂的排序算法（如快速排序、归并排序等），特别是在数据接近有序的情况下。
代码语言：javascript复制
// 当区间长度小于10时，使用插入排序处理
if ((right - left   1) < 10)
{
    InsertSort(a   left, right - left   1);
    return;
}

优化后整体代码：

代码语言：javascript复制
void InterCellGetMidQuickSort(int* a, int left, int right)
{

	if (left >= right)
	{
		return;
	}

	// 小区间优化
	// right - left   1为总个数：比如下标十个数的数组下标为  9 - 0，所以要   1
	if ((right - left   1) < 10)
	{
		// 加 left 为了在递归分区间后保持区间边界
		InsertSort(a   left, right - left   1);
	}
	else
	{
		int keyi = left;
		int begin = left;
		int end = right;

		while (begin < end)
		{
			// 左边找大
			// a[end] >= a[keyi] 防止两个位置相同时一直交换，陷入无限循环
			while (begin < end && a[end] >= a[keyi])
			{
				--end;
			}

			// 右边找小
			while (begin < end && a[begin] <= a[keyi])
			{
				  begin;
			}

			/*if (begin < end)
			{
				Swap(&a[begin], &a[end]);
			}*/

			Swap(&a[begin], &a[end]);

		}

		Swap(&a[keyi], &a[begin]);

		// 现在的begin位置是之前的keyi位置的数据，所以更新
		keyi = begin;

		InterCellGetMidQuickSort(a, left, keyi - 1);
		InterCellGetMidQuickSort(a, keyi   1, right);
	}
}

递归快速排序的完整优化实现代码

代码语言：javascript复制
void InterCellGetMidQuickSort(int* a, int left, int right)
{

	if (left >= right)
	{
		return;
	}

	// 小区间优化
	// right - left   1为总个数：比如下标十个数的数组下标为  9 - 0，所以要   1
	if ((right - left   1) < 10)
	{
		// 加 left 为了在递归分区间后保持区间边界
		InsertSort(a   left, right - left   1);
	}
	else
	{
		// 三数取中
		int midi = GetMidi(a, left, right);
		Swap(&a[left], &a[midi]);

		int keyi = left;
		int begin = left;
		int end = right;

		while (begin < end)
		{
			// 左边找大
			// a[end] >= a[keyi] 防止两个位置相同时一直交换，陷入无限循环
			while (begin < end && a[end] >= a[keyi])
			{
				--end;
			}

			// 右边找小
			while (begin < end && a[begin] <= a[keyi])
			{
				  begin;
			}

			/*if (begin < end)
			{
				Swap(&a[begin], &a[end]);
			}*/

			Swap(&a[begin], &a[end]);

		}

		Swap(&a[keyi], &a[begin]);

		// 现在的begin位置是之前的keyi位置的数据，所以更新
		keyi = begin;

		InterCellGetMidQuickSort(a, left, keyi - 1);
		InterCellGetMidQuickSort(a, keyi   1, right);
	}
}

非递归实现快速排序（栈、DFS）

非递归实现快速排序的核心思想是使用栈来模拟递归调用的行为。通过显式地管理栈，可以避免系统栈溢出的问题，同时对栈的管理更加清晰明确。

代码语言：javascript复制
void QuickSortNonR(int* a, int left, int right)
{
	stack<int> st;
	st.push(right);
	st.push(left);

	while (!st.empty())
	{
		int begin = st.top();
		st.pop();
		int end = st.top();
		st.pop();

        // 执行快排的单趟逻辑，不递归
		int keyi = PartQuickSort(a, begin, end);

		// 现将后面的区间入栈
		// keyi   1  :   end
		if (keyi   1 < end)
		{
			st.push(end);
			st.push(keyi   1);
		}

		if (keyi - 1 > begin)
		{
			st.push(keyi - 1);
			st.push(begin);
		}
	}
}
代码过程理解
  1. 初始化阶段:
  • 首先，将待排序数组的右边界 right 压入栈 st，然后将左边界 left 压入栈。此时，栈中的内容是 [right, left]。
  1. 第一轮循环:
    1. 从栈中先弹出 begin（栈顶元素），然后弹出 end，代表当前需要处理的子数组的左右边界。
    2. 对 a[begin] 到 a[end] 这部分数组执行一次快速排序的划分操作，找到枢轴的位置 keyi。
    3. 根据 keyi 的位置，将右子数组（keyi 1 到 end）的边界先后压入栈，再将左子数组（begin 到 keyi - 1）的边界先后压入栈。注意，每次先压入区间的右边界，再压入左边界，这样在后续出栈时能够先处理左子数组。
  2. 第二轮循环及之后:
    1. 从栈中再依次弹出 begin 和 end，处理下一个子数组。
    2. 执行一次划分操作，确定新的枢轴位置 keyi。
    3. 同样，根据 keyi 的位置，将新的子数组区间的边界按顺序压入栈。
  3. 不断重复:
  • 反复从栈中弹出左右边界，进行子数组的划分和压栈操作，直到栈为空。每次栈中压入的是还未排序的子数组边界，而从栈中弹出时则是准备进行排序操作的边界。
  1. 结束:
  • 栈为空时，表示所有子数组均已被排序，整个数组也因此被完全排序。

执行的是非递归，但是逻辑还是递归的逻辑，还是用DFS进行遍历排序

代码语言：javascript复制
         [0,9]
        /      
     [0,4]       [5,9]
      /           /   
   [0,2]  [3,4]  [5,6]   [7,9]
    /       |     |     / 
[0,1] [2,2] [3,4] [5,5] [6,6] [7,8] [9,9]
实例演示

假设初始数组为 [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]，初始左右边界为 left = 0 和 right = 9。栈的初始状态是 [9, 0]。

  • 第一轮:
    • 出栈：begin = 0, end = 9
    • 执行划分，假设 keyi = 5
    • 压入：[9, 6, 4, 0]
  • 第二轮:
    • 出栈：begin = 0, end = 4
    • 执行划分，假设 keyi = 1
    • 压入：[9, 6, 4, 2]
  • 第三轮:
    • 出栈：begin = 2, end = 4
    • 执行划分，假设 keyi = 3
    • 压入：[9, 6, 4, 4]
  • 第四轮:
    • 出栈：begin = 6, end = 9
    • 执行划分，假设 keyi = 7
    • 压入：[9, 8, 6, 6]
  • 第五轮:
    • 出栈：begin = 8, end = 9
    • 执行划分，假设 keyi = 9
    • 不再压入新的边界，因为子数组已经排序完成

如此循环，直到栈为空。最终，整个数组被正确排序。

这个过程通过栈结构有效地管理了需要排序的子数组区间，避免了递归带来的深度问题。每一轮循环中，都会先处理左边子数组，这保证了遍历的顺序和处理的深度都受到控制。

归并排序

归并排序（Merge Sort）是一种基于分治法（Divide and Conquer）的排序算法，其核心思想是将一个数组分成两个子数组，对每个子数组分别排序，然后将两个有序子数组合并成一个有序数组。归并排序具有稳定性和较好的时间复杂度，通常为 O(n log n)。

归并排序的原理

  1. 分治法思想: 归并排序遵循分治法的思想，将问题分解为更小的子问题来解决，然后将子问题的结果合并，以得到最终结果。具体而言：
    • 分：将数组从中间划分为两个子数组，分别对这两个子数组进行排序。
    • 治：将两个已排序的子数组合并成一个有序数组。
  2. 递归过程: 归并排序通过递归实现，递归地将数组不断划分，直到每个子数组的长度为1，此时子数组本身就是有序的。然后，合并这些有序的子数组。

归并排序过程解析

划分阶段（Divide）

从中间将数组划分成两个子数组，分别对两个子数组进行同样的操作。这一步通过计算中间位置 mid 来实现：

代码语言：javascript复制
mid = (begin   end) / 2

继续递归地对两个子数组进行同样的划分，直到每个子数组只包含一个元素（即 begin >= end）。在这种情况下，数组本身已经是有序的。

合并阶段（Conquer）

当子数组被划分到只包含一个元素时，开始将这些子数组两两合并。合并时，通过比较两个子数组的首元素，将较小的元素放入临时数组（或直接放入原数组的适当位置），直到所有元素都被合并。 具体合并步骤如下：

  • 初始化两个指针分别指向两个子数组的起始位置。
  • 比较两个指针指向的元素，将较小的元素拷贝到临时数组，并移动相应的指针。
  • 重复上述步骤，直到一个子数组的所有元素都被拷贝到临时数组。
  • 将另一个子数组剩余的所有元素依次拷贝到临时数组。
递归回溯

随着递归函数的回溯，每次合并两个子数组，并在回溯结束时，将临时数组的内容复制回原数组对应的位置，使整个数组逐渐变为有序。

归并排序的特性

  1. 稳定性: 归并排序是一种稳定的排序算法，即相同元素的相对顺序在排序后保持不变。
  2. 时间复杂度: 归并排序在最坏、最好和平均情况下的时间复杂度均为 O(n log n)。这是因为无论如何分，数组总会分为 log n 层，而每层的合并过程需要 O(n) 的时间。
  3. 空间复杂度: 归并排序需要额外的空间来存储合并过程中的临时数组，因此空间复杂度为 O(n)。

归并排序的代码实现

代码
代码语言：javascript复制
void _MergeSort(int* a, int* tmp, int begin, int end)
{
	if (begin >= end)
		return;

	int mid = (begin   end) / 2;
	// 如果[begin, mid][mid 1, end]有序就可以进行归并了
	_MergeSort(a, tmp, begin, mid);
	_MergeSort(a, tmp, 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, (end - begin   1) * sizeof(int));
}

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

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

	free(tmp);
	tmp = NULL;
}
代码实现再解析
递归划分

终止条件: 当 begin 大于等于 end 时，子数组的元素个数小于或等于 1，此时无需再分割，直接返回。

代码语言：javascript复制
if (begin >= end)
    return;

划分数组: 将当前数组的范围 [begin, end] 分为两个子数组 [begin, mid] 和 [mid 1, end]，其中 mid 是中间位置。

代码语言：javascript复制
int mid = (begin   end) / 2;

递归排序子数组: 先对左子数组 [begin, mid] 进行排序，再对右子数组 [mid 1, end] 进行排序。这里递归调用 _MergeSort，将问题不断分解，直到满足终止条件。

代码语言：javascript复制
_MergeSort(a, tmp, begin, mid);
_MergeSort(a, tmp, mid   1, end);
合并有序数组

在对两个子数组 [begin, mid] 和 [mid 1, end] 排序后，它们分别是有序的。接下来将它们合并成一个有序的数组。

初始化指针:

  • begin1 和 end1 表示左子数组的范围。
  • begin2 和 end2 表示右子数组的范围。
  • i 用于指向临时数组 tmp 中当前存放位置。
代码语言：javascript复制
int begin1 = begin, end1 = mid;
int begin2 = mid   1, end2 = end;
int i = begin;

合并过程: 比较 a[begin1] 和 a[begin2] 的大小，将较小的元素放入 tmp[i] 中，并移动相应的指针。重复这一过程，直到某一子数组的元素全部放入 tmp 中。

代码语言：javascript复制
while (begin1 <= end1 && begin2 <= end2)
{
    if (a[begin1] < a[begin2])
    {
        tmp[i  ] = a[begin1  ];
    }
    else
    {
        tmp[i  ] = a[begin2  ];
    }
}

处理剩余元素:

  • 如果左子数组还有未放入 tmp 的元素，则将它们依次放入 tmp 中。
  • 同样地，如果右子数组还有未放入 tmp 的元素，则将它们依次放入 tmp 中。
代码语言：javascript复制
while (begin1 <= end1)
{
    tmp[i  ] = a[begin1  ];
}

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

将 **tmp** 中的元素拷贝回原数组:

  • 在完成合并后，将 tmp 中的元素拷贝回原数组 a 中的对应位置，保证原数组 a 中的 [begin, end] 范围内的元素有序。
代码语言：javascript复制
memcpy(a   begin, tmp   begin, (end - begin   1) * sizeof(int));

总结

归并排序通过递归地将数组分成更小的子数组，然后再合并这些有序子数组来完成排序。它的分治思想和稳定性使其在处理大规模数据时表现良好（ 特别是对于链表排序或外部排序“数据存储在外部存储器中，如磁盘”的情况 ），但由于需要额外的存储空间（临时数组 tmp），在空间效率上可能不如原地排序算法（如快速排序）。

计数排序

计数排序是一种 非比较排序算法，它不同于基于比较的排序算法（如快速排序、归并排序等），其时间复杂度受限于输入数据的最大值和最小值之间的范围，而不是数据本身的数量级。计数排序的核心思想是 利用数组元素的值直接作为索引 来存储数据，从而避免了元素之间的比较。

countingSort.gifcountingSort.gif

代码实现

代码语言：javascript复制
// 时间复杂度: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;
	//printf("%dn", range);

	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
	{
		perror("calloc fail");
		return;
	}

	// 统计次数
	for (int i = 0; i < n; i  )
	{
		count[a[i] - min]  ;
	}

	// 排序
	int j = 0;
	for (int i = 0; i < range; i  )
	{
		while (count[i]--)
		{
			a[j  ] = i   min;
		}
	}

	free(count);
}

算法实现过程及原理

算法的步骤包括找出数组中的最大值和最小值，统计各个元素的频率，然后根据频率重新排列数组。

找到最小值和最大值

计数排序首先确定数组中元素的范围（即最大值和最小值之间的差）。这一步的目的是为了明确辅助数组（即计数数组）的大小。如果范围过大，计数数组的大小也会很大，导致空间浪费。因此，计数排序适用于数据范围相对集中的情况。 创建并初始化计数数组 计数数组 count 的大小为 range = max - min 1。数组的每个元素初始值为0，表示对应元素还未出现。

统计元素出现的次数

遍历待排序的数组 a，对于每个元素 a[i]，在计数数组 count 中对应位置 count[a[i] - min] 的值加1。这里的 a[i] - min 计算方式将数组的值映射到计数数组的索引范围 [0, range-1]。这样，计数数组的每个索引位置记录了对应元素在数组中出现的次数。

计算元素的累积计数

通过计算计数数组的累积和来确定每个元素在排序后数组中的位置。累积计数实际上表示的是比当前元素值小的元素总个数加上当前元素出现的次数，这样我们就能直接得到元素排序后在最终数组中的位置。

根据计数排序重构输出数组

根据累积计数反向遍历原数组，将每个元素放到输出数组的正确位置。需要注意的是，这一步必须从原数组的末尾开始向前遍历，原因是为了保持排序的稳定性（即相同元素在排序后的位置相对不变）。

将排序结果拷贝回原数组

将排序好的元素从输出数组复制回原数组 a 中。

释放辅助空间

在算法结束时，释放为计数数组分配的空间。这是为了防止内存泄漏。

算法的时间和空间复杂度

  • 时间复杂度： 计数排序的时间复杂度为 O(n range)O(n text{range})O(n range)，其中 n 是待排序数组的元素数量，range 是元素的取值范围（即最大值与最小值之差加1）。这是因为计数排序在统计元素出现次数和重新排列元素时各遍历了两次数组 a 和 count。
  • 空间复杂度： 计数排序的空间复杂度为 O(range)O(text{range})O(range)。主要是因为需要额外分配一个计数数组 count 来存储每个元素的出现次数，大小为 range。

计数排序的局限性

  • 数据范围问题：如果输入数据的范围 range 远大于元素的数量 n，计数排序的空间复杂度将大大增加，甚至超出实际的需求。这会导致内存的浪费。
  • 适用场景：由于计数排序依赖于数据范围的大小，它更适用于数据范围集中且分布较均匀的整数集合。不适合范围特别大或者小数的数据集。
  • 稳定性：虽然计数排序本身是稳定的，但这一点依赖于算法的具体实现方式，尤其是在重新排列元素时必须保证同值元素的相对顺序不变。
递归 排序 排序算法 数组 数据结构

0 人点赞