3种冒泡排序

第一种:最基本的解法


void bubble_sort1( int a[], int size )
{
	bool swapped = true;
	int n = size;
	
	while ( swapped ) {
		swapped = false;
		for ( int i = 0; i < n - 1; i++ ) {
			if ( a[i] > a[i+1] ) {
				int tmp;
				tmp = a[i];
				a[i] = a[i+1];
				a[i+1] = tmp;
				
				swapped = true;
			}//if
		}//for
	}//while
}

第一种解法每次从第一个元素开始把第i+1个最大的元素放到它应有的位置,而每次却是比较所有的n个元素,明显每次和之前已经排好的元素比较属于多余,引出解法2:每次排序后n自减1。

第二种:与咱们通常写的二层for循环的冒泡排序一样

void bubble_sort2( int a[], int size )
{
	bool swapped = true;
	int n = size;
	
	while ( swapped ) {
		swapped = false;
		for ( int i = 0; i < n - 1; i++ ) {
			if ( a[i] > a[i+1] ) {
				int tmp;
				tmp = a[i];
				a[i] = a[i+1];
				a[i+1] = tmp;
				
				swapped = true;
			}//if
		}
		n = n - 1;
	}//while
}


上述解法1,2综合起来就是我们经常写的二重for循环的冒泡排序,如下所示:

下面就是我们通常写的冒泡排序(摘自中文维基百科)

void bubble_sort(int a[], const int size)
{
        bool flag = true;
        int temp = 0; /* Temporary value for swapping two elements */
 
        for (int i = 0; i < size - 1; i ++)
        {
                flag = true;
                for (int j = 0; j < size - i - 1; j ++)
                {
                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag = false;
                        } // end if
                } // end for j = ...
 
                if (flag == true)
                        break;
 
        } // end for i = ...
}

然后是第三种解法:此种解法原理同样是减少每次排序的个数。由于我们每次交换两个数a[i],a[i+1]时,都是因为a[i]<a[i+1] 这样总有i所在位置的元素值小于它后面的元素,由此可以减小n的值。

具体精确描述为:

More generally, it can happen that more than one element is placed in their final position on a single pass. In particular, after every pass, all elements after the last swap are sorted, and do not need to be checked again. This allows us to skip over a lot of the elements, resulting in about a worst case 50% improvement in comparison count (though no improvement in swap counts), and adds very little complexity because the new code subsumes the "swapped" variable:

To accomplish this in pseudocode we write the following:


void bubble_sort( int a[], const int size )
{
	int n = size;
	int newn = 0;
	int swap = 0;
	while ( n ) {
		newn = 0;
		for ( int i = 0; i < n - 1; i++ ) {
			if ( a[i] > a[i+1] ) {
				/*太慢
				a[i] = a[i] + a[i+1] ;
				a[i+1] = a[i] - a[i+1];
				a[i] = a[i] - a[i+1];*/
				int tmp;
				tmp = a[i];
				a[i] = a[i+1];
				a[i+1] = tmp;

				newn = i+1;
			}
		}
		n = newn;
	}
}


尽管bubble_sort从理解上和实施上是最简单的排序算法,但是它O(n2)的时间复杂度意味着在lists有更多的元素时,该算法的效率是非常低的。即使在

那些简单的O(n2)时间复杂度的排序算法中,比如插入排序也通常被认为比冒泡排序更优。

由于冒泡排序的简单性,它经常被用来作为介绍算法的概念。。。。。省略。。

此文只是在看《数据结构与算法分析》引论时突然想写写,读者朋友们还是应该掌握其他更高级的排序算法。

Reference: http://en.wikipedia.org/wiki/Bubble_sort


;