首页 / 算法 / 八大排序算法之五--交换排序—冒泡排序（Bubble Sort）

八大排序算法之五--交换排序—冒泡排序（Bubble Sort）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了八大排序算法之五--交换排序—冒泡排序（Bubble Sort），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1329字，纯文字阅读大概需要2分钟。

内容图文

基本思想：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

算法实现：（HDU 1040 亲测 AC）

技术分享 技术分享 
#include<iostream>
usingnamespace std;
constint N =1005;
void BubbleSort(int a[],int );
void print(int a[],int num);
void swap(int &a,int &b);

int main()
{
    int s[N];
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int j=0;j<n;j++)
           cin>>s[j];
        BubbleSort(s,n);
        print(s,n);       
        cout<<endl;        
    }
    return0;
}
void BubbleSort(int a[],int num)//冒泡排序算法 {
    for(int i=0;i<num-1;i++)
    {
        for(int j=0;j<num-i-1;j++)
        {
            if(a[j]>a[j+1])
            {
                swap(a[j],a[j+1]);
            }
        }
    }
}
void swap(int &a,int& b)//交换元素 {
    int temp;
    temp=a;
    a=b;
    b=temp;
}
void print(int a[],int n)//输出数组元素 {
    cout<<a[0];
    for(int k=1;k<n;k++)
    {
        cout<<""<<a[k];
    }
}
View Code

n个数排序 比较趟数为n-1次
算法时间复杂度：O(n2) 

空间复杂度 ：O(n)

 

改进版本：

上面的冒泡排序中每一趟排序操作只能找到一个最大值或最小值,但如果在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

            void BubbleSort_Modify(int a[],int num)//冒泡排序算法 {
   int low=0;
   int high=num-1;
   while(low<high)
   {
          for(int i=low;i<high;i++)// 正向冒泡得到最大值 if(a[i]>a[i+1])
                swap(a[i],a[i+1]);
          high--;//high前移一位 for(int i=high;i>low;i--)// 反向冒泡得到最小值          {
                 if(a[i]<a[i-1])
                   swap(a[i],a[i-1]);
        }
        low++;//low后移一位    }
}

 

原文：http://www.cnblogs.com/wft1990/p/5894550.html

内容总结

以上是互联网集市为您收集整理的八大排序算法之五--交换排序—冒泡排序（Bubble Sort）全部内容，希望文章能够帮你解决八大排序算法之五--交换排序—冒泡排序（Bubble Sort）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1203261.html

来源：【匿名】