快速排序还是考的比较频繁的，几乎每年都考。本题考察快速排序的方式和时间复杂度的计算。

快速排序的方式，就是在一行数据中，取某一端的数据为基准数据（就是用来和其他每一个元素进行比较的值，本题已给出按最后一个元素），然后再从基准元素的另一端开始，逐步和基准值进行比较，然后交换两个位置，交换还是保持，看排序规则，题目中给出非递减排序，也就是从左到右大概是递增排序，左大右小就交换顺序。交换位置后换边比较（因为被比较元素总是处于基准元素的另一端），比较条件也取反。

所以第一趟排序过程是：

4和2比较，4比2大，不动；

4和8比较，4比8小，交换，结果为(2,4,7,1,3,5,6,8)；

4和6比较，4比6小（条件取反，因为要保证从小到大），不动；

4和5比较，同上；

4和3比较，4比3大，交换，结果为(2,3,7,1,4,5,6,8)；

4和7比较，4比7小，交换，结果为(2,3,4,1,7,5,6,8)；

4和1比较，4比1大，交换，结果为(2,3,1,4,7,5,6,8)；

4和4比较，结束；所以结果就是C选项。

第二空：因为一趟会和所有元素进行一次比较，所以时间复杂度是O(n)。