【排序算法】冒泡排序、选择排序

P_M_P

修改于 2024-01-20 08:12:33

1550

修改于 2024-01-20 08:12:33

冒泡排序

💡思想

冒泡排序，又被称为气泡排序或泡沫排序。它会遍历若干次要排序的数列，每次遍历时，会从前往后一次比较相邻两个数的大小，如果前者比后者大，则交换它们的位置，如果后者比前者大，则继续遍历。这样，一次遍历之后，数组中最大的元素就会处于数组的末尾。同理，第二次遍历后，数组第二大的元素则会处在最大的元素前一位。重复上述操作，知道整个数组有序为止。

💡图片演示

💡代码实现

void bubble_sort(int* arr,int sz)
{
	int i = 0;
	int flag = 1;
	for (i = 0; i < sz-1; i++)
	{
		int j = 0;
 //一趟冒泡排序之后，数组中最大的元素就在数列的末尾
		for (j = 0; j < sz - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])//如果左边的数比右边的数大，就交换
			{
				flag = 0;
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
		if (flag == 1)//如果已经有序，提前跳出循环
			break;
	}
}

💡算法分析

时间复杂度：最坏O(N^2),最好O(N)，平均时间复杂度O(N^2)

空间复杂度：O(1)

选择排序

💡思想

首先在未排序的数组中找到最大或者最小的元素，然后将其放在起始位置，同理，在未排序的数组中继续寻找最大或最小的数，将其放在已排序（每次找到的元素构成的数列）的数列的末尾。

💡图片演示

第一趟找到最小的数，然后与第一个数交换

第二趟找到次小的数，然后与第二个数交换，

以此类推......

⚠注意：这里交换时，保存的是下标，不然无法交换

💡代码实现

void SelectSort(int* a, int n)
{
	//每轮选出区间内最大的元素和最小的元素的下标
	//然后将这两个元素分别和区间最右边和最左边的元素交换
	int begin = 0;
	int end = n - 1;
	while (begin <= end)
	{
		int mini = begin;
		int maxi = begin;
		for (int i = begin + 1; i <= end; i++)//保存的是下标
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		swap(&a[mini], &a[begin]);
		if (maxi == begin)//可能第一次换的时候最大的数在最左边，这样交换之后，
			              //最大的数的位置就发生了变化，第二次交换，最大的数就不能换到最后面
		{
			maxi = mini;
		}
		swap(&a[maxi], &a[end]);
		begin++;
		end--;
	}
}