选择排序和堆排序

目录

前言??????

一.选择排序

1.思想

2.实现

3.特点

二.堆排序

1.思想

2.实现

3.特点

---

前言??????

?????????排序算法是计算机科学中的基础工具之一，对于数据处理和算法设计有着深远的影响。了解不同排序算法的特性和适用场景，能够帮助程序员在特定情况下选择最合适的算法，从而提高程序的效率和性能。本节我们讲述选择排序和堆排序。

一.选择排序

1.思想

基本思想是在未排序的部分中选择最小和最大的元素，然后将其与未排序部分的第一个元素和最后一个交换位置。重复这个过程，直到整个序列有序。

选择排序的步骤如下：

1. 初始状态： 将整个序列分为已排序部分和未排序部分，初始时已排序部分为空，未排序部分包含所有元素。

2. 选择最小元素： 在未排序部分中找到最小和最大的元素，并记录其位置。

3. 交换位置： 将找到的最小元素与未排序部分的第一个元素交换位置。最大元素与最后一个元素交换。

4. 更新已排序部分和未排序部分： 将交换后的元素视为已排序，将原未排序部分减少二个元素，继续从未排序部分重复步骤2和步骤3。

5. 重复直至完成： 重复上述过程，直到整个序列有序。

2.实现

void SelectSort(int* a, int n)
{
	int gap = 0;
	int end = n - 1;
	while (gap < end)
	{
		int maxi = gap, mini = gap;
		for (int i = gap+1; i <= end; i++)
		{
			if (a[mini] > a[i])
			{
				mini = i;
			}
			if (a[maxi] < a[i])
			{
				maxi = i;
			}
		}
		Swap(&a[gap], &a[mini]);
		if (gap == maxi)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		gap++;
		end--;
	}
}

????????注意:为了避免最大值为第一个时,被最小值交换时换走,我们修正一下,如果第一个值就是最大值,那么当第一个值与最小值交换后,修正最大值的位置

时间复杂度:O(n^2)

空间复杂度O(1)

稳定性:不稳定

3.特点

1.优势:

1. 交换操作相对较少： 选择排序的交换操作次数相对较少，每次只进行一次交换。这使得它在某些场景下可能比冒泡排序更有效。

2. 适用于小规模数据集： 在数据规模较小的情况下，选择排序的性能可能相对较好，因为其简单性和交换操作的相对少。

2.缺点

1. 时间复杂度高： 选择排序的时间复杂度为O(n^2)，其中n是待排序序列的长度。这意味着对于大规模数据集，选择排序的性能可能相对较差，尤其是与一些O(nlog n)时间复杂度的算法相比。

2. 不稳定： 选择排序是一种不稳定的排序算法。当存在相等元素时，它可能会改变它们的相对顺序，使得选择排序在某些应用场景中不适用。

3. 对逆序数据的不足： 在对逆序数据（完全逆序排列的情况）进行排序时，选择排序的性能较差。每次选择最小元素时，都需要在未排序的部分中进行线性搜索，导致交换操作次数较多。

二.堆排序

1.思想

堆排序是一种基于二叉堆（Binary Heap）数据结构的排序算法。堆是一个特殊的树状数据结构，其中每个节点的值都不大于或不小于其子节点的值。堆可以分为最大堆和最小堆。(可以看这个堆的实现与操作-CSDN博客)

堆排序的基本思想如下：

1. 建堆： 将待排序序列构建成一个二叉堆。对于最大堆，父节点的值大于或等于其子节点的值；对于最小堆，父节点的值小于或等于其子节点的值。

2. 排序： 不断将堆顶元素与堆的最后一个元素交换，然后对除最后一个元素外的部分重新调整成堆。这样，每次交换后，最大或最小元素就被放置在了正确的位置。重复这个过程，直到整个序列有序。

2.实现

void AdjustDown(int* a,int parent,int size)//向下调整建堆
{
	int child = parent *2 + 1;
	while (child < size)
	{
		if (child+1<size&&a[child] < a[child + 1])
			child++;
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent*2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)//堆排序
{
	for (int i = (n - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, i, n);
	}
	int end = n-1 ;
	while (end)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, 0, end );
		end--;
	}
}

????????这里我们采用向下调整建堆,从第一个非叶子节点开始,建大堆后,每次将堆顶元素调整到数组后面,再调整堆

时间复杂度:O(nlogn)

空间复杂度O(1)

稳定性:不稳定

3.特点

1.优势:

1. 时间复杂度稳定： 堆排序的时间复杂度为O(n log n)，其中n是待排序序列的长度。这使得堆排序在大规模数据集上具有相对较好的性能。

2. 适用于大规模数据： 由于其O(n log n)的时间复杂度，堆排序对于大规模数据集的排序任务是一个较好的选择，特别是相对于一些O(n^2)复杂度的排序算法。

2.缺点:

1. 不稳定性： 堆排序是一种不稳定的排序算法。在交换的过程中，可能会改变相同元素的相对顺序。对于需要保持相等元素相对位置关系的应用场景，不稳定性可能是一个不可接受的缺点。

2. 对于小规模数据： 尽管堆排序在大规模数据集上表现良好，但在小规模数据集上，它的性能可能不如一些简单且更容易实现的排序算法，如快速排序或插入排序。