# 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
}``````

``````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
}``````

``````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 = ...
}``````

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;
}
}``````

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

;