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

偏执的太偏执、 2022-04-03 10:11 166阅读 0赞

# 1. 原理介绍 #

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

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

D&C主要指利用递归的方式来不断的缩小需要处理问题的规模，最终使问题容易解决。使用D&C解决问题的过程包括两个步骤。  
(1) 找出递归的终止条件，这种条件必须尽可能简单（称为基线  
条件）。  
(2) 不断将问题分解（或者说缩小规模），直到符合递归的终止条件(称为归纳条件)。

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

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70]  
代码如下：

// 使用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为基准值，则流程大概如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 1]

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

# 4. 运行时间分析 #

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

## 4.1 最糟糕情况 ##

下面来看看到底啥时候才会出现最糟糕的情况，考虑如下的排序：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 2]

快速排序的性能高度依赖于你选择的基准值。假设你总是将第一个元素用作基准值，且要处  
理的数组是有序的。由于快速排序算法不检查输入数组是否有序，因此它依然尝试对其进行排序，需要进行N层操作，每层需要比较N个数。所以算法复杂度为O(n^2)

## 4.2 最佳情况 ##

考虑如下排序:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 3]

该图也是对有序数组进行排序，但每次都选择中间的元素作为基准值，此时递归的次数变成了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)。
 *  当数组有序，始终选择第一元素作为基准值时，快速排序将出现最糟情况
 *  当数组有序，始终选择中间元素作为基准值时，快速排序将出现最佳情况

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70]: /images/20220403/f2bdf85031314fb0becf69b06c2ad6c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 1]: /images/20220403/2753e97a02434086a7b2f54ddf20bea3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 2]: /images/20220403/e7201d3adaeb4ce398f5aa2d9fc509e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 3]: /images/20220403/e945f70654684f7b973c8b1dea3dc5e8.png