快速排序算法详解

简介: 快速排序算法详解

一、引言

快速排序(Quicksort)是一种基于分治策略的排序算法,由英国计算机科学家托尼·霍尔于1960年提出。它通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。快速排序的排序效率在同为O(nlogn)的排序方法中非常高。

二、算法原理

快速排序的核心思想是分治。它将一个数组分成两个子数组,其中一个子数组的所有元素都比另一个子数组的元素小,然后递归地对这两个子数组进行快速排序。这个分割过程通常通过一个基准元素(pivot)来完成。

快速排序的步骤如下:

1.选择基准元素:通常选择数组的第一个元素、最后一个元素或中间元素作为基准元素。

2.分区操作:将数组分成两个子数组,左侧子数组的所有元素都小于基准元素,右侧子数组的所有元素都大于或等于基准元素。

3.递归排序:对左侧和右侧子数组分别进行快速排序。

三、算法实现(Python)

下面是一个使用Python实现的快速排序算法:

python复制代码

  def quicksort(arr): 
  if len(arr) <= 1: 
  return arr 
  pivot = arr[len(arr) // 2] # 选择中间元素作为基准 
  left = [x for x in arr if x < pivot] 
  middle = [x for x in arr if x == pivot] 
  right = [x for x in arr if x > pivot] 
  return quicksort(left) + middle + quicksort(right) 
  
  # 测试代码 
  arr = [3, 6, 8, 10, 1, 2, 1] 
  print("原始数组:", arr) 
  sorted_arr = quicksort(arr) 
  print("排序后的数组:", sorted_arr)

这个实现虽然直观,但使用了列表推导式来创建新的子列表,这在大数据集上可能会导致空间效率低下。为了优化空间效率,我们可以使用原地(in-place)快速排序算法,它只使用常数级别的额外空间。

四、原地快速排序算法

python复制代码

  def partition(arr, low, high): 
  i = (low - 1) # 最小元素索引 
  pivot = arr[high] # 基准元素 
  
  for j in range(low, high): 
  if arr[j] <= pivot: 
  i = i + 1 
  arr[i], arr[j] = arr[j], arr[i] 
  
  arr[i + 1], arr[high] = arr[high], arr[i + 1] 
  return (i + 1) 
  
  def quicksort_inplace(arr, low, high): 
  if low < high: 
  pi = partition(arr, low, high) 
  quicksort_inplace(arr, low, pi - 1) 
  quicksort_inplace(arr, pi + 1, high) 
  
  # 测试代码 
  arr = [10, 7, 8, 9, 1, 5] 
  n = len(arr) 
  quicksort_inplace(arr, 0, n - 1) 
  print("排序后的数组:", arr)

在这个实现中,partition 函数负责将数组分为两部分,并返回基准元素的最终位置。然后,quicksort_inplace 函数递归地对基准元素左右两侧的子数组进行排序。

五、算法性能分析

时间复杂度

· 平均时间复杂度:O(nlogn),其中n是待排序数组的长度。这是快速排序算法的最优时间复杂度。

· 最坏时间复杂度:O(n^2)。当输入的数组已经有序或接近有序时,快速排序的性能会退化到O(n^2)。为了避免这种情况,可以选择随机基准元素或者使用三数取中法来选择基准元素。

空间复杂度

· 原地快速排序的空间复杂度为O(logn),这是因为递归调用栈的深度为logn(当数组分割平衡时)。然而,如果使用尾递归优化或迭代实现,空间复杂度可以降低到O(1)。

· 非原地快速排序(如前面的Python列表推导式实现)的空间复杂度为O(n),因为需要创建新的子列表来存储数据。

 

相关文章
|
27天前
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现(c语言)
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低,而三路快排通过将数组分为三部分(小于、等于、大于基准值)来优化这一问题。文章详细讲解了三路快排的实现步骤,并提供了完整的代码示例。
52 4
|
2月前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
27 1
|
2月前
|
搜索推荐 Java Go
深入了解快速排序算法
深入了解快速排序算法
44 2
|
2月前
|
存储 搜索推荐 算法
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
|
2月前
|
算法 Python
Python算法编程:冒泡排序、选择排序、快速排序
Python算法编程:冒泡排序、选择排序、快速排序
27 0
|
2月前
|
搜索推荐 C语言 C++
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
|
4月前
|
搜索推荐 算法 Java
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
该博客文章通过UML类图和Java源码示例,展示了如何使用适配器模式将QuickSort类和BinarySearch类的排序和查找功能适配到DataOperation接口中,实现算法的解耦和复用。
47 1
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
|
4月前
|
算法 搜索推荐
算法设计 (分治法应用实验报告)基于分治法的合并排序、快速排序、最近对问题
这篇文章是关于分治法应用的实验报告,详细介绍了如何利用分治法实现合并排序和快速排序算法,并探讨了使用分治法解决二维平面上的最近对问题的方法,包括伪代码、源代码实现及时间效率分析,并附有运行结果和小结。
|
5月前
|
算法 搜索推荐 编译器
算法高手养成记:Python快速排序的深度优化与实战案例分析
【7月更文挑战第11天】快速排序是编程基础,以O(n log n)时间复杂度和原址排序著称。其核心是“分而治之”,通过选择基准元素分割数组并递归排序两部分。优化包括:选择中位数作基准、尾递归优化、小数组用简单排序。以下是一个考虑优化的Python实现片段,展示了随机基准选择。通过实践和优化,能提升算法技能。**
60 3
|
6月前
|
搜索推荐 算法 Java
Java中的快速排序、归并排序和堆排序是常见的排序算法。
【6月更文挑战第21天】Java中的快速排序、归并排序和堆排序是常见的排序算法。快速排序采用分治,以基准元素划分数组并递归排序;归并排序同样分治,先分割再合并有序子数组;堆排序通过构建堆来排序,保持堆性质并交换堆顶元素。每种算法各有优劣:快排平均高效,最坏O(n²);归并稳定O(n log n)但需额外空间;堆排序O(n log n)且原地排序,但不稳定。
50 3