现在的位置: 首页 > 自动控制 > 工业·编程 > 正文

冒泡排序

2012-08-20 06:45 工业·编程 ⁄ 共 2471字 ⁄ 字号 暂无评论

冒泡排序又称起泡排序,这是一种简单效率最低的排序,也是大家非常熟悉。
下面看看,冒泡排序的是怎样工作:
我认为这种排序分为两两种:向上冒泡和向下冒泡:

一,向上冒泡:也就满足条件的向上冒泡,看一组数9 8 6 7 4
(假设是从小到大排序,反之一样)
因为是向上冒泡也就小的数往前走。

第一躺:4 9 8 6 7
第二躺:4 6 9 8 7
第三躺:4 6 7 9 8
第四躺:4 6 7 8 9
每一躺是把相邻的数比较,以第一躺为例:初始为9 8 6 7 4,

先让4冒到7前:9 8 6 4 7
再让4冒到6前:9 8 4 6 7
再让4冒到8前:9 4 8 6 7
再让4冒到9前:4 9 8 6 7
以后每躺也一样
分析算法:这样的做的最坏情况就是所有数都要交换。复杂度为第一躺要交换n-1次,第二躺要交换n-2次(第二躺不要与第一躺交换?因为第一躺已将最小的数放在第1位),第n-1躺要交换1次,只要交换n-1次,原因是把n-1数都冒到前面,那最后一个数必为最大数。所以最坏情况要交换:n-1+n-2+...2+1=(n-1+1)*(n-1)/2=n*(n-1)/2,大O为O(n2)
分析完毕下面是C++代码:

/*****************************************************
*排序之一:冒泡排序算法(Bubble Sort)
*排序思想:复杂度最高,最简单的交换排序,依次比较相邻的
*两个数,将大数放在前面,小数放在后面。
*****************************************************/
#include <iostream>
#include <ctime>
#define ANRAY_SIZE 5
#define RANGE 80

using namespace std;

template<typename T>
void BubbleSort(T *,unsigned int);

int main()
{
srand(unsigned(time(NULL)));
int a[ANRAY_SIZE];

//随机赋值
for (int i = 0;i < ANRAY_SIZE ; i++)
      a[i] = rand() % RANGE + 1;
     
    //排序前
for (int i = 0;i < ANRAY_SIZE; i++)
      cout<<a[i]<<" ";
    cout<<endl;
     
    BubbleSort(a,ANRAY_SIZE);

//排序后
for (int i = 0;i < ANRAY_SIZE; i++) cout<<a[i]<<" ";
return 0;
}/***********************************************/

//冒泡排序1,向上冒
template<typename T>
void BubbleSort(T* anr,unsigned int SIZE)
{
for (int pass = 1;pass < SIZE ; pass++)
{
   for (int i = SIZE - 1;i > pass-1 ; i--)
   {
    if (anr[i] > anr[i-1])
    {
     T temp = anr[i];
     anr[i] = anr[i-1];
     anr[i-1] = temp;
    }
   }
}
}
/***********************************************/

二,向下冒泡(假设是从小到大排序,反之一样)

假设序列为:9 8 6 7 4
因为是向下冒泡也就是大的数往后走。

第一躺:8 6 7 4 9
第二躺:6 7 4 8 9
第三躺:6 4 7 8 9
第四躺:4 6 7 8 9
每一躺是把相邻的数比较,以第一躺为例:初始为9 8 6 7 4

先让9冒到8后:8 9 6 4 7
再让9冒到6后:8 6 9 4 7
再让9冒到7后:8 6 7 9 4
再让9冒到4后:8 6 7 4 9

以后每躺也一样
分析算法:同上这样的做的最坏情况就是所有数都要交换。复杂度为第一躺要交换n-1次,第二躺要交换n-2次(第二躺不要与第一躺交换?因为第一躺已将最小的数放在第1位),第n-1躺要交换1次,只要交换n-1次,原因是把n-1数都冒到前面,那最后一个数必为最大数。所以最坏情况要交换:n-1+n-2+...2+1=(n-1+1)*(n-1)/2=n*(n-1)/2,大O为O(n2)
分析完毕下面是C++代码:

#include <iostream>
#include <ctime>
#define ANRAY_SIZE 5
#define RANGE 80

using namespace std;

template<typename T>
void BubbleSort(T *,unsigned int);

int main()
{
srand(unsigned(time(NULL)));
int a[ANRAY_SIZE];

//随机赋值
for (int i = 0;i < ANRAY_SIZE ; i++)
      a[i] = rand() % RANGE + 1;
     
    //排序前
for (int i = 0;i < ANRAY_SIZE; i++)
      cout<<a[i]<<" ";
    cout<<endl;
     
    BubbleSort(a,ANRAY_SIZE);

//排序后
for (int i = 0;i < ANRAY_SIZE; i++) cout<<a[i]<<" ";
return 0;
}

/**********************************************/
//冒泡排序1,向下冒
template<typename T>
void BubbleSort(T* anr,unsigned int SIZE)
{
for (int pass = 1;pass < SIZE ; pass++)
{
   for (int i = 0;i < SIZE - pass; i++)
   {
    if (anr[i] > anr[i+1])
    {
     T temp = anr[i];
     anr[i] = anr[i+1];
     anr[i+1] = temp;
    }
   }
}
}
/***********************************************/

给我留言

留言无头像?