算法快学笔记（四）：快速排序的原理与实现

1. 原理介绍

快速排序是一种 排序 算法，速度比选择排序快得多，其主要基于“分而治之”的思想对集合进行排序，本文将对该算法进行分析。

2. 分而治之(D&C)的思想

D&C主要指利用递归的方式来不断的缩小需要处理问题的规模，最终使问题容易解决。使用D&C解决问题的过程包括两个步骤。

(1) 找出递归的终止条件，这种条件必须尽可能简单（称为基线

条件）。

(2) 不断将问题分解（或者说缩小规模），直到符合递归的终止条件(称为归纳条件)。

为了便于理解，举个例子。

假设有一个数组A=[2,4,6], 想要统计A所有元素的和，可以使用两种方式

1. 遍历A,并将结果一个一个的加起来
2. 使用D&C思想，通过不断缩小集合的规模，最终把每次递归的结果加起来，流程如下

代码如下：

// 使用dc的思想统计一个数组元素的和
func Sum(ints [] int) int {
	if len(ints)==1{
		//当集合只有一个元素时，返回结果
		return ints[0]
	}
	subArr := ints[1:]
	//每次递归的时候，传个Sum的集合数量都比上一次少一个元素
	return ints[0]+Sum(subArr)
}

3. 快速排序的原理

快速排序的流程大概分为两步：

1. 确定递归的终止条件：对于排序操作而言，如果数组为空或只包含一个元素，则只需原样返回数组且不用排序。因此数组为空或只包含一个元素可以作为循环结束的条件

2. 如果没有满足递归终止条件，需要将数组分解，并做以下操作，直到满足递归终止条件。

   2.1. 从数组中选择一个元素，这个元素被称为基准值

   2.2. 将数组分成两个子数组：小于基准值的元素和大于基准值的元素

   2.3. 对步骤2产生的两个子数组再执行快速排序操作

假设要对[2,1,3,5,4]进行排序，选择了3为基准值，则流程大概如下：

对于快速排序，在基线条件中，我证明这种算法对空数组或包含一个

元素的数组管用。在归纳条件中，如果快速排序对包含一个元素的数组管用，对包含两个元素的数组也将管用；如果它对包含两个元素的数组管用，对包含三个元素的数组也将管用，以此类推。因此，可以说明快速排序对任何长度的数组都管用。

4. 运行时间分析

快速排序的平均情况运行的时间复杂度为O(n log n),但在最糟糕的情况下其复杂度将为O(n^2),下面对两种情况进行分析

4.1 最糟糕情况

下面来看看到底啥时候才会出现最糟糕的情况，考虑如下的排序：

快速排序的性能高度依赖于你选择的基准值。假设你总是将第一个元素用作基准值，且要处

理的数组是有序的。由于快速 排序算法 不检查输入数组是否有序，因此它依然尝试对其进行排序，需要进行N层操作，每层需要比较N个数。所以算法复杂度为O(n^2)

4.2 最佳情况

考虑如下排序:

该图也是对有序数组进行排序，但每次都选择中间的元素作为基准值，此时递归的次数变成了3次(logN),每次也是需要比较N个元素，所以算法复杂度为O(n log n)

5. 代码实现

为了简单演示，代码都始终选用第一个元素作为基准值

Python版本：

def quicksort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)
print quicksort([3,5,6,2,6,2])

• D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元
  素的数组。
• 快速排序的平均运行时间为O(n log n)。
• 当数组有序，始终选择第一元素作为基准值时，快速排序将出现最糟情况
• 当数组有序，始终选择中间元素作为基准值时，快速排序将出现最佳情况