A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

冒泡排序(从大到小)

       原理:对于n个数,需要进行n-1次扫描,每次扫描通过相邻两个数的比较,找出最大的数,放到数列顶部。

      程序:

    1.冒泡排序1:每次扫描把下一个元素和最前面的元素比较,一次扫描结束后,最大的元素就在最前面了。

     void bubble_sort1(int a[],int len)
{
        int i,j;
        for (i=0; i<len-1; i++)
        {
                for (j=i+1; j<len; j++)
                {
                        if (a[i] < a[j])
                        {
                            /***数值交换方法3-位运算******/
                                a[i]^= a[j];
                                a[j]^= a[i];
                                a[i]^= a[j];
                        }
                }
        }
}

  2.冒泡排序2:每扫描一次,通过相邻两个元素的比较,使得最小或最大的数位于顶部。

   void bubble_sort2(int a[],int len)
{
        int i,j;
        for (i=0; i<len-1; i++) //扫描次数len-1
        {
              for (j=len-1; j>i; j--)
                {
                   if (a[j] > a[j-1])
                        {
                          /***数值交换方法1--加减法******
                          a[j]+=a[j-1];
                         a[j-1] = a[j] - a[j-1];
                         a[j] = a[j] - a[j-1];
                        }
                }
        }
}

3.冒泡排序3。对冒泡排序的改进方法:通过加入exchange变量用来判断每次扫描是否发生数值交换,如果哪次扫描没有发生数值交换,则已经排序好,无需进行下次扫描,减少了时间复杂度。

void bubble_sort3(int a[],int len)
{
        int i,j;
        int exchange = 0;     //用户标识是否发生过排序,用作冒泡的改进
         int temp;
        for (i=0; i<len-1; i++)    //扫描次数len - 1
        {
                exchange = 0;  //每次扫描前对exchange置0
                for (j=len-1; j>i; j--)
                {
                        if (a[j] > a[j-1])
                        {
                                /***数值交换方法2--临时变量置换法******/
                                temp = a[j];
                                a[j] = a[j-1];
                                a[j-1] = temp;
                                exchange = 1;  //如果还有排序,则exchange 为1
                        }
                }

                if (exchange == 0)  //如果此次扫描没有发生过交换,则说明已经全部排序好,不需要进行下次扫描
                {
                        return;
                }
        }
}

  以上三个简单的冒泡算法中,用了三种不同的数值交换方法:加减法、置换法、位运算法。其中位运算法效率最高。

以上排序均为从大到小排序,若要从小到大,只做少许改动即可,原理相同!



直接插入排序


原理:每次执行,把后面的数插入到前面已经排序好的数组中,直到最后一个完成。


/****************直接插入排序**************/
void directinsert_sort(int a[], int len)
{
        int i,j;
        int temp;
        for (i=1; i<len; i++) //
        {
                temp = a[i];
                for (j=i-1; j>=0; j--)
                {
                        if (temp < a[j])  //如果插入的值小于某个值,则退出循环
                        break;

                        a[j+1] = a[j];
               
                }
                a[j+1] = temp;
        }
}


选择排序



    原理:每次从待排序的记录中选出最大的数,放入已排好序的子文件中,直到全部记录完成。


/****************选择排序************/
void select_sort(int a[], int len)
{
        int i,j;
        int max,k;  //最大值及其下标
        for (i=0; i<len-1; i++)       //遍历len-1次
        {
                max = a[i];               //每次遍历前max 和 k的设置
                k = i;

                for (j=i+1; j<len; j++)    //每次取得剩余的最大值,及其下标
                {
                        if (a[j] > max)
                        {
                                max = a[j];
                                k = j;
                        }
                }

                a[k] = a[i];
                a[i] = max;
               
        }
}


以下为main函数及数组打印函数:

  /**********打印数组函数*************/
void print_array(int a[], int len)
{
        for (int i=0; i<len; i++)
        {
                cout<<a[i]<<" ";
        }
        cout<<endl;
}

int main()
{
        int a[10]={3,5,7,5,2,7,8,4,1,30};
        cout<<"排序前:";
        print_array(a,10);

        bubble_sort2(a,10);  //冒泡排序
//        select_sort(a,10);   //选择排序
        //directinsert_sort(a,10);//插入排序
        cout<<"排序后:";
        print_array(a,10);
        return 0;
}

  以上三种简单排序算法,都是从大到小的排序!

评分

参与人数 2技术分 +3 黑马币 +5 收起 理由
why19910522 + 2 写的不错!
33姗姗 + 3 + 3 加油!希望可以学以致用~

查看全部评分

10 个回复

倒序浏览
541630430 来自手机 中级黑马 2015-8-27 17:56:08
沙发
6666 顶一个

点评

谢谢你 一楼  发表于 2015-8-27 21:32
回复 使用道具 举报
顶一个,加油啦~

点评

共同努力吧 来这里的目的 没忘就好  发表于 2015-8-27 21:31
回复 使用道具 举报
挺不错的总结,还把方法封装成函数了,拿走一分,顺便支持一下

点评

节约 空间嘛 不过看着就麻烦了  发表于 2015-8-27 21:30
回复 使用道具 举报
学习了,加油  加油  

点评

一起加油吧 妹子加微信怎么样  发表于 2015-8-27 21:28
回复 使用道具 举报
总结的不错啊!

点评

感觉 还差点什么似的  发表于 2015-8-27 21:29
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马