I have to second Skiena's book. I had three books: the famous Cormen tome, "Algorithm Design" by Kleinberg and Tardos, and Skiena's "Algorithm Design Manual" available when learning advanced algorithms. I'm still amazed at how Skiena's book covers both the basics in a far better pedagogical way than the other two, as well as serving as a really nice lookup utility for tackling specific problems (the second half of the book is jammed packed with short problem description, as well as a overview of approaches and considerations). I kept looking up the same topic in all three, and ended up reading the Algorithm Design Manual.

That said, Cormen's book is famous for a reason, but more often than not, I felt it gave way for mathematical rigor than plain language.

Note: The second edition of Skiena's book is significantly improved over the first... well, besides the quality if the paper.

edit: Meant second edition of Skiena's book, not Cormen's. Sorry.