冒泡排序介绍

• 列表每两个相邻的数，如果前面比后面大（升序），则交换这两个数。
• 一趟排序完成后，则无序区减少一个数，有序区增加一个数。
• 时间复杂度：O(n^2)

#include<stdio.h>

void Print(int li[], int n)
{
	int i = 0;
	for (i = 0; i < n; i++)
	{
		printf("%d ", li[i]);
	}
	printf("n");
}

void bubble_sort(int li[], int n)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < n - 1; i++)    //第i趟
	{
		for (j = 0; j < n - i - 1; j++)
		{
			if (li[j] > li[j + 1])	//大于号——>升序，小于号——>降序
			{
				int tmp = li[j];
				li[j] = li[j + 1];
				li[j + 1] = tmp;
			}
		}
		Print(li, n);//验证
	}
	Print(li, n);//验证
}

int main()
{
	int li[] = { 3,5,8,6,9,2,4,1,7 };
	int n = sizeof(li) / sizeof(li[0]);
	bubble_sort(li, n);

	return 0;
}

• 冒泡排序-优化：如果冒泡排序中的一趟排序没有发生交换，则说明列表已经有序，可以直接结束算法。
• 操作：在外重循环增加一个标志位exchange
• 时间复杂度：O(nlogn)

#include<stdio.h>

#define FALSE 0
#define TURE 1

void Print(int li[], int n)
{
	int i = 0;
	for (i = 0; i < n; i++)
	{
		printf("%d ", li[i]);
	}
	printf("n");
}

void bubble_sort(int li[], int n)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < n - 1; i++)    //第i趟
	{
		int exchange = FALSE;	//标志位
		for (j = 0; j < n - i - 1; j++)
		{
			if (li[j] > li[j + 1])	//大于号——>升序，小于号——>降序
			{
				int tmp = li[j];
				li[j] = li[j + 1];
				li[j + 1] = tmp;
				exchange = TURE;
			}
		}
		if (!exchange)
		{
			break;
		}
		Print(li, n);//验证
	}
	Print(li, n);//验证
}

int main()
{
	int li[] = { 7,8,9,1,2,3,4,5,6 };	//冒泡三趟即得到有序列表
	int n = sizeof(li) / sizeof(li[0]);
	bubble_sort(li, n);

	return 0;
}