C++ と PHP で実装されたソート アルゴリズム バブル ソート

バブルソートは、小さな要素を前方に移動したり、大きな要素を後方に移動したりすることです。比較は隣接する 2 つの要素の比較であり、これら 2 つの要素間でも交換が行われます。最も遅い並べ替えアルゴリズムです。実際には、これは最も効率の悪いアルゴリズムです。

時間計算量:

最悪の時間計算量: O(n^2)、バブルソートの最高の時間計算量: O(n^2)、平均時間計算量: O(n^2) )

アルゴリズム原理:

1. 隣接する要素を比較します。最初のものが 2 番目のものより大きい場合は、両方を交換します。

2. 隣接する要素の各ペアに対して、最初の最初のペアから最後の最後のペアまで、同じ作業を実行します。この時点では、最後の要素が最大の数値である必要があります。

3. 最後の要素を除くすべての要素に対して上記の手順を繰り返します。

4. 比較する数値のペアがなくなるまで、要素を減らして上記の手順を繰り返します

アルゴリズムの安定性:

バブルソートは、小さな要素を前に移動するか、大きな要素を移動します戻る。比較は隣接する 2 つの要素の比較であり、これら 2 つの要素間でも交換が行われます。したがって、2つの要素が等しい場合は、退屈に交換することはないと思いますが、2つの等しい要素が隣接していない場合は、前のペアごとの交換で2つが隣接していても、この順序は交換されません。同じ要素は変化しないため、バブルソートは安定したソートアルゴリズムです。

php コード:

<?php $n = 8; $min = 1; $max = 100; $data = createData($n, $min, $max); echo "随机生成数组："; print_r($data); echo "<br />"; bubble_sort($data, $n);     //生成一个随机数组成的不重复数组 function createData($n, $min, $max){     $bigarr = range($min, $max);  $arrkey = array_rand($bigarr, $n); //返回键名  for($i=0; $i<count($arrkey); $i++){      $arr[] = $bigarr[$arrkey[$i]];  }  return $arr; }  //冒泡排序函数 function bubble_sort($data, $n) {  $flag = 0;  for($i=0; $i<$n-1; $i++){   for($j=0; $j<$n-$i-1; $j++){    if($data[$j+1] < $data[$j]){     $flag = 1;     $temp = $data[$j];     $data[$j] = $data[$j+1];     $data[$j+1] = $temp;    }   }   if (!$flag){    break;   }   $flag = 0;   echo "排序过程 ".($i+1)." 步:";   print_r($data);   echo "<br/>";  }  echo "排序后的结果：";  print_r($data); }?>

実行結果:

C++ コード:

#include<iostream>#include<stdlib.h>#include<time.h>using namespace std;int createData(int arr[], int n, int min, int max);void bubble_sort(int *a, int n);int main(){    int arr[100];    int n=6;    int min=2;    int max=12;    createData(arr, n, min, max);    for (int i=0; i<n; i++)        cout << arr[i] << " ";    cout << endl;    bubble_sort(arr, n);    for (int j=0; j<n; j++)        cout << arr[j] << " ";    cout << endl;    return 1;} //生成一个随机数组成的不重复数组int createData(int arr[], int n, int min, int max){    srand(time(NULL));    int i,j,flag;    for(i=0; i<n; i++){        do{            int num = min + rand()%(max-min+1);            arr[i] = num;            flag = 0;            for(j=0; j<i; j++){               if( arr[i] == arr[j])                   flag = 1;            }        }while(flag);    }    return 1;} //冒泡排序函数void bubble_sort(int *a, int n){    bool flag = true;    int k = n;    while(flag)    {        flag = false;        for(int i=1; i<k; i++)        {            if(a[i-1] > a[i])            {                int tmp = a[i];                a[i] = a[i-1];                a[i-1] = tmp;                flag = true;            }        }        k--;    }}

実行結果: