Utilisez la force brute pour résoudre le tri à bulles

Le tri à bulles est une autre incarnation classique de la méthode de la force brute.

Idée d'algorithme :

Comparez les éléments adjacents dans la liste, et s'ils sont dans l'ordre inverse, échangez leurs positions. Après l'avoir répété plusieurs fois, l'élément le plus grand est classé en dernier. La deuxième opération déplace le deuxième élément vers l'avant-dernière position, et la comparaison se poursuit jusqu'à n-1 fois, et la liste entière est triée. Ce qui suit est l'implémentation de mon code : C++

#include 
using namespace std;
int main()
{
    int i,j,temp,N;
    cin>>N;
    int *Arr=new int[N];
    for(i=0;i<n cin>>Arr[i];
 
    for(i=0;i<n for if>Arr[j+1])//如果逆序，就交换
            {
                temp=Arr[j];
                Arr[j]=Arr[j+1];
                Arr[j+1]=temp;
            }
        }
    }
 
    for(i=0;i<n cout return>
</n></n></n>

Analyse de l'algorithme : la taille de l'entrée est entièrement déterminée par N. L'opération de base est la comparaison : Arr[j]>Arr[j+1], complexité temporelle C(n)=Θ(n2).

Mais le nombre d'échanges de clés dépend de l'entrée spécifique. Le pire des cas est l'opposé du tri dont nous avons actuellement besoin, le nombre d'échanges de clés = le nombre de comparaisons de clés = Θ(n2). Mais dans certains cas de saisie, si après comparaison de la liste, les positions des éléments ne sont pas échangées, alors la liste est déjà en ordre, et on peut arrêter l'algorithme. La version spécifique améliorée est la suivante :

#include 
using namespace std;
int main()
{
    int i,j,temp,N;
    bool change=false;
    cin>>N;
    int *Arr=new int[N];
    for(i=0;i<n cin>>Arr[i];
 
    for(i=0;i<n change="false;" for if>Arr[j+1])//如果逆序，就交换
            {
                temp=Arr[j];
                Arr[j]=Arr[j+1];
                Arr[j+1]=temp;
                change=true;
            }
        }
        if(!change)//没有发生交换，则不用继续比较了。
        {
            break;
        }
    }
 
    for(i=0;i<n cout return>
</n></n></n>

Mais dans le pire des cas, la complexité temporelle est toujours Θ(n2).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!