对键值序列（61，87，12，3，8，70）以位于最左位置的键值为基准进行由小到大的快速排序，请写出第一趟排序后的结果，并给出快速排序算法在平均情况和最坏情况下的时间复杂度。
【正确答案】：
第一趟排序结果：[8    3    12]  61  [87  70]
平均情况下的时间复杂度：
最坏情况下的时间复杂度：
【题目解析】：
快速排序基本思想：在n个记录中取某一个记录的键值为标准，通常取第一个记录键值为基准，通过一趟排序将待排的记录分为小于或等于这个键值和大于这个键值的两个独立的部分，这时一部分的记录键值均比另一部分记录的键值小，然后，对这两部分记录继续分别进行快速排序，以达到整个序列有序。
初始关键字： 61 87 12 3 8 70
一次交换后： 8 87 12 3 61 70
二次交换后： 8 61 12 3 87 70
第一趟排序结果：[8 3 12] 61 [87 70]
就平均时间性能而言，快速排序方法最佳，其时间复杂度为。但在最坏情况下，即对几乎已是排好序的输入序列，该算法的效率较低，近似于。