快速排序（Python）

╰+哭是因爲堅強的太久メ 2022-03-24 15:07 293阅读 0赞

# 快速排序 #

<table> 
 <thead> 
 <tr> 
 <th>排序算法</th> 
 <th>平均时间复杂度</th> 
 <th>空间复杂度</th> 
 <th>稳定性</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/112305019" rel="nofollow">冒泡排序</a></td> 
 <td> O ( n 2 ) O(n^2) O(n2)</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td>稳定</td> 
 </tr> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/112305118" rel="nofollow">选择排序</a></td> 
 <td> O ( n 2 ) O(n^2) O(n2)</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td>不稳定</td> 
 </tr> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/86178111" rel="nofollow">插入排序</a></td> 
 <td> O ( n 2 ) O(n^2) O(n2)</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td>稳定</td> 
 </tr> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/86178111" rel="nofollow">希尔排序</a></td> 
 <td> O ( n log ⁡ 2 n ) O(n\log^2 n) O(nlog2n)</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td>不稳定</td> 
 </tr> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/112305240" rel="nofollow">归并排序</a></td> 
 <td> O ( n log ⁡ 2 n ) O(n\log^2 n) O(nlog2n)</td> 
 <td> O ( n ) O(n) O(n)</td> 
 <td>稳定</td> 
 </tr> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/86591978" rel="nofollow">快速排序</a></td> 
 <td> O ( n log ⁡ n ) O(n\log n) O(nlogn)</td> 
 <td> O ( log ⁡ n ) O(\log n) O(logn)</td> 
 <td>不稳定</td> 
 </tr> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/86582643" rel="nofollow">堆排序</a></td> 
 <td> O ( n log ⁡ n ) O(n\log n) O(nlogn)</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td>不稳定</td> 
 </tr> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/86632295" rel="nofollow">计数排序</a></td> 
 <td> O ( n + k ) O(n+k) O(n+k)</td> 
 <td> O ( k ) O(k) O(k)</td> 
 <td>稳定</td> 
 </tr> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/86632295" rel="nofollow">基数排序</a></td> 
 <td> O ( n × k ) O(n\times k) O(n×k)</td> 
 <td></td> 
 <td>稳定</td> 
 </tr> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/86632295" rel="nofollow">桶排序</a></td> 
 <td> O ( n ) O(n) O(n)</td> 
 <td> O ( m ) O(m) O(m)</td> 
 <td>稳定</td> 
 </tr> 
 </tbody> 
</table>

## 1. 算法思路 ##

快速排序是一个采用分而治之思路的递归算法，对于一个待排序数列，快速排序会从数列中挑出一个元素，称为“基准”(pivot)，将数列中所有比基准值小的元素移动到基准的前边，将所有比基准值大的元素移动到基准的后边，再递归的用该方法排序大于以及小于基准的子数列。

## 2. 算法实现 ##

话不多说直接上图！！！![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTMwODU3Mw_size_16_color_FFFFFF_t_70]

def quick_sort(arr, start, end):
 if start >= end:
 return
 
 pivot = partition(arr, start, end)
 quick_sort(arr, start, pivot - 1)
 quick_sort(arr, pivot + 1, end)
 
 def partition(arr, start, end):
 lt, pivot = start, end
 for i in range(start, end):
 if arr[i] < arr[pivot]:
 arr[lt], arr[i] = arr[i], arr[lt]
 lt += 1
 arr[lt], arr[end] = arr[end], arr[lt]
 return lt

### 图片及知识来源 ###

<<算法导论>>第7章堆排序

--------------------

本博客文章仅供博主学习交流，博主才疏学浅，语言表达能力有限，对知识的理解、编写代码能力都有很多不足，希望各路大神多多包涵，多加指点。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTMwODU3Mw_size_16_color_FFFFFF_t_70]: /images/20220323/c1c377ca867e4c4197e115a727f3a123.png