When we talk about best-case or worse-case or average-case time-complexity of quicksort (or just about any algorithm), the case of average case is very different from the best case or the worse case. The time-complexity $T(n)$ of average case is the average time-complexity of quicksort running on a (usually uniform) distribution of arrays of size $n$. While we can say a particular input is the best case or the worst case for some quicksort algorithm, we cannot just point to one particular input and say that input is the average case (even an average case) for some quicksort algorithm even though people do that sloppily all the time.
There are more than three cases if we consider different input for classical quicksort (with Hoare partition scheme ). The possible time complexity for particular runs of quicksort can be anywhere between the best case and the worse case. For example, it could be about $\Theta(n(\log n)^2)$ or $\Theta(n^{\frac32})$ or $\Theta(n^{\frac{19}{10}})$ or $\Theta(n^2/\log n)$. More specifically, given any $f(n)$ such that $\log n\le f(n)\le n$ for all $n$, we could construct runs of quicksort on an array of size $n$ whose time-complexity is $\Theta(nf(n))$. In fact, we have the following property of quicksort.
(Continuum of comparisons by quicksort) Let $c(A)$ be the number of comparisons used by the classic quicksort on array $A$. Let $m_n=\min_{\#A=n}c(A)$ and $M_n=\max_{\#A=n}c(A)$ for integer $n>0$. Given any integer $i$ such that $m_n\le i\le M_n$, there is an array $A$ of size $n$ such that $c(A)=i$.
This property holds for number of swaps and for many other quicksort algorithms as well. This property should help us understand the general picture of time-complexity of the classic quicksort.
Statement 1: Any other partition should result in average case.
Q1. Is statement 1 true? If no, which other pivot selection strategies could result in worst case or best case behavior?
As analyzed in the previously paragraphs, statement 1 does not make much sense in the standard semantic. To determine the asymptotic behavior of a quicksort algorithm, we need to specifies both the actual kind of quicksort algorithm especially its partition scheme and which one of the best case, or worst case, or average case the input array will be. It does not make sense to say $O(n\log n)$ is the average case.
I would rather summarize the situation instead as the following.
All quicksort algorithms (that I have seen, including the variants here excluding the "non-pure" ones) is $\Theta(n\log n)$ in average case, that is, if the given input arrays are uniformly random. ( No precise definition of "uniformly random" is given here. It can be formulated rigorously, for example here.)
On the other hand, some quicksort algorithm (almost) always choose pivot that partition array in some fixed proportion. Those algorithms have $\Theta(n\log n)$ even in the worst cases of inputs. However, those algorithms usually have much larger constant factor hidden in the big $\Theta$-notation than the constant factor hidden in the big $\Theta$-notation of other algorithms in average case.
Statement 2: Any pivot which does not partition array in some proportion should result in worst case. If nth smallest or largest element is selected as pivot, it will result in worst case.
Q2. Is statement 2 true?
"Any pivot which does not partition array in some proportion should result in worst case" sounds reasonable but not precise enough to be verified or refuted mathematically. The following is a precise version that can be proved.
(Statement 3) (the classic) quicksort runs in time-complexity $\Theta(n^2)$ if each pivoting on any array partition it into two parts with one part of size $O(1)$. In particular, for any constant $c$, if $c$-th smallest or largest element is selected as pivot whenever the size is no less than $c$, it will result in $\Theta(n^2)$ time-complexity.
The following two exercise may not be easy. Beginners should attempt them later.
Exercise 1. Prove statement 3.
Exercise 2. Prove the claim of "continuum of comparisons by quicksort".
The following two resources are not exactly about pure quicksort, but are related and interesting enough.
