排序算法-冒泡排序

冒泡排序（Bubble Sort），应该算是比较简单也是很经典的排序算法。也比较好理解，先说一下结论，它的时间复杂度O(n^2),具有稳定性，重复遍历元素序列，依次比较相邻两个数，如果第一个比第二个大，就交换他们两个。（一般指排序从小到大）这样的话每一轮结束后，最大的就跑到后面去了，就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

BubbleSort

一. c语言版

【原版1】

/*    
         比较是相邻的两个元素比较，大的元素往后调。
         经过冒泡后，会将最大给浮上水面（从小到大排序）  
    -循环，比较相邻两个数值，如果 第一个比第二个大就交换位置
    -对每一对相邻的元素做同样的工作，从开始到最后一对，经过一轮后，最大值会在数组最后
    -持续重复上面的操作，直到没有数字需要对比 
*/
void BubbleSort1(int *arr,int len)
{
    int i,j;//两个变量 来控制双循环来进行排序  
    for( i=0; i<len-1 ; i++){//外循环为排序趟数 一共len个数 走len-1趟
        for( j=0 ; j<len-1-i; j++){//内循环代表每一轮的冒泡处理  第i趟比较len-i次 
            if(arr[j] > arr[j+1]){//每次处理后最大值都在后面
                swap(&arr[j],&arr[j+1]); //这个是交换两个数的地址 
            }
        }
    } 
}

【优化1】

/*
    进一步 优化一下冒泡排序 
    8 3 2 4 5
        =>第一轮 3 2 4 5 8  所以8已经有序了 
        第二轮 2 3 4 5 8    所以2到5已经有序了 但是原版的还是会继续循环下去
        用标记order，判断是否有序
        第三轮   已经都有序，不需要再进行比较了，直接跳出循环 
*/ 
void BubbleSort1(int *arr,int len)
{
    int i,j;
    for( i=0; i<len-1 ; i++){ 
        bool   order = true;//有序标记 
        for( j=0 ; j<len-1-i; j++){
            if(arr[j] > arr[j+1]){
                swap(&arr[j],&arr[j+1]);//有交换 就表示无序 
                order = false;
            }
        }
        if(order){
            break;//整个数组已经有序，跳出循环 
        }
    } 
}

【优化2】

/*
    再优化
        确定的是  有序区的长度和排序的轮数是相等的。
        比如第一轮排序过后的有序区长度是1，第二轮排序过后的有序区长度是2 . 
    但是对于部分有序的数组，可能后面已经有序，大于排序的轮数。 
    因此后面的许多次元素比较是没有意义的。

    我们可以在每一轮排序的最后，记录下最后一次元素交换的位置，
    那个位置也就是无序数列的边界，再往后就是有序区了。 
*/
void BubbleSort2(int *arr,int len)
{
    int i,j;
    int lastIndex = 0;//记录最后一次交换的位置 
    int sortBorder= len - 1;//无序数组的边界，后面就是有序的 
    for(i=0; i<len-1; i++){
        bool order = true;
        for(j=0; j<sortBorder; j++){//所以只需要比较到这个边界 
            if(arr[j]>arr[j+1]){
                swap(&arr[j],&arr[j+1]);
                order = false;
                lastIndex = j;//更新最后交换的位置 
            }
        }
        sortBorder = lastIndex;//重新确定无序的边界 
        if(order){
            break;
        }
    }    
}

【完整代码】

#include<stdio.h>
#include <stdbool.h>
#include <time.h>
#define MAX 10000 //数组长度

void BubbleSort(int *arr,int len);//冒泡排序 
void BubbleSort1(int *arr,int len); //优化 判断是否已经有序 
void BubbleSort2(int *arr,int len); //优化 判断有序与无序边界 

void getRandArray(int *arr,int len,int Range); //随机生成一个一维数组 
void getNearRandArray(int *arr,int len,int times);//生成一个部分有序的数组 
void swap(int *a,int *b);                     //交换两个变量 
void dump(int arr[],int len);                 //打印数组 

/**
    如果比较这三个冒泡排序，
    可以利用 getNearRandArray构造出一个部分有序的数组 
    对比三组时间快慢 
*/ 
int main()
{
    clock_t begin , end;
    double time;
    int arr[MAX],arr1[MAX],arr2[MAX];
    getRandArray(arr,MAX,10000);//生成无序数组
    getNearRandArray(arr,MAX,10);//生成部分有序的数组
    memcpy(arr1,arr,sizeof(arr));//拷贝arr  
    memcpy(arr2,arr,sizeof(arr));//拷贝arr
//    dump(arr,MAX); 
    begin = clock();//开始记录
            BubbleSort(arr,MAX);
    end = clock();    //结束记录
    time = (double)(end - begin)/CLOCKS_PER_SEC;
    printf("【 array length is %d 】【冒泡排序】【cost time is %lf 】\n",MAX,time);
//    dump(arr,MAX); 
    begin = clock();//开始记录
            BubbleSort1(arr1,MAX);
    end = clock();    //结束记录
    time = (double)(end - begin)/CLOCKS_PER_SEC;
    printf("【 array length is %d 】【冒泡排序2】【cost time is %lf 】\n",MAX,time);
//    dump(arr1,MAX); 
    begin = clock();//开始记录
            BubbleSort2(arr2,MAX);
    end = clock();    //结束记录
    time = (double)(end - begin)/CLOCKS_PER_SEC;
    printf("【 array length is %d 】【冒泡排序3】【cost time is %lf 】\n",MAX,time);
//    dump(arr2,MAX); 
    return 0; 
}

//冒泡排序 
/**    
        时间复杂度O(n^2),具有稳定性 
     经典算法，也是比较简单的一种排序算法 
         比较是相邻的两个元素比较，大的元素往后调。
         经过冒泡后，会将最大给浮上水面（从小到大排序）  
    -循环，比较相邻两个数值，如果 第一个比第二个大就交换位置
    -对每一对相邻的元素做同样的工作，从开始到最后一对，经过一轮后，最大值会在数组最后
    -持续重复上面的操作，直到没有数字需要对比 
*/
void BubbleSort(int *arr,int len)
{
    int i,j;//两个变量 来控制双循环来进行排序  
    for( i=0; i<len-1 ; i++){//外循环为排序趟数 一共len个数 走len-1趟
        for( j=0 ; j<len-1-i; j++){//内循环代表每一轮的冒泡处理  第i趟比较len-i次 
            if(arr[j] > arr[j+1]){//每次处理后最大值都在后面
                swap(&arr[j],&arr[j+1]); //这个是交换两个数的地址 
            }
        }
    } 
}

/**
    进一步 优化一下冒泡排序 
    8 3 2 4 5
        =>第一轮 3 2 4 5 8  所以8已经有序了 
        第二轮 2 3 4 5 8    所以2到5已经有序了 但是原版的还是会继续循环下去
        用标记order，判断是否有序
        第三轮   已经都有序，不需要再进行比较了，直接跳出循环 
*/
void BubbleSort1(int *arr,int len)
{
    int i,j;
    for( i=0; i<len-1 ; i++){ 
        bool   order = true;//有序标记 
        for( j=0 ; j<len-1-i; j++){
            if(arr[j] > arr[j+1]){
                swap(&arr[j],&arr[j+1]);//有交换 就表示无序 
                order = false;
            }
        }
        if(order){
            break;//整个数组已经有序，跳出循环 
        }
    } 
}

/*
    再优化
        确定的是  有序区的长度和排序的轮数是相等的。
        比如第一轮排序过后的有序区长度是1，第二轮排序过后的有序区长度是2 . 
    但是对于部分有序的数组，可能后面已经有序，大于排序的轮数。 
    因此后面的许多次元素比较是没有意义的。

    我们可以在每一轮排序的最后，记录下最后一次元素交换的位置，
    那个位置也就是无序数列的边界，再往后就是有序区了。 
*/
void BubbleSort2(int *arr,int len)
{
    int i,j;
    int lastIndex = 0;//记录最后一次交换的位置 
    int sortBorder= len - 1;//无序数组的边界，后面就是有序的 
    for(i=0; i<len-1; i++){
        bool order = true;
        for(j=0; j<sortBorder; j++){//所以只需要比较到这个边界 
            if(arr[j]>arr[j+1]){
                swap(&arr[j],&arr[j+1]);
                order = false;
                lastIndex = j;//更新最后交换的位置 
            }
        }
        sortBorder = lastIndex;//重新确定无序的边界 
        if(order){
            break;
        }
    }    
}


//随机生成一个数组  随机数范围在[0,Range) 
void getRandArray(int *arr,int len,int Range)
{
    srand(time(NULL));//设置随机种子
    int i = 0;
    for (i=0; i<len; i++){
        arr[i] = rand() % Range;//范围在Range以内 
    }
} 

//随机生成一个部分有序的数组 
void getNearRandArray(int *arr,int len,int times)
{
    int i = 0;
    for(i;i<len;i++){//先构造一个有序的数组 
        arr[i] = i;
    }    
    srand(time(NULL));//设置种子 
    for(i=0;i<times;i++){//尽量有序 循环交换多少次 
        int posx = rand()%(len-1);//在[1,len-1]上随机位置 
        int posy = rand()%(len-1);
        swap(&arr[posx],&arr[posy]);//随机交换两个位置的数 
    }
} 

//交换两个值  利用指针交换位置 
void swap(int *a,int *b)
{
    int temp;
    temp = *a;
    *a   = *b;
    *b   = temp;
}

 //打印输出数组
void dump(int *arr,int len)
{
    int i=0;
     for(i=0; i<len; i++)
        printf("%d ",arr[i]);
    printf("\n");//换行 
}

二. PHP版

【PHP知识点】

1.随机数的产生
    【rand()】产生随机整数
        a.如果没有传入参数，默认从0到getrandmax()之间的伪随机整数 （getrandmax()在win下32767）
        b.如果传入参数rand(2,10)，也就是从[2,10]返回之间进行获取随机整数
        c.之前获取随机数，都需要提前设置随机种子srand()，不过PHP已经 由系统自动完成的。
    【mt_rand()】生成更好的随机数 同rand()，不过效果更好
        a.不写参数，默认从0到mt_getrandmax()
        b.PHP 的 rand() 函数默认使用 libc 随机数发生器。
        c.产生随机数值的平均速度比 libc 提供的 rand() 快四倍。
2.统计时间
     microtime() — 返回当前 Unix 时间戳和微秒数
    a.默认参数False,返回字符串 "microsec sec" ，
           其中 sec 为自 Unix 纪元（0:00:00 January 1, 1970 GMT）起的秒数，
            microsec 为微秒部分。
    b.参数设置为 TRUE，则返回一个浮点数，
        表示自 Unix 纪元起精确到微秒的以秒为单位的当前时间。
3.交换两个变量
 【异或】相同为0 
 a.任一变量X与其自身进行异或结果为0，即 X^X=0
 b.任一变量X与0进行异或结果不变，即 X^0=X
 c.异或运算具有可结合性，即 a^b^c = (a^b)^c = a^(b^c)
 d.异或运算具有可交换性，即 a^b = b^a

【冒泡排序】

<?php
//冒泡排序
class Bubble
{
    const   min  = 0;
    const   max  = 10000;

    private  $len = 100;//默认构造的数组长度
    private  $times= 10;//无序交换次数

    public  $arr = [];//要排序的数组

    public function __construct($len=0,$times=0,$min=Bubble::min,$max=Bubble::max)
    {
        $this->len = empty($len) ? $this->len:$len;//判断要生成数组的长度
        $this->times= empty($times) ? $this->times:$times; //无序交换次数 
        $this->arr = $this->getNearRandArray($this->len,$this->times,$min,$max);//生成无序数组
    }

/**
 * 冒泡排序
 */
    public function bubbleSort()
    {
        $out = $this->arr;
        for($i=0;$i<$this->len-1;$i++){
            for($j=0;$j<$this->len-1-$i;$j++){
                ($out[$j]>$out[$j+1]) && $this->swap($out[$j],$out[$j+1]);//大数冒泡
            }
        }
        return $out;
    }

    //改进 添加order 判断是否数组已经有序
    public function bubbleSort1()
    {
        $out = $this->arr;
        for($i=0;$i<$this->len-1;$i++){
            $order = true;
            for($j=0;$j<$this->len-1-$i;$j++){
                ($out[$j]>$out[$j+1]) && $this->swap($out[$j],$out[$j+1]);
                $order = false;
            }
            if($order){
                break;
            }
        }
        return $out;
    }

    //改进 判断有序区域的界限
    public function bubbleSort2()
    {
        $out = $this->arr;
        $lastIndex = 0;//最后一次交换的位置
        $sortBorder= $this->len - 1;//无序数组边界
        for($i=0;$i<$this->len-1;$i++){
            $order = true;
            for($j=0;$j<$this->len-1-$i;$j++){
                ($out[$j]>$out[$j+1]) && $this->swap($out[$j],$out[$j+1]);
                $order = false;
                $lastIndex = $j;//记录最后 交换的位置
            }
            $sortBorder = $lastIndex;//重新确定无序的边界 防止无效比较
            if($order){
                break;
            }
        }
        return $out;
    }


/**
 * 交换两个变量
 * 第一步 a = a ^ b 完成
 *      经过第一步运算后a 变量的结果为 a ^ b；
 *   第二步 b = a ^ b 等号右边即是 (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a，
 *      经过第二步运算后b中的值为a；
 *   第三步 a = a ^ b 此时赋值号右边的a保存的仍然是 a ^ b 的值，而赋值号右边的b已经是原始的a了，
 *   即等号右边的 a ^ b = (a ^ b) ^ a = a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b, 该值赋值给a，即 a = b，
 *      经过第三步运算后a中的值为b；


 */
    private function swap(&$a,&$b)
    {
        $a = $a^$b;
        $b = $b^$a;
        $a = $a^$b;
    }

/**
 * 生成部分有序的数组
 * Params 
 *      $len 数组大小
 *      $min , $max 随机数范围
 *      $times 无序交换位置次数
 * return
 *      返回数组 
 */
    private function getNearRandArray($len,$times,$min,$max)
    {
        $arr = [];//生成部分有序的数组
        for($i=0; $i<$len; $i++){
           $arr[$i] = $i;
        } 
        for($i=0; $i<$times; $i++){//打乱有序 循环交换多少次 
            $posx = mt_rand()%($len-1);//在[1,len-1]上随机位置 
            $posy = mt_rand()%($len-1);
            $this->swap($arr[$posx],$arr[$posy]);//随机交换两个位置的数 
        } 
        return $arr;
    }


}

$obj = new Bubble(100,5);

$stime=microtime(true); 
    $obj->bubbleSort();
$etime=microtime(true);
$total=$etime-$stime;
echo "<br />[冒泡排序1]执行时间为：{$total} 秒<br/>"; 

$stime=microtime(true); 
    $obj->bubbleSort1();
$etime=microtime(true);
$total=$etime-$stime;
echo "<br />[冒泡排序2]执行时间为：{$total} 秒<br/>"; 

$stime=microtime(true); 
    $obj->bubbleSort1();
$etime=microtime(true);
$total=$etime-$stime;
echo "<br />[冒泡排序3]执行时间为：{$total} 秒<br/>";

自己数据结构与算法很差，于是决定从基础入手，一步一个脚印，体验算法之美，由于打算走PHP方向，所以用PHP来进行编写代码，希望能对我的成长有一定帮助。第一次在牛客上发博，希望大家可以互相帮助，有错误及时指出，共同进步，加油！！！🐂

全部评论

相关推荐

今天 15:37
已编辑
北京邮电大学 银行其它
本科别学ai
坐标北邮ai,大四上学校硬排了五门专业课……大四上学期，我要上多模态，三维重建，情感计算，智能医学，专业实习，人工智能创新（这课很逆天，论文or三个月以上实习or竞赛）两周的小学期智能医学，没一点用，竟然还爆改八周，每周一次代码作业，还要出去实习，考研人的绝望时刻。学的多且杂，本科期间要学cv,nlp,语音，多模态，大模型，rag,数据库，计网，计原c++,vue,js,python……。注，大四这些课，只能在第七学期学，无法提前上。不然谁会大四留给自己一堆课。最后，一句话让你知道有多卷，保研最低89分。北邮其它专业还行啊，并且ai有三个方向，我仅在此吐槽ai人工智能方向排课不合理。以后如果有...
想去夏威夷的小哥哥在度假：更重要的是学ai只有本科学历是找不到工作的，建议取消本科ai专业
选完offer后，你后悔学本专业吗
点赞 评论 收藏
分享
11-19 17:10
武汉大学 前端开发其它
点赞 评论 收藏
分享
头像
11-06 10:58
已编辑
门头沟学院 嵌入式工程师
和HR的默契
看似什么都没问，实则什么都问了，哈哈哈哈哈哈哈哈哈字节跳动，我来了！#牛客创作赏金赛##字节求职进展汇总#
双非25想找富婆不想打工：哦，这该死的伦敦腔，我敢打赌，你简直是个天才，如果我有offer的话，我一定用offer狠狠的打在你的脸上
牛客创作赏金赛 字节求职进展汇总
点赞 评论 收藏
分享
10-14 23:01
已编辑
中国地质大学（武汉） Java
完全找不到实习啊
怎么办啊，求大佬指点
CUG芝士圈：虽然是网上的项目，但最好还是包装一下，然后现在大部分公司都在忙校招，十月底、十一月初会好找一些。最后，boss才沟通100家，别焦虑，我去年暑假找第一段实习的时候沟通了500➕才有面试，校友加油
点赞 评论 收藏
分享
头像
11-20 04:45
门头沟学院 C++
腾讯面经
迟来的面经。。。因为直到今日我居然还没有面完。鹅厂的面试跨度有点大，以至于我甚至忘掉了相当多的部分，于是只能简单描述一下。一面：项目拷打，几乎没有八股，最后是一道算法题，写出来了，但是没写出最优的来。二面：项目拷打，无八股，无算法题。三面：项目拷打，然后是发散性题目，比如：“你对于XX领域（面试的岗位相关）怎么看的啊？”，“你以前是做A的，为什么想做B？这个gap你是怎么看的？”四面：自我介绍，然后是，“你刚刚提到你的一个观点XXX，你能具体描述一下吗？”&nbsp;于是拿了自己经历过的两个项目来佐证；“现在有最新的研究尝试把机器学习替换掉某些关键的组件，比如XX，你了解过吗？”&nbsp;正好之前了解过相关的内...
查看5道真题和解析
点赞 评论 收藏
分享
1 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
294232次浏览 2582人参与
# 如果不工作真的会快乐吗 #
58490次浏览 505人参与
# 北方华创开奖 #
25900次浏览 279人参与
# 地方国企笔面经互助 #
3640次浏览 8人参与
# 国央企薪资爆料 #
6831次浏览 50人参与
# 选完offer后，你后悔学本专业吗 #
19071次浏览 137人参与
# 百度开奖 #
157161次浏览 939人参与
# 学历or实习经历，哪个更重要 #
50116次浏览 389人参与
# 美团求职进展汇总 #
1325236次浏览 12437人参与
# 投递实习岗位前的准备 #
1178349次浏览 18384人参与
# 面试体验感最好的是哪家？ #
84815次浏览 842人参与
# 正在实习的你，几点下班 #
51261次浏览 381人参与
# 如何一边实习一边秋招 #
990844次浏览 12631人参与
# 得物求职进展汇总 #
65936次浏览 679人参与
# 实习生应该准时下班吗 #
167234次浏览 1159人参与
# 提前批简历挂麻了怎么办 #
146090次浏览 1942人参与
# 0offer是寒冬太冷还是我太菜 #
896824次浏览 8002人参与
# 腾讯求职进展汇总 #
195271次浏览 1637人参与
# 银行笔面经互助 #
82486次浏览 873人参与
# 网申一定要掌握的小技巧 #
5280次浏览 52人参与
# 数据人offer决赛圈怎么选 #
116457次浏览 1461人参与
# 海康威视求职进展汇总 #
398276次浏览 3404人参与
牛客网
牛客企业服务