选择排序、冒泡排序----C语言数据结构

引言

选择排序（Selection Sort）是一种简单直观的排序算法，它的基本思想是每次从未排序的元素中选择最小（或最大）的元素，然后将其放置在已排序部分的末尾。这个过程不断重复，直到所有元素都被排序完成。

选择排序虽然在时间复杂度上不如一些高级的排序算法，但由于其简单直观的实现方式，以及在某些特定情况下的一些优势：

小型数据集：选择排序在处理小规模数据集时可能比较适用。由于其基本操作是选择最小元素并交换，对于较小规模的数据集，选择排序可能不会带来很大的性能损失，并且实现较为简单。
内存有限的环境：
由于选择排序是一种原地排序算法，它不需要额外的存储空间，仅使用常数级别的额外空间。在内存有限的环境下，选择排序可能是一个可行的选择，因为它不会占用太多内存。

1.选择排序的实现

基本思想: 每一次从待排序的数据元素中选出最小(或者最大的)的一个元素,置于最前端也就是序列的起始位置,使最前端的数据元素是有序的,直到全部待排序的数据元素全都排列完全

思路:

在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中,继续此操作

初始版

void Swap(int* a, int* b)
{
	int c = *a;
	*a = *b;
	*b = c;
}

void SelectSort(int* a, int n)
{
	for (int j = 0;j < n;j++)
	{
	//注意这里min记录的是下标而不是值，原因是记录值，无法实现交换
		int begin = j, min = begin;
		for (int i = j;i < n;i++)
		{
			if (a[i] <= a[min])
			{
				min = i;
			}
		}
		Swap(&a[begin], &a[min]);
	}
}

优化版
在实践中我们其实是可以再一趟循环中，同时交换最大值和最小值，也就是将最小值放到最前面，将最大值放到最后面，来提升效率

void SelectSort(int* a, int n)
{
	int begin = 0,end = n;
	while (begin<end)
	{
		//记录一趟循环的最大最小值
		int min = begin, max = begin;
		for (int i = begin + 1;i < end;i++)
		{
			if (a[i] <= a[min])
				min = i;
			if (a[i] > a[max])
				max = i;
		}
		Swap(&a[begin], &a[min]);
		//防止最大值为begin而被交换
		if (max == begin)
		{
			max = min;
		}
		Swap(&a[end - 1], &a[max]);
		begin++;
		end--;
	}
}

1.1选择排序的时间复杂度

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

最好情况时间复杂度：
在最好的情况下，即输入数组已经是有序的状态，选择排序每次只需要比较一次元素就能确定最小值，然后进行一次交换。因此，最好情况时间复杂度为 O(n^2)。
最坏情况时间复杂度：
在最坏的情况下，即输入数组是逆序的状态，选择排序每次都需要比较未排序部分的所有元素，找到最小值，然后进行交换。对于长度为 n 的数组，第一次需要比较 n 次，第二次需要比较 n-1 次，以此类推，总的比较次数是 n + (n-1) + (n-2) + … + 1，可以用等差数列求和公式求解，最坏情况时间复杂度为 O(n^2)。
平均情况时间复杂度：
在平均情况下，选择排序的性能也是 O(n^ 2)。这是因为无论初始数组的顺序如何，每次选择都需要进行一次完整的未排序部分的遍历，找到最小值进行交换。平均情况下，比较次数和交换次数都是 O(n^2)。

优：

简单直观：选择排序是一种非常简单直观的排序算法，易于理解和实现。这使得它成为学习排序算法的良好入门例子。
原地排序：选择排序是一种原地排序算法，只需要常数级别的额外空间。
不受输入数据分布影响：
与某些排序算法（例如快速排序）不同，选择排序的性能不会受输入数据的分布情况的影响。它在任何情况下都需要相同数量的比较和交换操作。

缺：

低效率：选择排序的时间复杂度为
O(n^2)，无论输入数据的分布如何，它都需要进行相同数量的比较和交换操作。在大规模数据集上，性能相对较差。
不稳定性：选择排序是一种不稳定的排序算法，相等元素的相对顺序在排序后可能发生改变。
固定元素位置：选择排序每次都会选择最小的元素放置到正确的位置，这可能导致一些已经有序的元素在排序过程中仍然会发生交换，增加了不必要的操作。
不适用于部分有序数组：对于部分有序的数组，选择排序的性能也较差，因为它在每一轮都会进行完整的比较和交换操作。

2.冒泡排序的实现

冒泡排序是比较基础的排序算法之一，其思想是相邻的元素两两比较，较大的数下沉，较小的数冒起来，这样一趟比较下来，最大(小)值就会排列在一端。整个过程如同气泡冒起，因此被称作冒泡排序。
冒泡排序的步骤是比较固定的：

俩俩相邻元素比较,大的往后沉 (也就是交换),小的往前冒[单趟,内层循环]
按待排序数组的元素,依次重复遍历(外层循环),直到遍历整个数组

在这里插入图片描述

void Swap(int* a, int* b)
{
	int c = *a;
	*a = *b;
	*b = c;
}


//冒泡排序,把最大的排最后，排除最大的后的数组再遍历排最大
void BubbleSort(int* a, int n)
{	for(int j=0;j<n-1;j++)
	{
		for (int i = 0;i <n-j-1;i++)
		{
			if (a[i] > a[i + 1])
			{
				Swap(&a[i], &a[i + 1]);
			}
		}
	}
}