If you don't need very precise information, then the quick answer is that $n^{1/2}$ is about right.

I want to use Stirling's formula in the version
$$
An^{n+1/2}e^{-n} \le n! \le Bn^{n+1/2}e^{-n} .
$$
This shows that
$$
\frac{n!}{(n-j)!n^j}\simeq e^{-j}\left( \frac{n}{n-j}\right)^{n-j+1/2} ,
$$
so the sum is
$$
S(n) \simeq e^{-n}\sum_{k=1}^n \left( \frac{ne}{k}\right)^{k+1/2} .
$$
By calculus, the function $f(x)=e^{-n}(ne/x)^{x+1/2}$ has a unique maximum on $1\le x\le n$ at $x=n-1/2+o(1)$. So for an upper bound, we can estimate the terms with $1\le k\le (1-\delta)n$ by taking $k=(1-\delta)n$ instead. Now
$$
f((1-\delta)n) = \left( \frac{e^{-\delta}}{1-\delta}\right)^n \simeq e^{-\delta^2 n} ,
$$
so this produces the estimate
$S(n)\lesssim \delta n + ne^{-\delta^2 n}$. With $\delta = C(\log n/n)^{1/2}$, this becomes $S(n)\lesssim (n\log n)^{1/2}$.

In the same way, we can use $\delta n f(n-\delta n)\gtrsim \delta n e^{-\delta^2 n}$ as a lower bound, and for $\delta = n^{-1/2}$, this gives that $S(n)\gtrsim n^{1/2}$.