排序算法之冒泡排序 C++和PHP实现

字体大小: 中小 标准 ->行高大小: 标准 中 大
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。是最慢的排序算法。在实际运用中它是效率最低的算法。
时间复杂度：
它是最差时间复杂度为：O(n^2)，冒泡排序最好的时间复杂度为：O(n^2)，平均时间复杂度为：O(n^2)
算法原理：
    1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
    2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
    3. 针对所有的元素重复以上的步骤，除了最后一个。
    4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
算法稳定性：
冒 泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊 地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变， 所以冒泡排序是一种稳定排序算法。

php代码：
[php] view plaincopy在CODE上查看代码片派生到我的代码片
  1. <?php  
  2.  $n = 8;  
  3.  $min = 1;  
  4.  $max = 100;  
  5.  $data = createData($n, $min, $max);  
  6.  echo "随机生成数组：";  
  7.  print_r($data);  
  8.  echo "<br />";  
  9.  bubble_sort($data, $n);  
  10.    
  11.     //生成一个随机数组成的不重复数组  
  12.  function createData($n, $min, $max){  
  13.      $bigarr = range($min, $max);  
  14.   $arrkey = array_rand($bigarr, $n); //返回键名  
  15.   for($i=0; $i<count($arrkey); $i++){  
  16.       $arr[] = $bigarr[$arrkey[$i]];  
  17.   }  
  18.   return $arr;  
  19.  }  
  20.    
  21.  //冒泡排序函数  
  22.  function bubble_sort($data, $n)  
  23.  {  
  24.   $flag = 0;  
  25.   for($i=0; $i<$n-1; $i++){  
  26.    for($j=0; $j<$n-$i-1; $j++){  
  27.     if($data[$j+1] < $data[$j]){  
  28.      $flag = 1;  
  29.      $temp = $data[$j];  
  30.      $data[$j] = $data[$j+1];  
  31.      $data[$j+1] = $temp;  
  32.     }  
  33.    }  
  34.    if (!$flag){  
  35.     break;  
  36.    }  
  37.    $flag = 0;  
  38.    echo "排序过程 ".($i+1)." 步:";  
  39.    print_r($data);  
  40.    echo "<br/>";  
  41.   }  
  42.   echo "排序后的结果：";  
  43.   print_r($data);  
  44.  }  
  45. ?>  
运行结果：


c++代码：
[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
  1. #include<iostream>  
  2. #include<stdlib.h>  
  3. #include<time.h>  
  4. using namespace std;  
  5. int createData(int arr[], int n, int min, int max);  
  6. void bubble_sort(int *a, int n);  
  7. int main()  
  8. {  
  9.     int arr[100];  
  10.     int n=6;  
  11.     int min=2;  
  12.     int max=12;  
  13.     createData(arr, n, min, max);  
  14.     for (int i=0; i<n; i++)  
  15.         cout << arr[i] << " ";  
  16.     cout << endl;  
  17.     bubble_sort(arr, n);  
  18.     for (int j=0; j<n; j++)  
  19.         cout << arr[j] << " ";  
  20.     cout << endl;  
  21.     return 1;  
  22. }  
  23.  //生成一个随机数组成的不重复数组  
  24. int createData(int arr[], int n, int min, int max)  
  25. {  
  26.     srand(time(NULL));  
  27.     int i,j,flag;  
  28.     for(i=0; i<n; i++){  
  29.         do{  
  30.             int num = min + rand()%(max-min+1);  
  31.             arr[i] = num;  
  32.             flag = 0;  
  33.             for(j=0; j<i; j++){  
  34.                if( arr[i] == arr[j])  
  35.                    flag = 1;  
  36.             }  
  37.         }while(flag);  
  38.     }  
  39.     return 1;  
  40. }  
  41.  //冒泡排序函数  
  42. void bubble_sort(int *a, int n)  
  43. {  
  44.     bool flag = true;  
  45.     int k = n;  
  46.     while(flag)  
  47.     {  
  48.         flag = false;  
  49.         for(int i=1; i<k; i++)  
  50.         {  
  51.             if(a[i-1] > a[i])  
  52.             {  
  53.                 int tmp = a[i];  
  54.                 a[i] = a[i-1];  
  55.                 a[i-1] = tmp;  
  56.                 flag = true;  
  57.             }  
  58.         }  
  59.         k--;  
  60.     }  
  61. }  
运行结果：


此文章由 http://www.ositren.com 收集整理 ,地址为: http://www.ositren.com/htmls/69172.html