C/C++冒泡排序4种优化方法

怼烎@ 2022-11-17 14:44 127阅读 0赞

冒泡排序应该是大多数人接触的第一种排序方法，虽然它的时间复杂度为O（n^2），但是它简单易懂，代码复杂度低，所以仍有很大的用武之地。最近在总结排序算法，决定重温下冒泡排序，以及它的优化方法。

冒泡排序的原理以及排序过程参考：[冒泡排序][Link 1]，[三分钟彻底理解冒泡排序][Link 2]

冒泡排序的一些属性：

普通冒泡排序：

void myBubleSort1(int * nums, int len) {
    	int temp;
    	for (int i = 0; i < len; ++i) {
    		for (int j = 0; j < len-i-1; ++j) {
    			if (nums[j] > nums[j+1]) {
    				temp = nums[j];
    				nums[j] = nums[j+1];
    				nums[j+1] = temp;
    			}
    		}
    	}
    }

# 优化1：使用异或运算交换两个数 #

在冒泡循环中，我们要交换两个变量的值，通常是使用一个临时变量来辅助交换过程。在C++中可以使用swap()函数。如果交换的值是整数，我们可以省略这个临时变量，使用异或运算符交换两个变量的值：

a和b的值进行交换：

a = a^b;
    b = b^a;
    a = a^b;

代码实现：

void myBubleSort2(int * nums, int len) {
    	for (int i = 0; i < len; ++i) {
    		for (int j = 0; j < len - i - 1; ++j) {
    			if (nums[j] > nums[j + 1]) {
    				nums[j] = nums[j] ^ nums[j + 1];
    				nums[j + 1] = nums[j + 1] ^ nums[j];
    				nums[j] = nums[j] ^ nums[j + 1];
    			}
    		}
    	}
    }

# 优化2：设置排序完成的标志 #

冒泡排序需要有两层循环，无论数组是否排好序，都会完成这两层循环，对于最差的情况，比如\[9,8,7,6,5,4\]，对其进行升序排序，这两层循环必不可少；但是对于\[9,1,2,3,4,5\]这种情况，第一遍循环结束后，整个数组就已经是升序排列的了，但是普通的冒泡排序还会继续进行循环遍历比较，这就对做了不少无用功。所以需要设置一个排序完成的标志，如果排序已经完成，就没必要再继续循环遍历了，直接跳出循环。

void myBubleSort3(int * nums, int len) {
    	bool isSwapped;
    	for (int i = 0; i < len; ++i) {
    		isSwapped = false;
    		for (int j = 0; j < len - i - 1; ++j) {
    			if (nums[j] > nums[j + 1]) {
    				nums[j] = nums[j] ^ nums[j + 1];
    				nums[j + 1] = nums[j + 1] ^ nums[j];
    				nums[j] = nums[j] ^ nums[j + 1];
    				isSwapped = true;
    			}
    		}
    		if(!isSwapped) break;
    
    	}
    }

# 优化3：跳过无意义的比较 #

优化一仅仅适用于连片有序而整体无序的数据(例如：1， 2，3 ，4 ，7，6，5)。但是对于前面大部分是无序而后边小半部分有序的数据(1，2，5，7，4，3，6，8，9，10)排序效率也不可观，对于种类型数据，我们可以继续优化。既我们可以记下最后一次交换的位置，后边没有交换，必然是有序的，然后下一次排序从第一个比较到上次记录的位置结束即可。

![70][]

void myBubleSort4(int * nums, int len) {
    	bool isSwapped;
    	int lastSwap = 0;
    	int k = len - 1;
    	for (int i = 0; i < len; ++i) {
    		isSwapped = false;
    		for (int j = 0; j < k; ++j) {
    			if (nums[j] > nums[j + 1]) {
    				nums[j] = nums[j] ^ nums[j + 1];
    				nums[j + 1] = nums[j + 1] ^ nums[j];
    				nums[j] = nums[j] ^ nums[j + 1];
    				isSwapped = true;
    				//lastSwap之后的数都是排好序的
    				lastSwap = j;
    			}
    		}
    		if (!isSwapped) break;
    		k = lastSwap;
    	}
    }

# 优化4 #

优化3的效率有很大的提升，还有一种优化方法可以继续提高效率。大致思想就是一次排序可以确定两个值，正向扫描找到最大值交换到最后，反向扫描找到最小值交换到最前面。例如：排序数据1，2，3，4，5，6，0

void BubbleSort(int arr[], int len)
    {
    	int i = 0;
    	int j = 0;
    	int n = 0;//同时找最大值的最小需要两个下标遍历
    	int flag = 0;
    	int pos = 0;//用来记录最后一次交换的位置
    	int k = len - 1;
    	for (i = 0; i < len - 1; i++)//确定排序趟数
    	{
    		pos = 0;
    		flag = 0;
    		//正向寻找最大值
    		for (j = n; j < k; j++)//确定比较次数
    		{
    			if (arr[j]>arr[j + 1])
    			{
    				//交换
    				int tmp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = tmp;
    				flag = 1;//加入标记
    				pos = j;//交换元素，记录最后一次交换的位置
    			}
    		}
    		if (flag == 0)//如果没有交换过元素，则已经有序,直接结束
    		{
    			return;
    		}
    		k = pos;//下一次比较到记录位置即可
    		//反向寻找最小值
    		for (j = k; j > n; j--)
    		{
    			int tmp = arr[j];
    			arr[j] = arr[j - 1];
    			arr[j - 1] = tmp;
    			flag = 1;
    		}
    		n++;
    		if (flag == 0)//如果没有交换过元素，则已经有序,直接结束
    		{
    			return;
    		}
    	}
    }

参考文章：[【排序】：冒泡排序以及三种优化][Link 3]

[Link 1]: https://www.cnblogs.com/jyroy/p/11248691.html
[Link 2]: https://www.cnblogs.com/bigdata-stone/p/10464243.html
[70]: /images/20221022/1a2ee0be678f411da2be88ada96e09af.png
[Link 3]: https://blog.csdn.net/hansionz/article/details/80822494