排序算法入门之冒泡排序优化

ゝ一世哀愁。 2022-05-26 11:43 201阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    void swap(int *a, int *b);
    int main()
    {
    	int    array[10] = { 15, 225, 34, 42, 52, 6, 7856, 865, 954, 10 };
    	int    i, j;
    	int array_length = sizeof(array) / sizeof(array[0]);
    	for (i = 0; i < array_length; i++)//sizeof(array) / sizeof(array[0])数组元素个数
    	{
    		//每一次由底至上地上升
    		for (j = array_length - 1; j > i; j--)
    		{
    			if (array[j] < array[j - 1])
    			{
    				swap(&array[j], &array[j - 1]);
    			}
    		}
    	}
    	for (i = 0; i < 10; i++)
    	{
    		printf("%d\n", array[i]);
    	}
    
    	//优化的冒泡排序算法
    	int    array1[10] = { 2, 1, 3, 4, 5, 6, 7, 8, 9, 10 };
    	int    flag = 1;   //设置标记变量  
    	for (i = 0; i < 10 && flag; i++)
    	{
    		flag = 0;      //只要flag在下一次外循环条件检测的时候值为0，就说明已经排好序，不用继续循环  
    		/*
    		当第一次循环,从10 与 9 判断，到 1 和2判断,发生交换,数组变成{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}后,这个时候flag为1,
    		进入下一次循环,发现循环后,没有发生交换,说明排序完成,不用继续循环,直接弹出循环
    		*/
    		for (j = 9; j > i; j--)
    		{
    			if (array1[j] < array1[j - 1])//从小到大
    			{
    				swap(&array1[j], &array1[j - 1]);
    				flag = 1;   //如果有交换，就将标记变量赋1  
    			}
    		}
    	}
    
    	for (i = 0; i < 10; i++)
    	{
    		printf("%d\n", array1[i]);
    	}
    
    	system("pause");
    	return    0;
    }
    void swap(int *a, int *b)
    {
    	int    temp;
    	temp = *a;
    	*a = *b;
    	*b = temp;
    }

参考：[排序算法入门之冒泡排序][Link 1]

这篇文章是对[上一篇文章][Link 2]中的冒泡排序进行优化

先来说说，冒泡排序哪些地方需要优化：

根据[上一篇文章][Link 2]的内容，可以知道冒泡排序的核心是两两对比进行交换。如果有一个无序数列（2，1，3，4，5，6，7，8，9，10）

按照[上一篇文章][Link 2]的代码，从第一次循环交换后的操作，可以说都是没必要的。所以，这些操作就是我们需要优化的地方。

那么如何优化？

通过观察可以看到，造成没必要的操作主要原因是后面8个数的顺序都已经是有序。所以，我们可以通过设置一个标记变量，标记数列中的数是否在循环结束前就已经排好序

[Link 1]: https://blog.csdn.net/cbs612537/article/details/8294960
[Link 2]: http://blog.csdn.net/cbs612537/article/details/8294960