【初阶数据结构与算法】排序算法总结篇(每个小节后面有源码)（直接插入、希尔、选择、堆、冒泡、快速、归并、计数以及非递归快速、归并排序）

一、直接插入排序

1. 稳定性分析 （1）稳定性指的是在排序过程中，两个相等的元素在排序后的相对位置不会发生变化，直接插入排序是稳定的排序算法 （2）在排序过程中，它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。由于相等元素在插入时不会改变它们在已排序序列中的相对位置（即如果两个相等元素在原序列中相邻，它们在排序后的序列中仍然相邻），因此直接插入排序是稳定的
2. 时间复杂度： （1）最优情况：O(n)（当输入序列已经是有序的情况下，每次插入操作都只需比较一次，无需移动元素） （2）最劣情况：O(n^2)（当输入序列是逆序的情况下，每次插入操作都需要比较n次，并可能需要移动n-1个元素） （3）平均情况：O(n^2)（对于随机排列的输入序列，平均需要进行n(n-1)/4次比较和移动操作）
3. 空间复杂度：O(1) （1）直接插入排序是原地排序算法，不需要额外的存储空间（除了几个用于循环控制和辅助计算的变量）
4. 特点 （1）直接插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。其核心思想是逐步将每个待排序的元素插入到已排序序列的适当位置，直到所有元素都排序完毕，这个过程类似于我们日常整理扑克牌或书籍时的插入动作
5. 优点 （1）实现简单直观，代码易于编写和理解 （2）对小规模数据或几乎已经有序的数据效率高，性能接近最优 （3）稳定性好，不会改变相等元素的相对位置 （4）原地排序，不需要额外的存储空间
6. 缺点 （1）对大规模数据效率低，特别是当数据完全逆序时，时间复杂度达到最坏情况的O(n^2) （2）需要频繁移动数据元素，特别是在插入位置靠前的情况下，会导致大量的数据移动操作 （3）不适用于数据规模较大且分布不均匀的情况，因为时间复杂度较高且性能不稳定。
7. 源码：

//直接插入排序
void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i, tmp = arr[end + 1];
		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}

二、希尔排序

1. 稳定性分析 （1）希尔排序是不稳定的排序算法 （2）在排序过程中，由于分组和增量递减的特性，相同大小的元素可能会因为分组后的插入排序操作而发生相对位置的改变。特别是当两个相等元素位于不同增量分组时，它们可能经过不同的插入排序路径，最终导致相对位置的变化
2. 时间复杂度： （1）最优情况：依赖于增量序列的选择和数据分布，但一般优于O(n^2) （2）最劣情况：同样依赖于增量序列的选择，可能退化到O(n^2)，特别是在增量选择不当或数据分布极端的情况 （3）平均情况：通常认为在良好选择的增量序列下，希尔排序的平均时间复杂度介于O(n logn)和O(n^1.5)之间，但具体数值受多种因素影响
3. 空间复杂度：O(1) （1）希尔排序是原地排序算法，不需要额外的存储空间（除了几个用于循环控制和辅助计算的变量）
4. 特点 希尔排序通过引入增量序列，将数组分成若干个子序列，并对每个子序列进行直接插入排序。随着增量的递减，子序列的长度逐渐增加，直到增量为1时，对整个数组进行一次完整的插入排序。这种分组和增量递减的策略，使得希尔排序在初始阶段能够快速减少数据的无序度，为后续的直接插入排序提供更有利的环境
5. 优点 （1）相对于直接插入排序，希尔排序在处理大规模数据时通常具有更高的效率，因为它能够更快地减少数据的无序度 （2）希尔排序的空间复杂度为O(1)，不需要额外的存储空间 （3）实现相对简单，代码易于理解和维护
6. 缺点 （1）稳定性差，可能会改变相等元素的相对位置 （2）时间复杂度的具体表现依赖于增量序列的选择，选择不当可能导致性能下降
7. 源码：

//希尔排序
void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i, tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}

三、直接选择排序

1. 稳定性分析 （1）稳定性：直接选择排序是不稳定的排序算法 （2）在排序过程中，每次从未排序部分选出最小（或最大）的元素后，都会将其与未排序部分的第一个元素进行交换。这种交换操作可能会破坏相同元素之间的原始顺序，因此直接选择排序不是稳定的排序算法
2. 时间复杂度： （1）最优情况：O(n^2)（无论输入序列如何，都需要进行n-1次选择操作，每次选择都需要遍历剩余未排序部分） （2）最劣情况：O(n^2)（同最优情况，因为每次选择都需要遍历剩余未排序部分） （3）平均情况：O(n^2)（同最优和最劣情况，因为直接选择排序的时间复杂度不依赖于输入序列的具体分布）
3. 空间复杂度：O(1) （1）直接选择排序是原地排序算法，不需要额外的存储空间（除了几个用于循环控制和辅助计算的变量）
4. 特点 （1）直接选择排序通过反复从未排序部分选出最小（或最大）的元素，并将其放到已排序部分的末尾（或开头），从而逐步构建出有序序列。其核心思想是每次选择都确保选出的是当前未排序部分的最小（或最大）元素，然后将其放到正确的位置上
5. 优点 （1）实现简单直观，代码易于编写和理解 （2）不需要额外的存储空间，空间复杂度为O(1) （3）对于小规模数据或数据分布较为均匀的情况，性能尚可接受
6. 缺点 （1）不稳定性可能导致相同元素的相对位置发生变化，这在某些应用场景中可能是不可接受的 （2）时间复杂度为O(n^2)，在处理大规模数据时效率较低 （3）在选择最小（或最大）元素时，需要遍历整个未排序部分，导致大量的比较操作 （4）对于几乎已经有序的数据，性能没有显著提升，因为每次选择仍然需要遍历剩余未排序部分
7. 源码：

//直接选择排序(单向)
void SelectSort1(int* arr, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		for (int i = begin; i <= end; i++)
		{
			if (arr[i] < arr[mini])
				mini = i;
		}
		Swap(&arr[begin], &arr[mini]);
		begin++;
	}
}

//直接选择排序(双向)
void SelectSort2(int* arr, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin; i <= end; i++)
		{
			if (arr[i] < arr[mini])
				mini = i;
			if (arr[i] > arr[maxi])
				maxi = i;
		}
		if (maxi == begin)
			maxi = mini;
		Swap(&arr[begin], &arr[mini]);
		Swap(&arr[end], &arr[maxi]);
		begin++, end--;
	}
}

四、堆排序

1. 稳定性分析 （1）稳定性：堆排序是不稳定的排序算法 （2）堆排序通过构建最大堆（或最小堆）来选择最大（或最小）元素，并将其放到已排序部分的末尾（或开头）。在这个过程中，如果两个相等元素位于不同子树中，它们可能会因为堆的调整（如堆化过程）和元素交换而发生相对位置的改变。因此，堆排序不能保证相同元素的相对位置在排序前后保持不变
2. 时间复杂度： （1）最优情况：O(n log n)（无论输入序列如何，堆排序都需要构建堆和调整堆，这两个过程的时间复杂度都是O(n log n)） （2）最劣情况：O(n log n)（同最优情况，因为堆排序的时间复杂度不依赖于输入序列的具体分布） （3）平均情况：O(n log n)（同最优和最劣情况，堆排序的时间复杂度在最好、最坏和平均情况下都是一致的）
3. 空间复杂度：O(1) （1）堆排序是原地排序算法，不需要额外的存储空间（除了几个用于循环控制和辅助计算的变量）。所有操作都在原数组上进行，因此空间复杂度为O(1)
4. 特点 （1）堆排序是一种基于二叉堆数据结构的排序算法。它利用堆的性质（如最大堆或最小堆）来选择最大（或最小）元素，并逐步构建出有序序列。堆排序通过构建初始堆、不断交换堆顶元素与末尾元素、并调整剩余堆结构的过程来实现排序。
5. 优点 （1）时间复杂度稳定：堆排序的时间复杂度为O(n log n)，在最好、最坏和平均情况下都是一致的，因此性能稳定 （2）空间复杂度低：堆排序是原地排序算法，不需要额外的存储空间，空间复杂度为O(1) （3）适用性广：堆排序可以处理大规模数据，且不需要递归调用，适合用在对稳定性要求不高且空间不允许递归的场景下 （4）可以作为优先级队列的基础：堆数据结构本身就是一个优先级队列，堆排序算法可以看作是不断地从堆中取出优先级最高（或最低）的元素的过程
6. 缺点 （1）不稳定性：堆排序是不稳定的排序算法，相同元素的相对位置可能会发生变化。这在某些应用场景中可能是不可接受的 （2）实现相对复杂：堆排序的实现需要掌握堆的实现以及向上、向下调整算法，相对于一些简单的排序算法（如直接插入排序）来说，实现起来较为复杂 （3）对数据的访问模式不利：堆排序在构建堆和调整堆的过程中，需要频繁地访问父节点和子节点，这种访问模式可能会导致CPU缓存的命中率降低，从而影响排序的效率。然而，这个缺点在大多数情况下并不明显，因为堆排序的整体时间复杂度仍然是O(n log n)
7. 源码：

在这里插入代码片//向上调整算法
void AdjustUp(int* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//向下调整算法
void AdjustDown(int* arr, int parent, int n)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child + 1] > arr[child])
		{
			child++;
		}
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


//堆排序
void HeapSort(int* arr, int n)
{
	//向上调整建堆
	/*for (int i = 0; i < n; i++)
	{
		AdjustUp(arr, i);
	}*/

	//向下调整建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}

	//建堆后进行排序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}
}

五、冒泡排序

1. 稳定性分析 （1）稳定性：冒泡排序是稳定的排序算法 （2）在排序过程中，它通过相邻元素的比较和交换来逐步将最大（或最小）元素“冒泡”到数组的末尾（或开头）。由于每次交换只涉及相邻元素，并且当发现两个元素相等时不会进行交换，因此冒泡排序能够保持相等元素的相对位置不变
2. 时间复杂度： （1）最优情况：O(n)（当输入序列已经是有序的情况下，冒泡排序只需进行一次遍历，确认所有元素都已排序，不进行任何交换操作） （2）最劣情况：O(n^2)（当输入序列完全逆序的情况下，冒泡排序需要进行大量的比较和交换操作，每次遍历都需要将未排序部分的最大元素移动到末尾，总共需要(n-1) + (n-2) + … + 1 = n*(n-1)/2次比较和接近这个数量的交换） （3）平均情况：O(n^2)（对于随机排列的输入序列，平均需要进行大量的比较和交换操作，时间复杂度接近最劣情况）
3. 空间复杂度：O(1) （1）冒泡排序是原地排序算法，不需要额外的存储空间（除了几个用于循环控制和辅助计算的变量）
4. 特点 （1）冒泡排序通过相邻元素的比较和交换，逐步将最大（或最小）元素移动到数组的末尾（或开头）。它重复这个过程，直到整个数组有序。冒泡排序的核心思想是每次遍历都确定一个最大（或最小）元素的位置，并通过相邻元素的比较和交换来实现
5. 优点 （1）实现简单直观，代码易于编写和理解 （2）稳定性好，不会改变相等元素的相对位置 （3）对小规模数据或几乎已经有序的数据，性能尚可接受
6. 缺点 （1）时间复杂度较高，为O(n^2)，在处理大规模数据时效率较低 （2）需要频繁地比较和交换相邻元素，导致算法的执行效率不高 （3）不适用于数据规模较大且分布不均匀的情况，因为每次都需要进行完整的遍历和可能的多次交换
7. 源码：

//冒泡排序
void BubbleSort(int* arr, int n)
{
	//一趟冒泡排序排好一个数，把n-1个数排好，剩下一个数肯定就在该在的位置
	for (int i = 0; i < n - 1; i++)
	{
		//一趟冒泡排序的逻辑
		int flag = 1;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(&arr[j], &arr[j + 1]);
				flag = 0;
			}
		}
		if (flag)
			break;
	}
}

六、快速排序

1. 稳定性分析 （1）稳定性：快速排序是不稳定的排序算法 （2）在快速排序的分区过程中，如果数组中存在两个或多个相等的元素，并且这些相等元素在基准元素（pivot）的两侧，那么这些相等元素在排序后的相对位置可能会发生变化 （3）具体来说，当一个相等元素被分配到基准元素的左侧子数组时，而另一个相等元素被分配到基准元素的右侧子数组时，它们的相对顺序就会被打乱。因此，快速排序不能保证排序前后相等元素的相对位置保持不变
2. 时间复杂度： （1）最优情况：O(n log n)（当每次选择的基准元素都能将数组均匀分成两部分时，递归深度为log n，每层递归处理n个元素，因此时间复杂度为O(n log n)） （2）最劣情况：O(n ^ 2 )（当每次选择的基准元素都是数组的最大或最小元素时，会导致每次划分都极不平衡，递归深度为n，每层递归仍然需要处理n个元素，因此时间复杂度为O(n^2)，这种情况通常发生在数组已经有序或几乎有序的情况下） （2）平均情况：O(n log n) 通过随机选择基准元素或使用其他优化策略（如三数取中法），可以大大降低最坏情况出现的概率，使得平均时间复杂度保持在O(n log n)
3. 空间复杂度： （1）主要取决于递归调用栈的深度 （2）在最优情况下，递归深度为log n，因此空间复杂度为O(log n) （3）在最劣情况下，递归深度为n，因此空间复杂度为O(n) （4）通常情况下，快速排序的空间复杂度会介于O(log n)和O(n)之间。不过，由于快速排序通常使用原地分区（in-place partition），不需要额外的存储空间来存储子数组，因此除了递归调用栈外，不需要额外的空间开销
4. 特点 （1）快速排序是一种基于分治思想的排序算法 （2）它选择一个基准元素，通过一趟排序将数组分成两个子数组，使得左边子数组的所有元素都小于或等于基准元素，右边子数组的所有元素都大于基准元素 （3）然后递归地对两个子数组进行排序，直到整个数组有序
5. 优点 （1）实现简单，代码易于编写和理解 （2）在平均情况下，时间复杂度为O(n log n)，效率较高 （3）原地排序，不需要额外的存储空间（除了递归调用栈） （4）适用于大规模数据的排序
6. 缺点 （1）不稳定性可能导致相同元素的相对位置发生变化 （2）在最坏情况下，时间复杂度会退化为O(n^2)，尽管通过优化基准元素的选择可以降低这种风险，但无法完全消除。特别是当数组已经有序或几乎有序时，快速排序的性能会较差 （3）递归调用可能导致栈溢出，特别是在处理大规模数据时。不过，这可以通过改用非递归实现或限制递归深度来避免
7. 源码：

//hoare版本
int _QuickSort1(int* arr, int left, int right)
{
	int keyi = left++;
	while (left <= right)
	{
		while (left <= right && arr[right] >= arr[keyi])
		{
			right--;
		}
		while (left <= right && arr[left] <= arr[keyi])
		{
			left++;
		}
		if (left <= right)
		{
			Swap(&arr[left++], &arr[right--]);
		}
	}
	Swap(&arr[keyi], &arr[right]);
	return right;
}

//挖坑法
int _QuickSort2(int* arr, int left, int right)
{
	int hole = left, key = arr[left];
	while (left < right)
	{
		while (left < right && arr[right] >= key)
		{
			right--;
		}
		arr[hole] = arr[right];
		hole = right;
		while (left < right && arr[left] <= key)
		{
			left++;
		}
		arr[hole] = arr[left];
		hole = left;
	}
	arr[hole] = key;
	return hole;
}

//Lomuto双指针
int _QuickSort3(int* arr, int left, int right)
{
	int prev = left, cur = left + 1;
	int keyi = left;
	while (cur <= right)
	{
		if (arr[cur] < arr[keyi] && ++prev != cur)
		{
			Swap(&arr[prev], &arr[cur]);
		}
		cur++;
	}
	Swap(&arr[keyi], &arr[prev]);
	return prev;
}

//快排
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = _QuickSort2(arr, left, right);
	//[left, keyi - 1] [keyi + 1, right]
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);
}

七、归并排序

1. 稳定性分析 （1）稳定性：归并排序是稳定的排序算法 （2）在归并排序的过程中，当两个相等元素被分配到不同的子数组时，合并这两个子数组时，会按照它们在原数组中的顺序进行合并，因此相等元素的相对位置不会发生变化 （3）具体来说，归并排序在合并两个有序子数组时，是从两个子数组的开头依次比较元素，将较小的元素依次放入合并后的数组中，如果两个元素相等，则先放入左子数组中的元素，从而保证了排序的稳定性
2. 时间复杂度： （1）最优情况：O(n log n) 归并排序的时间复杂度主要取决于合并操作的次数。在最优情况下，每次合并操作都能将两个长度相等的子数组合并成一个有序数组，递归深度为log n，每层递归处理n个元素，因此时间复杂度为O(n log n)。 （2）最劣情况：O(n log n) 即使在最劣情况下，即每次合并操作都是将一个长度为1的子数组与一个长度为n-1的子数组合并，递归深度仍然为log n，每层递归仍然需要处理n个元素，因此时间复杂度仍然为O(n log n) （3）平均情况：O(n log n) 无论输入数组的顺序如何，归并排序的时间复杂度都保持在O(n log n)，具有较好的稳定性
3. 空间复杂度： （1）归并排序的空间复杂度主要取决于合并过程中所需的辅助空间。在合并两个有序子数组时，需要额外的存储空间来存放合并后的数组。因此，归并排序的空间复杂度为O(n) （2）不过，归并排序的空间复杂度可以通过一些优化手段来降低，如使用原地归并算法（但实现较为复杂，且可能影响性能）
4. 特点 （1）归并排序是一种基于分治思想的排序算法 （2）它将数组分成两个子数组，分别对这两个子数组进行排序，然后将两个有序子数组合并成一个有序数组 （3）递归地对数组进行分割和合并，直到整个数组有序
5. 优点 （1）稳定性保证了相等元素的相对位置不变 （2）时间复杂度为O(n log n)，具有较好的性能 （3）适用于各种规模的数据排序
6. 缺点 （1）空间复杂度为O(n)，需要额外的存储空间来存放合并后的数组。虽然可以通过一些优化手段来降低空间复杂度，但实现较为复杂，且可能影响性能 （2）归并排序的递归实现可能导致栈溢出，特别是在处理大规模数据时。不过，这可以通过改用非递归实现或增加栈空间来避免
7. 源码：

void _MergeSort(int* arr, int left, int right, int* tmp)
{
	if (left >= right)
	{
		return;
	}

	int mid = left + (right - left) / 2;
	//[left, mid] [mid + 1, right]
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right, tmp);

	//合并两个有序序列
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] <= arr[begin2])
		{
			tmp[index++] = arr[begin1++];
		}
		else
		{
			tmp[index++] = arr[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[index++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = arr[begin2++];
	}

	//将数据拷贝回原数组
	for (int i = left; i <= right; i++)
	{
		arr[i] = tmp[i];
	}
}

//归并排序
void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(n * sizeof(int));
	if (tmp == NULL)
	{
		perror("malloc");
		return;
	}

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

	free(tmp);
	tmp = NULL;
}

八、计数排序

1. 稳定性分析 （1）稳定性：计数排序是稳定的排序算法 （2）在计数排序的过程中，相同元素的计数是分别进行的，且在最后根据计数结果构建有序数组时，相同元素会按照它们在原数组中的顺序依次放入，因此保证了排序的稳定性 （3）具体来说，计数排序通过计算每个元素在数组中出现的次数，然后根据计数结果确定每个元素在排序后数组中的位置，最后依次将元素放入对应位置，从而实现了排序。在这个过程中，相同元素的相对位置不会发生变化
2. 时间复杂度： （1）最优情况：O(n + k)    计数排序的时间复杂度主要取决于计数和构建有序数组两个步骤。其中，计数步骤需要遍历一次数组，时间复杂度为O(n)；    构建有序数组步骤需要遍历一次计数数组（或哈希表），并根据计数结果将元素放入有序数组中，时间复杂度为O(k)，其中k是元素的取值范围。因此，计数排序的最优时间复杂度为O(n + k)。 （2）最劣情况：O(n + k)    无论输入数组的顺序如何，计数排序的时间复杂度都保持在O(n + k)，具有较好的稳定性 （3）平均情况：O(n + k)    计数排序的平均时间复杂度也保持在O(n + k)，不受输入数组顺序的影响
3. 空间复杂度： （1）计数排序的空间复杂度主要取决于计数数组（或哈希表）的大小 （2）在计数排序中，需要使用一个大小为k的计数数组（或哈希表）来存储每个元素的出现次数。因此，计数排序的空间复杂度为O(k) （3）不过，需要注意的是，这里的k是元素的取值范围，而不是数组的长度。如果元素的取值范围很大，但数组中元素的种类很少，那么计数数组的大部分空间可能会被浪费
4. 特点 （1）计数排序是一种非基于比较的排序算法 （2）它适用于元素取值范围较小的整数排序问题 （3）计数排序通过计算每个元素在数组中出现的次数，然后根据计数结果构建有序数组，从而实现了排序
5. 优点 （1）稳定性保证了相等元素的相对位置不变 （2）时间复杂度为O(n + k)，在元素取值范围较小的情况下具有较好的性能。 （3）实现简单，代码易于编写和理解。
6. 缺点 （1）空间复杂度为O(k)，其中k是元素的取值范围。如果元素的取值范围很大，那么计数排序的空间开销会很大 （2）计数排序只能用于整数排序问题，对于浮点数或字符串等其他类型的数据，无法使用计数排序进行排序 （3）当元素取值范围很大且数组中元素种类很多时，计数排序的性能会下降，甚至不如基于比较的排序算法（如快速排序、归并排序等）
7. 源码：

//计数排序
void CountSort(int* arr, int n)
{
	int min = arr[0], max = arr[0];
	for (int i = 1; i < n; i++)
	{
		if (arr[i] < min)
			min = arr[i];
		if (arr[i] > max)
			max = arr[i];
	}
	int range = max - min + 1;
	//可以使用calloc直接将数组初始化
	int* count = (int*)malloc(range * sizeof(int));
	if (count == NULL)
	{
		perror("malloc");
		return;
	}
	memset(count, 0, range * sizeof(int));
	for (int i = 0; i < n; i++)
	{
		count[arr[i] - min]++;
	}
	int index = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			arr[index++] = i + min;
		}
	}

	free(count);
	count = NULL;
}

九、非递归快速排序

1. 稳定性分析 （1）稳定性：非递归快速排序与递归快速排序在稳定性方面是一致的，都是不稳定的排序算法 （2）在快速排序的分区过程中，如果数组中存在两个或多个相等的元素，并且这些相等元素在基准元素（pivot）的两侧，那么这些相等元素在排序后的相对位置可能会发生变化 （3）具体来说，当一个相等元素被分配到基准元素的左侧子数组时，而另一个相等元素被分配到基准元素的右侧子数组时，它们的相对顺序就会被打乱。因此，非递归快速排序也不能保证排序前后相等元素的相对位置保持不变。
2. 时间复杂度： （1）最优情况：O(n log n)    当每次选择的基准元素都能将数组均匀分成两部分时，无论是递归还是非递归实现，时间复杂度都能达到最优的O(n log n)。 （2）最劣情况：O(n^2)    与递归快速排序相同，当每次选择的基准元素都是数组的最大或最小元素时，会导致每次划分都极不平衡，时间复杂度会退化为O(n^2)    这种情况通常发生在数组已经有序或几乎有序的情况下。不过，通过优化基准元素的选择（如三数取中法）或使用随机化策略，可以降低最坏情况出现的概率。 （3）平均情况：O(n log n) 在平均情况下，通过合理的基准元素选择，非递归快速排序的时间复杂度也能保持在O(n log n)
3. 空间复杂度： （1）非递归快速排序的空间复杂度通常低于递归快速排序，因为它不需要递归调用栈来保存中间状态 （2）不过，非递归实现通常需要额外的栈或队列等数据结构来模拟递归过程，因此其空间复杂度仍然与输入数组的大小n有关，但通常不会达到O(n)的级别（除非使用显式的栈来保存待排序的子数组范围）
4. 特点 （1） 非递归快速排序是一种基于分治思想的排序算法，但与递归快速排序不同的是，它使用显式的栈或队列等数据结构来保存待排序的子数组范围，从而避免了递归调用带来的栈溢出风险 （2）在每次迭代中，非递归快速排序选择一个基准元素，通过一趟排序将数组分成两个子数组，然后依次对这两个子数组进行排序，直到整个数组有序。
5. 优点 （1）避免了递归调用带来的栈溢出风险，特别是在处理大规模数据时更加安全 （2）通过优化基准元素的选择和使用显式的栈或队列等数据结构，可以提高排序的稳定性和效率
6. 缺点 （1）实现相对复杂，需要额外的数据结构来模拟递归过程 （2）虽然空间复杂度通常低于递归快速排序，但仍然需要额外的空间来保存待排序的子数组范围 （3）在最坏情况下，时间复杂度仍然会退化为O(n^2)，尽管通过优化可以降低这种风险
7. 源码：

//非递归快排(使用栈实现)
void QuickSortNonR1(int* arr, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);
	
	while (!STEmpty(&st))
	{
		int left = STTop(&st);
		STPop(&st);
		int right = STTop(&st);
		STPop(&st);
		int keyi = _QuickSort1(arr, left, right);
		//[left, keyi - 1] [keyi + 1, right]
		if (right > keyi + 1)
		{
			STPush(&st, right);
			STPush(&st, keyi + 1);
		}
		if (left < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, left);
		}
	}

	STDestroy(&st);
}

//非递归快排(使用队列实现)
void QuickSortNonR2(int* arr, int left, int right)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, left);
	QueuePush(&q, right);

	while (!QueueEmpty(&q))
	{
		int left = QueueFront(&q);
		QueuePop(&q);
		int right = QueueFront(&q);
		QueuePop(&q);
		int keyi = _QuickSort2(arr, left, right);
		//[left, keyi - 1] [keyi + 1, right]
		if (left < keyi - 1)
		{
			QueuePush(&q, left);
			QueuePush(&q, keyi - 1);
		}
		if (right > keyi + 1)
		{
			QueuePush(&q, keyi + 1);
			QueuePush(&q, right);
		}
	}

	QueueDestroy(&q);
}

十、非递归归并排序

1. 稳定性分析 （1）稳定性：非递归归并排序与递归归并排序在稳定性方面保持一致，都是稳定的排序算法 （2）在归并排序的过程中，当两个相等元素分别位于不同的子数组时，合并这两个子数组时会按照它们在原数组中的顺序进行合并，因此保证了排序的稳定性 （3）具体来说，非递归归并排序通过迭代的方式，依次合并相邻的子数组，直到整个数组有序。在这个过程中，相同元素的相对位置不会发生变化。
2. 时间复杂度： 最优情况：O(n log n)    非递归归并排序的时间复杂度主要取决于合并操作的次数。在最优情况下，每次合并操作都能将两个长度相等的子数组合并成一个有序数组，迭代次数为log n（以2为底），每层迭代处理n个元素，因此时间复杂度为O(n log n) 最劣情况：O(n log n)    无论输入数组的顺序如何，非递归归并排序的迭代次数都保持在log n，每层迭代仍然需要处理n个元素，因此时间复杂度始终为O(n log n)，具有较好的稳定性 平均情况：O(n log n)    非递归归并排序的平均时间复杂度也保持在O(n log n)，不受输入数组顺序的影响
3. 空间复杂度： （1）非递归归并排序的空间复杂度主要取决于合并过程中所需的辅助空间。在合并两个有序子数组时，需要额外的存储空间来存放合并后的数组 （2）虽然非递归实现避免了递归调用栈的开销，但仍然需要额外的空间来保存合并过程中的中间结果。因此，非递归归并排序的空间复杂度通常为O(n)，其中n是数组的长度。 （3）需要注意的是，这里的空间复杂度是指除了输入数组外所需的额外空间
4. 特点 （1）非递归归并排序是一种基于分治思想的排序算法，但与递归归并排序不同的是，它使用迭代的方式依次合并相邻的子数组，从而避免了递归调用带来的栈溢出风险。在每次迭代中，非递归归并排序选择相邻的两个子数组进行合并，直到整个数组有序
5. 优点 （1）稳定性保证了相等元素的相对位置不变 （2）时间复杂度为O(n log n)，具有较好的性能 （3）避免了递归调用带来的栈溢出风险，特别是在处理大规模数据时更加安全
6. 缺点 （1）空间复杂度为O(n)，需要额外的存储空间来存放合并过程中的中间结果。虽然可以通过一些优化手段来降低空间复杂度（如使用原地归并算法），但实现较为复杂且可能影响性能 （2）非递归实现相对递归实现来说，代码可能更加复杂和难以理解。不过，这取决于具体的实现方式和个人的编程经验
7. 源码：

//非递归版归并排序
void MergeSortNonR(int* arr, int n)
{
	int* tmp = (int*)malloc(n * sizeof(int));
	if (tmp == NULL)
	{
		perror("malloc");
		return;
	}

	//gap是每组元素的个数
	//刚开始每组元素个数为1
	int gap = 1;
	while (gap < n)
	{
		//每组gap个元素，两组两组进行合并
		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;
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}
			int index = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] <= arr[begin2])
				{
					tmp[index++] = arr[begin1++];
				}
				else
				{
					tmp[index++] = arr[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[index++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = arr[begin2++];
			}
			for (int j = i; j <= end2; j++)
			{
				arr[j] = tmp[j];
			}
		}
		gap *= 2;
	}
	free(tmp);
	tmp = NULL;
}

   那么本次的排序算法总结就分享到这里啦，初阶数据结构与算法这个篇章的知识也就到这里结束啦，凑巧也是2024年最后一篇文章，从2025年开始就进入C++的学习啦，感谢大家近来的支持，大家新年快乐！    bye~