快速排序的时间复杂度分析

上一章节已经为大家详细讲解了排序的相关概念，现在本文将专注于为大家详细介绍快速排序。

快速排序（Quicksort）是对冒泡排序的一种改进，属于交换类排序算法。该算法由C. A. R. Hoare在1960年提出，其基本思想是通过一趟排序将待排序的数据分割成两部分，其中一部分的所有数据都比另一部分小，然后再按此方法对这两部分数据分别进行快速排序，从而实现对整个数据的排序。这种算法体现了分而治之的思想。

在快速排序中，首先要选取一个元素作为分界值，将大于该分界值的元素放到数组的右边，小于分界值的元素放到数组的左边，等于分界值的元素位置不变。然后不断迭代上述规则完成排序。

快速排序的具体原理如下：

1. 设定一个分界值，将数组分成左右两部分。

2. 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。左边部分中各元素都小于或等于分界值，右边部分中各元素都大于或等于分界值。

3. 然后对左右两部分数据独立进行排序。对左侧的数组数据再取一个分界值，将该部分数据继续分成左右两部分，右边部分的数据也可进行类似处理。

4. 重复上述过程，可以看出这是一个递归定义的过程。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左右两部分数据都排序完成后，整个数组的排序也就完成了。

接下来，我们来谈谈快速排序的时间复杂度。快速排序的一次划分算法从两头交替搜索，直至left和right重合，因此其时间复杂度是O(n)。而整个快速排序算法的时间复杂度与划分的趟数有关。

在最理想的情况下，每次划分所选择的中间数恰好将当前序列几乎等分。经过log2n趟划分，便可以得到长度为1的子表，这样整个算法的时间复杂度为O(nlog₂n)。在最坏的情况下，每次所选的中间数是当前序列中的最大或最小元素。这可能导致每次划分所得的子表中一个为空表，另一子表的长度为原表的长度减1，使得时间复杂度为O(n²)。

为改善最坏情况下的时间性能，可以采用其他方法选取中间数。通常采用的是“三者值取中”方法，即比较H->r[left].key、H->r[right].key与H->r[(left + right)/2].key，选择三者中关键字为中值的元素作为中间数。