复习数据结构：排序算法（二）——冒泡排序

￡神魔★判官ぃ 2022-08-07 01:52 183阅读 0赞

这篇复习冒泡排序。

**冒泡排序也是一种稳定排序、内排序。  
冒泡排序的基本思想：对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。  
插入排序比冒泡排序快！**

上面说的是普通的冒泡排序算法，时间复杂度是O(n^2)，这种方法只能一趟排序操作只能找到一个最大值或最小值，消耗时间太多。

**改进方法1：我们可以让每趟排序中进行正向和反向两遍冒泡的方法，一次就可以同时得到最大值和最小值，这样一来排序的趟数减少了一半。这种方法形象来说就像振荡小球，如果两端已经选择出来最大值和最小值，那么下一趟排序的时候就会缩小排序的距离，后面振荡的幅度就会减小，一直当幅度为0，是不是很像振荡小球由于阻尼的存在，不断减少幅度，直至停止。**

**改进方法2：在每趟排序过程中，用标记位记录每趟排序中最后一次交换的位置，如果最后一次交换的位置在0，那么就说明整个数组排序完毕。这种改进的思想是把先前排序的先验信息使用上，减少排序的次数。**

实现代码：

#include<iostream>
    using namespace std; 
    
    void BubbleSort(int a[], int n)
    {
    	for(int i = 0; i < n-1; i++)
    	{
    		for(int j = 0; j < n-i-1; j++)
    		{
    			if(a[j] > a[j+1])
    				swap(a[j], a[j+1]); 
    		}
    	}
    }
    
    void BubbleSort_2(int a[], int n)
    {
    	int low = 0; 
    	int high = n-1; 
    	int j; 
    	while(low < high)
    	{
    		for(j = low; j < high; j++)
    		{
    			if(a[j] > a[j+1])
    				swap(a[j], a[j+1]); 
    		}
    		high--; 
    
    		for(j = high; j > low; j--)
    		{
    			if(a[j] < a[j-1])
    				swap(a[j], a[j-1]); 
    		}
    		low++; 
    	}
    }
    
    void BubbleSort_3(int a[], int n)
    {
    	int i = n-1;  // 初始时的最后交换位置
    	while(i > 0)  //  直到交换位置为0
    	{
    		int pos = 0; 
    		for(int j = 0; j < i; j++)  // 每趟排序只进行到上次最后交换的位置
    		{
    			if(a[j] > a[j+1])
    			{
    				pos = j; 
    				swap(a[j], a[j+1]);
    			}
    		}
    		i = pos; 
    	}
    }
    
    
    int main()
    {
    	int a[] = {1, 4, 8, 6, 2, 7}; 
    	BubbleSort_3(a, 6); 
    	for(int i = 0; i< 6; i++)
    		cout<<a[i]<<' '; 
    	cout<<endl; 
    
    	return 0; 
    }