冒泡排序是最基本的排序算法，常被做为内部排序的第一个排序算法进行讲解。它的原理非常简单，只是一个两层循环，每次将最大或最小的放到数组最后。
算法如下(b为数组的起始位置， e为数组的结果位置）：
这个函数返回两个整数比较以及进行交换的次数。如将序列5, 3, 1, 665, 77, 66, 44, 11, 10, 9, 8, 6
进行排序，bubble返回93。
这个算法的时间复杂度为 O(n^2)。
而时间复杂度由两部分组成：比较和交换
比较：
最好 平均 最差
O(n^2) O(n^2) O(n^2)
交换
最好 平均 最差
0 O(n^2) O(n^2)
也就是说bubble在最好的情况不需要进行交换，那还要做复杂度为O(n^2)的比较不是太浪费了吗？
下面给出一个bubble sort的改良版本，这个算法在数据基本有序时的时间复杂度为 O(n)。最差情况
和bubble函数一样，也是O(n^2)。
这个算法的主要思想是在两个整数最后一次交换后，在前一个整数后面的所有整数都是排序的，因此在
第一层循环的i变化时，无需减1，而只需将i置成这个整数所在的位置。从而第一层循环的次数就不一定是
n - 1，当待排序数组已经是有序时，第一层循环只循环一次。算法实现如下。
再用序列5, 3, 1, 665, 77, 66, 44, 11, 10, 9, 8, 6试一试，bubble_new返回65，比bubble快了30%。
完整的代码如下：
算法如下(b为数组的起始位置， e为数组的结果位置）：
int bubble(
int data[],
int b,
int e)
{
int i, j, n = 0;
for(i = e; i > b; i--)
for(j = b; j < i; j++)
{
n++;
if(data[j] < data[j + 1])
{
swap(&data[j], &data[j + 1]);
n++;
}
}
return n;
}
{
int i, j, n = 0;
for(i = e; i > b; i--)
for(j = b; j < i; j++)
{
n++;
if(data[j] < data[j + 1])
{
swap(&data[j], &data[j + 1]);
n++;
}
}
return n;
}
这个函数返回两个整数比较以及进行交换的次数。如将序列5, 3, 1, 665, 77, 66, 44, 11, 10, 9, 8, 6
进行排序，bubble返回93。
这个算法的时间复杂度为 O(n^2)。
而时间复杂度由两部分组成：比较和交换
比较：
最好 平均 最差
O(n^2) O(n^2) O(n^2)
交换
最好 平均 最差
0 O(n^2) O(n^2)
也就是说bubble在最好的情况不需要进行交换，那还要做复杂度为O(n^2)的比较不是太浪费了吗？
下面给出一个bubble sort的改良版本，这个算法在数据基本有序时的时间复杂度为 O(n)。最差情况
和bubble函数一样，也是O(n^2)。
这个算法的主要思想是在两个整数最后一次交换后，在前一个整数后面的所有整数都是排序的，因此在
第一层循环的i变化时，无需减1，而只需将i置成这个整数所在的位置。从而第一层循环的次数就不一定是
n - 1，当待排序数组已经是有序时，第一层循环只循环一次。算法实现如下。
int bubble_new(
int data[],
int b,
int e)
{
int i, j, n = 0, k;
for(i = e; i > b; i = k)
{
k = b;
for(j = b; j < i; j++)
{
n++;
if(data[j] < data[j + 1])
{
k = j;
swap(&data[j], &data[j + 1]);
n++;
}
}
}
return n;
}
{
int i, j, n = 0, k;
for(i = e; i > b; i = k)
{
k = b;
for(j = b; j < i; j++)
{
n++;
if(data[j] < data[j + 1])
{
k = j;
swap(&data[j], &data[j + 1]);
n++;
}
}
}
return n;
}
再用序列5, 3, 1, 665, 77, 66, 44, 11, 10, 9, 8, 6试一试，bubble_new返回65，比bubble快了30%。
完整的代码如下：
#include <stdio.h>
void output_array( int data[], int n)
{
int i;
for(i = 0; i < n; i++)
printf( " %d ", data[i]);
printf( " \n ");
}
void swap( int *a, int *b)
{
int x;
x = *a;
*a = *b;
*b = x;
}
int bubble( int data[], int b, int e)
{
int i, j, n = 0;
for(i = e; i > b; i--)
for(j = b; j < i; j++)
{
n++;
if(data[j] < data[j + 1])
{
swap(&data[j], &data[j + 1]);
n++;
}
}
return n;
}
int bubble_new( int data[], int b, int e)
{
int i, j, n = 0, k;
for(i = e; i > b; i = k)
{
k = b;
for(j = b; j < i; j++)
{
n++;
if(data[j] < data[j + 1])
{
k = j;
swap(&data[j], &data[j + 1]);
n++;
}
}
}
return n;
}
int main()
{
int data1[] = { 5, 3, 1, 665, 77, 66, 44, 11, 10, 9, 8, 6};
int data2[] = { 5, 3, 1, 665, 77, 66, 44, 11, 10, 9, 8, 6};
output_array(data1, 12);
printf( " %d \n ", bubble(data1, 0, 11));
output_array(data1, 12);
printf( " -----------------------------------\n ");
output_array(data2, 12);
printf( " %d \n ", bubble_new(data2, 0, 11));
output_array(data2, 12);
return 0;
}
void output_array( int data[], int n)
{
int i;
for(i = 0; i < n; i++)
printf( " %d ", data[i]);
printf( " \n ");
}
void swap( int *a, int *b)
{
int x;
x = *a;
*a = *b;
*b = x;
}
int bubble( int data[], int b, int e)
{
int i, j, n = 0;
for(i = e; i > b; i--)
for(j = b; j < i; j++)
{
n++;
if(data[j] < data[j + 1])
{
swap(&data[j], &data[j + 1]);
n++;
}
}
return n;
}
int bubble_new( int data[], int b, int e)
{
int i, j, n = 0, k;
for(i = e; i > b; i = k)
{
k = b;
for(j = b; j < i; j++)
{
n++;
if(data[j] < data[j + 1])
{
k = j;
swap(&data[j], &data[j + 1]);
n++;
}
}
}
return n;
}
int main()
{
int data1[] = { 5, 3, 1, 665, 77, 66, 44, 11, 10, 9, 8, 6};
int data2[] = { 5, 3, 1, 665, 77, 66, 44, 11, 10, 9, 8, 6};
output_array(data1, 12);
printf( " %d \n ", bubble(data1, 0, 11));
output_array(data1, 12);
printf( " -----------------------------------\n ");
output_array(data2, 12);
printf( " %d \n ", bubble_new(data2, 0, 11));
output_array(data2, 12);
return 0;
}
本文转自银河使者博客园博客，原文链接http://www.cnblogs.com/nokiaguy/archive/2008/05/16/1201086.html如需转载请自行联系原作者
银河使者
