经典排序算法----冒泡排序算法及其优化(稳定)

冒泡排序(稳定

《经典排序算法----冒泡排序算法及其优化(稳定)》

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

最好情况O(n),最坏情况O(n2),平均情况O(n2),辅助空间O(1)

概念:

设数组长度为N。

  1. 比较相邻的前后二个数据,如果前面数据大于后面的数据,就将二个数据交换。
  2. 这样对数组的第0个数据到N-1个数据进行一次遍历后,最大的一个数据就“沉”到数组第N-1个位置。
  3. N=N-1,如果N不为0就重复前面二步,否则排序完成。

算法实现

按照定义:

#include<stdio.h>
#include<stdlib.h>

void Show(int *arr, int n)
{
	printf("数组排序:");
	for (int i = 0; i < n; i++)
		printf("%-3d", arr[i]);
	printf("\n");
}

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

void BubbleSort(int *arr, int n)
{
	for (int i = 0; i < n; i++)
		for (int j = 1; j < n - i; j++)
			if (arr[j - 1] > arr[j])
				Swap(&arr[j - 1], &arr[j]);
}

void main()
{
	int arr[10] = { 9, 8, 7, 6, 4, 5, 3, 1, 2, 0 };
	Show(arr, 10);
	BubbleSort(arr, 10);
	Show(arr, 10);

	system("pause");
}

运行结果:

数组排序:9  8  7  6  4  5  3  1  2  0
数组排序:0  1  2  3  4  5  6  7  8  9
请按任意键继续. . .

优化一:

下面对其进行优化,设置一个标志,如果这一趟发生了交换,则为true,否则为false。明显如果有一趟没有发生交换,说明排序已经完成。

算法实现:

#include<stdio.h>
#include<stdlib.h>

void Show(int *arr, int n)
{
	printf("数组排序:");
	for (int i = 0; i < n; i++)
		printf("%-3d", arr[i]);
	printf("\n");
}

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

void BubbleSort2(int *arr, int n)
{
	int j, k;
	int flag;

	k = n;
	flag = 1;

	while (flag)
	{
		flag = 0;
		for (j = 1; j < k; j++)
			if (arr[j - 1] > arr[j])
			{
				Swap(&arr[j - 1], &arr[j]);
				flag = 1;
			}
		k--;
	}
}

void main()
{
	int arr[10] = { 9, 8, 7, 6, 4, 5, 3, 1, 2, 0 };
	Show(arr, 10);
	BubbleSort2(arr, 10);
	Show(arr, 10);

	system("pause");
}

运行结果:

数组排序:9  8  7  6  4  5  3  1  2  0
数组排序:0  1  2  3  4  5  6  7  8  9
请按任意键继续. . .

一种更为直观的实现方法:

void BubbleSort2(int *arr, int n)
{
	bool falg = true;

	for (int i = 0; i < n; ++i)
	{
		falg = false;
		for (int j = 1; j < n - i; ++j)
		{
			if (arr[j - 1] > arr[j])
			{
				falg = true;//如果有一趟数据未发生交换,则说明冒泡已经完成
				Swap(arr + j - 1, arr + j);
			}
		}
		if (!falg)
			break;
	}
}

优化二:

再做进一步的优化。如果有100个数的数组,仅前面10个无序,后面90个都已排好序且都大于前面10个数字,那么在第一趟遍历后,最后发生交换的位置必定小于10,且这个位置之后的数据必定已经有序了,记录下这位置,第二次只要从数组头部遍历到这个位置就可以了。

#include<stdio.h>
#include<stdlib.h>

void Show(int *arr, int n)
{
	printf("数组排序:");
	for (int i = 0; i < n; i++)
		printf("%-3d", arr[i]);
	printf("\n");
}

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

void BubbleSort3(int *arr, int n)
{
	int j, k;
	int flag;

	flag = n;
	while (flag > 0)
	{
		k = flag;
		flag = 0;
		for (j = 1; j < k; j++)
			if (arr[j - 1] > arr[j])
			{
				Swap(&arr[j - 1], &arr[j]);
				flag = j;
			}
	}
}

void main()
{
	int arr[10] = { 9, 8, 7, 6, 4, 5, 3, 1, 2, 0 };
	Show(arr, 10);
	BubbleSort3(arr, 10);
	Show(arr, 10);

	system("pause");
}

运行结果:

数组排序:9  8  7  6  4  5  3  1  2  0
数组排序:0  1  2  3  4  5  6  7  8  9
请按任意键继续. . .

引自<http://blog.csdn.net/morewindows/article/details/6657829>

    原文作者:排序算法
    原文地址: https://blog.csdn.net/qianqin_2014/article/details/51207800
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞