What is the algorithm used to encrypt Linux passwords? I noticed during an assignment that, if I create an user with a password (azerty for exemple), and then call the command to change the password but give him exactly the same password:

passwd user
&gt;&gt; azerty       


the encrypted string stored in ./etc/shadow changes (despite the password not changing).

What algorithm is used here?
It's not encryption, it's a one-way hash.

There are a handful of different password hashes usually used for Linux system users' passwords, they're listed in the man page for crypt(3)

The first is the original crypt algorithm, that only supported 8 character passwords (among other flaws), and which you'll hopefully never see again.

The second is the MD5-based md5crypt ([a], [b]), marked with $1$. It's considered dated mostly because it doesn't support changing the amount of iterations, i.e. the cost of the computation.

Currently more used are the SHA-256 and SHA-512 based hashes, sha256crypt and sha512crypt, which are similar in structure to md5crypt but support variable amounts of iteration. They're marked with $5$ and $6$ respectively. As @SEJPM quickly enough commented, sha512crypt ($6$) is what at least Ubuntu and Debian currently use by default.

For $1$, $5$, and $6$, the characters after the identifier up to the next $ are the salt, which is generated randomly when the password is changed.

The remaining option, not in mainline glibc is the Blowfish-based bcrypt, marked with $2a$ (or another letter). Bcrypt also uses a salt.

For more information on password hashing, and as to why use salts and why slower is better, see 
"How to securely hash passwords?" on security.SE.