冒泡排序（Bubble Sort），应该算是比较简单也是很经典的排序算法。也比较好理解，先说一下结论，它的时间复杂度O(n^2),具有稳定性，重复遍历元素序列，依次比较相邻两个数，如果第一个比第二个大，就交换他们两个。（一般指排序从小到大）这样的话每一轮结束后，最大的就跑到后面去了，就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
一. 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来进行编写代码，希望能对我的成长有一定帮助。第一次在牛客上发博，希望大家可以互相帮助，有错误及时指出，共同进步，加油！！！🐂
京公网安备 11010502036488号