排序算法-冒泡排序

冒泡排序（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/>";