冒泡排序及其高效优化（C语言版）

1.从头依次访问数组每个元素，进行相邻元素之间的交换

2.元素之间两两交换，把小的换到前面，大的放到后面。

3.所有元素交换完成后，一趟交换完成，此时最大的元素会到数组尾部。

4.反复执行以上步骤，直到所有元素都排序完。

结束条件：在任何一趟进行过程中，未出现交换。

注意点：冒泡算法通过双循环来控制跑的趟数和每趟需要比较的元素，即外层循环控制跑的趟数，内层循环控制需要比较的元素个数。

一趟最坏的情况是排好一个元素，所以n个元素需要n趟，因为剩最后一个元素时，已经排好序，所以最后需要n – 1趟。

编程思想：当解决某类问题没有思路时，可以借助实例进行分析。
eg：冒泡排序中，当不知道j的判断条件时，可以对实例进行分析，第一轮有10个元素，
进行10 – 1次交换，第二轮有10个元素，进行10 – 1 – j(此时的j为1) =8交换，
通过结果逆推出代码。

优化一：

假设我们现在排序arr[] = { 1, 2, 3, 4, 5, 6, 7, 9, 8 }这组数据，按照上面的排序方法，第一趟排序后将8 和9 已经交换有序，接下来的排序就是多余的，什么也没做。所以我们

可以在交换的地方加一个标记，如果那一趟排序没有交换元素，说明这组数据已经有序，不用再继续下去。


static void Swap(int*xp, int*yp){
	int temp = *xp;
	*xp = *yp;
	*yp = temp;
}
void BubbleSort(int arr[], int num){
	for (int i = 0; i < num - 1; i++){//交换的轮数//循环从0开始，因为数组元素的下标从0开始
		int flag = 1;
		for (int j = 0; j < num - i - 1; j++){//每一轮交换的次数
			if (arr[j] > arr[j + 1]){
				Swap(&arr[j], &arr[j + 1]);
				flag = 0;
			}
		}
		if (flag){
			break;
		}
	}
}

优化二：

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

注：第二种优化不需要使用flag,比较多余，如果最后交换位置为0，就已经说明没有交换了

static void Swap(int*xp, int*yp){
	int temp = *xp;
	*xp = *yp;
	*yp = temp;
}
void BubbleSort(int arr[], int num){
	for (int i = 0; i < num - 1; i++){
        int end = num -1;
		int pos = 0;
		for (int j = 0; j < end; j++){
			if (arr[j] > arr[j + 1]){
				Swap(&arr[j], &arr[j + 1]);
				pos = j;//交换元素，记录最后一次交换的位置
			}
		}
        end = pos;//下一次比较到记录位置即可
	}
}

优化三：

双向冒泡排序，又叫鸡尾酒排序：它的过程是：先从左往右比较一次，再从右往左比较一次，然后又从左往右比较一次，以此类推。

优点：能够再特定条件下，减少排序的回合数；缺点：代码量增大一倍。使用场景：大部分元素已经有序的情况下。

他是为了优化前面的大部分元素都已经排好序的数组，例如对于数组[2,3,4,5,6,7,8,1]如果使用普通的冒泡排序，需要比较7次；而换成双向冒泡排序，只需比较三次。

简单起见，先看下单纯的双向冒泡排序（没有结合前面两种优化）：

void BubbleSort(int arr[], int num){
	int left = 0;
	int right = num - 1;
	while (left < right){
		//奇数轮，从左向右比较交换
		for (int i = left; i < right; i++){
			if (arr[i] > arr[i + 1]){
				Swap(&arr[i], &arr[i + 1]);
			}
		}
		right--;
		//偶数轮，从右向左比较交换
		for (int i = right; i > left; i--){
			if (arr[i] < arr[i - 1]){
				Swap(&arr[i], &arr[i - 1]);
			}
		}
		left++;
	}
}

最终优化：优化一 + 优化二 + 优化三

void BubbleSort(int arr[], int num){
	int left = 0;
	int right = num - 1;
	int lastSwapIndex = 0;
	int flag = 1;
	while (left < right){
		//奇数轮，从左向右比较交换
		for (int i = left; i < right; i++){
			if (arr[i] > arr[i + 1]){
				Swap(&arr[i], &arr[i + 1]);
				lastSwapIndex = i;
			}
		}
		right = lastSwapIndex;//将最后一次交换的位置作为右边界
		if (flag){
			break;
		}
		//偶数轮，从右向左比较交换
		for (int i = right; i > left; i--){
			if (arr[i] < arr[i - 1]){
				Swap(&arr[i], &arr[i - 1]);
				lastSwapIndex = i;
			}
		}
		left = lastSwapIndex;//将最后一次交换的位置作为左边界
		if (flag){
			break;
		}
	}
}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/110987.html

冒泡排序及其高效优化（C语言版）

优化一：

优化二：

优化三：

相关推荐