[数据结构与算法]数据结构：冒泡排序及其优化

定义：沉石排序，从前向后，两两比较，大的向后挪动（从小到大排序），时间复杂度O（n^2） 空间复杂度O（1） ?稳定性：稳定

?

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
void BubbleSort(int *arr, int len)
{
	int count = 0;
	for(int i=0; i<len-1; i++)//需要多少趟
	{
		for(int j=0; j+1<len-i; j++)//控制两两比较   j指向两两比较的开始位置
		{
			if(arr[j] > arr[j+1])
			{
				int tmp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tmp;
			}
		}
		count++;

	}

	printf("%d\n",  count);
}
void Show(int arr[], int len)
{
	for(int i=0; i<len; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
int main()
{
	int arr[] = {12,2,39,88,4,6,25,232,62,221};
	BubbleSort(arr, sizeof(arr)/sizeof(arr[0]));
	Show(arr, sizeof(arr)/sizeof(arr[0]));
	return 0;
}

运行结果为

?进行优化：?

void BubbleSort(int *arr, int len)
{
	int count = 0;
	bool tag = true;//标记  首先赋初值为真
	//从头到尾遍历一般，没有交换操作，则可以认定完全有序
	//反过来说：只要有一次交换操作，则不能认定完全有序

	for(int i=0; i<len-1; i++)//需要多少趟
	{
		tag = true;//注意：不要忘，每一趟开始的时候，记得将tag重新置为true
		for(int j=0; j+1<len-i; j++)//控制两两比较   j指向两两比较的开始位置
		{
			if(arr[j] > arr[j+1])
			{
				int tmp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tmp;
				
				tag = false;
			}
		}
		count++;

		if(tag)//如果一趟跑完之后，发现tag没有变，还是真，则代表没有前面大于后面的情况发生，则已经完全有序
		{
			break;
		}
	}

	printf("%d\n",  count);
}
void Show(int arr[], int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
int main()
{
	int arr[] = { 12,2,39,88,4,6,25,232,62,221 };
	BubbleSort(arr, sizeof(arr) / sizeof(arr[0]));
	Show(arr, sizeof(arr) / sizeof(arr[0]));
	return 0;
}

运行结果：

?

?

?