|
|
Posted on 2009-03-24 15:02 赞劲小子 阅读(785) 评论(1) 编辑 收藏 引用 所属分类: 算法设计与分析
 #include "iostream.h"
  /**//**
 *冒泡排序
冒泡排序（Bubble Sorting）的基本思想是：设待排序n个元素存放在数组a[n]中,无序区范围
初始为(a(0),a(1),a(2), ,a[n-1]),冒泡排序方法是在当前无序区内,从最上面的元素a[0]开
始,对每两个相邻的元素a[i+1]和a[i](i=0,1,,n-1)进行比较,且使值较小的元素换至值较大
的元素之上(若a[i]>a[i+1],则a[i]和a[i+1]的值互换),这样经过一趟冒泡排序后,假设最后下移
的元素为a[k],则无序区中值较大的几个元素到达下端并从小到大依次存放在a[k+1],a[k+2],a[n-1]中,
这样无序区范围变为(a[0],a[1],a[2],,a[k])。在当前无序区内进行下一趟冒泡排序。这个过
程一直到某一趟排序中不出现元素交换的动作，排序结束。整个排序过程最多执行n-1遍。这种排序
方法是通过相邻元素之间的比较与交换，使值较小的元素逐渐从后部移向前部（从下标较大的单元
移向下标较小的单元），就象水底下的气泡一样逐渐向上冒。故称为冒泡排序法。
 **/
void bubble(int array[], int size);
int main(){
  int array[10] = {7,6,8,5,10,9,2,4,3,1};
bubble(array,10);
for(int i = 0; i < 10; i++)
cout << array[i] << ' ';
return 0;
}
void bubble(int array[], int size){
for(int pass = 0; pass < size - 1 ; pass++ )
for(int j = 0 ; j < size - 1; j++)
{
int temp;
if(array[j] > array[j + 1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
 }
}
}
改进后的冒泡排序 改进思想：比如用冒泡排序将4、5、7、1、2、3这6个数排序。在该列中，第二趟排序结束后，数组已排好序，但计算机此时并不知道已经反排 好序，计算机还需要进行一趟比较，如果这一趟比较，未发生任何数据交换，则知道已排序好，可以不再进行比较了。因而第三趟比较还需要 进行，但第四、五趟比较则是不必要的。为此，我们可以考虑程序的优化。 为了标志在比较中是否进行了，设一个布尔量flag。在进行每趟比较前将flag置成true。如果在比较中发生了数据交换，则将flag置为false，在 一趟比较结束后，再判断flag，如果它仍为true（表明在该趟比较中未发生一次数据交换）则结束排序，否则进行下一趟比较。
#include "iostream.h"
void bubble(int array[], int size);
int main(){
int array[10] = {7,6,8,5,10,9,2,4,3,1};
bubble(array,10);
for(int i = 0; i < 10; i++)
cout << array[i] << ' ';
return 0;
}
void bubble(int array[], int size){
bool tag;
for(int pass = 0; pass < size - 1; pass++ )
{
tag = true;
for(int j = 0 ; j < size - 1; j++)
{
int temp;
if(array[j] > array[j + 1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
tag = false;
}
}
if(tag == true)
return ;
}
}
Feedback
# re: 冒泡排序以及改进 回复 更多评论
2012-04-19 20:06 by
英文名www.ie10.net
|