初夏小谈：排序算法---冒泡排序（极致优化）

冒泡排序算法是我们学习数据结构时所接触到的第一个排序算法，因为其思想比较简单，易于理解，和其形象化的特点。也被我们称之为起泡排序。

冒泡排序就像鱼吐泡泡的过程，最大的最先浮上来一次是次大的。从第一个元素开始，将每两个之间进行比较，如果前面的大于后面的则将他们两个的位置进行交换，如果前面小于或者等于后者元素是则不交换。然后再拿比较后的大的元素继续和它后面的元素进行比较。（始终都是拿两个元素中比较大元素的去往后比较）直到后面没有元素。这样如果还不清楚那来一串数字来理解一下

刚开始时我们用j来指向前两个元素下标，注意：此时还没有比较

这是我们进行第一次比较并且将比较后的元素下标往后移动，第一次比较发现6是大于5的，所以不用交换

第二次比较时是将6和3进行比较发现6大就交换，j向后走一步

第三次比较时发现6是小于8的所以不用交换，只将j向后移动

第四次比较是8和9进行，发现9大则不用交换，只将j往后移一次



第五次比较是9和7进行比较，发现9比7大交换两个数，j往后走一步



第六次比较是9和3进行比较，发现9大则交换，至此j+1已经到数组最后一个元素，则j不在往后走，如果走则数组越界，是未定义行为。

这一趟下来将数组中最大元素移动到了最终的位置上。接下来就是循环上述步骤。

冒泡排序本质：每一趟都是将数组未排序的最大元素选出来放在最后的位置上

代码如下：

头文件：

#include<stdio.h>

//交换两个数
void SwapNum(int* ptr1, int* ptr2);

//冒泡排序
void BubbleSort(int array[], int size);

//打印数组
void PrintArray(int array[],int size);

函数体：

#include"BubbleSort.h"

//交换两个数
void SwapNum(int* ptr1, int* ptr2)
{
	int temp = *ptr1;
	*ptr1 = *ptr2;
	*ptr2 = temp;
}

//冒泡排序
void BubbleSort(int array[], int size)
{
	//冒泡排序走过的趟数
	for (int i = 0; i < size; i++)
	{
		//每趟排序
		for (int j = 0; j < size - 1; j++)
		{
			//大的数往后走，最终将最大的数排在最后
			if (array[j] > array[j + 1])
			{
				//交换两个数
				SwapNum(&array[j], &array[j + 1]);
			}
		}
	}
}


//打印数组
void PrintArray(int array[], int size)
{
	int i = 0;
	while(i < size)
	{
		printf("%d ", array[i]);
		i++;
	}
	printf("\n");
}

主函数：

#include"BubbleSort.h"
#include<stdlib.h>

int main()
{
	int array[] = { 5,6,3,8,9,7,3 };
	//size指数组的实际长度
	int size = sizeof(array) / sizeof(array[0]);
	//调用打印函数先将未排序数组打印一遍
	PrintArray(array, size);
	//进行冒泡排序
	BubbleSort(array, size);
	//将排序的结果打印出来
	printf("冒泡排序：");
	PrintArray(array, size);
	system("pause");
	return 0;
}

结果显示：

初夏小谈：排序算法---冒泡排序（极致优化）

冒泡算法优化：

至此我们搞定了冒泡排序算法，接下来想想在上面实现过程中可以优化吗？哪些是重复走过的？

我总结了一下三点：

优化①：每一趟排序都是从第一个元素到最后一个元素，这样很明显后面已经排好的元素会多次比较造成重复比较很明显不合适。对此可以对每趟排序做一下判断，发现每进行一趟排序后就有一个元素到最终的位置上，则不需要在后续的排序中再去比较它。所以可以优化每一趟排序的比较个数也就是size-1变为size-1-i

优化②：对于一个未知顺序的数组来说一切顺序皆有可能，所以假如当经过几趟排序后数组已经有序，而仍去继续循环比较这样不是白白浪费资源吗，对于一个小的数组来说几乎没什么影响，但是当是海量数据呢?所以加一个标志值，如果一趟排序会发生交换数则让标志值进行改变。然后去判断标志值是否改变来决定是否继续循环。

优化③：就是循环的次数，想想一共有N个数，我们需要循环N次吗？因为是交换比较所以当循环N-1此后后N-1个数已经有序，由冒泡得知此时第二个数一定是比第一个数大的所以无需再比较。循环N-1次足以

优化后的冒泡排序：

//冒泡排序
void BubbleSortS(int array[], int size)
{
	//冒泡排序走过的趟数
	for (int i = 0; i < size - 1; i++)
	{
		int k = 1;
		//每趟排序
		for (int j = 0; j < size - 1 - i; j++)
		{
			//大的数往后走，最终将最大的数排在最后
			if (array[j] > array[j + 1])
			{
				//交换两个数
				SwapNum(&array[j], &array[j + 1]);
				k = 0;
			}
		}

		//判断是否已经有序
		if (k == 1)
		{
			break;
		}
	}
}

需要注意的是：

1.循环的边界是否合适

2.j是从哪里开始

一、从时间复杂度上来看冒泡排序的平均时间复杂度是O(n^2),最快时间复杂度是O(n)也就是有序，最大时间复杂度也是O(n^2)就是逆序。空间复杂度是O(1)

二、冒泡排序是一种稳定的排序算法。它不会改变相同元素的相对位置

珍&源码

初夏小谈：排序算法---冒泡排序（极致优化）

冒泡排序本质：每一趟都是将数组未排序的最大元素选出来放在最后的位置上

相关推荐