冒泡法排序

你的名字 2022-08-04 01:59 227阅读 0赞

冒泡法排序是一种比较简单的排序算法，但同时它也是一种效率比较低的排序算法。

当要将元素进行单调非减排序时，冒泡法排序的基本过程为：

![Center][]

其基本思想是每一趟排序就将需要排序的序列的最大值像泡泡一样“冒”到排序的最上面，而下趟排序时就将需要排序的序列长度减1.

算法比较简单，下面给出一个最直观的实现：

void bubble_sort1(int arr[],int len)
    {
    	int temp;
    	for (int i = 0; i < len; i++)
    	{
    		for (int j = 0; j < len-1-i; j++)
    		{
    			if (arr[j + 1] < arr[j])
    			{
    				temp = arr[j + 1];
    				arr[j + 1] = arr[j];
    				arr[j] = temp;
    			}
    		}
    	}
    
    }

代码中输入分别为数组首地址和数组长度，代码中利用两个for循环来实现冒泡法排序，外层for来控制循环的次数，内层for每一次将需要排序的序列中的最大的数“冒”到需要排序的序列最前面。

下面还有另一种冒泡排序的实现，从算法分析的角度来看，它们的运行时间都是O(n^2)，但就平均情况而言，下面的实现会更好，同时也更加合理。

想象一下这个特殊的情形，如果上面程序的输入是一个已经排好序的数组，如\{1,2,3,4,5\}，上面的程序无法判断这种已经排好序的情况，它每次都傻傻地去比较，然后将最大的数“冒”到最上面，无论给出的序列情况如何。

下面是第二种冒泡排序的实现：

void bubble_sort2(int arr[], int len)
    {
    	int temp,last_i, end=len-1;
    	while (end>0)
    	{
    		last_i = 0;
    		for (int j = 0; j < end; j++)
    		{
    			if (arr[j + 1] < arr[j])
    			{
    				temp = arr[j + 1];
    				arr[j + 1] = arr[j];
    				arr[j] = temp;
    				last_i = j;//记录最后一个需要交换的关键码的下标，下一次重排的长度为从起始下标到这里（last_i）
    			}
    		}
    		end = last_i;//如果这次循环没有交换，则数组已经有序了
    	}
    
    }

第二个实现利用end变量来检测数组是否已经有序，这会在每一趟排序结束后进行检测，如果已经有序，程序就退出，否则继续下一趟排序。检测数组已经有序的原理是使end变量的值为最近一次发生元素交换的元素的下标，初始时end的值为数组首元素的下标。只要end的值为数组首元素的下标，说明这趟排序并没有什么进行交换，也就说明整个数组都已经有序了，while退出，整个函数结束。

[Center]: /images/20220731/9e88edaf511047538a7b34c8bb8a5bea.png