惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

人人都是产品经理
人人都是产品经理
量子位
月光博客
月光博客
罗磊的独立博客
宝玉的分享
宝玉的分享
博客园_首页
酷 壳 – CoolShell
酷 壳 – CoolShell
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
WordPress大学
WordPress大学
博客园 - 叶小钗
博客园 - 聂微东
阮一峰的网络日志
阮一峰的网络日志
V
V2EX
雷峰网
雷峰网
博客园 - 三生石上(FineUI控件)
Jina AI
Jina AI
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
博客园 - Franky
美团技术团队
爱范儿
爱范儿
V
Visual Studio Blog
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
H
Hackread – Cybersecurity News, Data Breaches, AI and More
Y
Y Combinator Blog

博客园 - Eagle6970

ASP.NET Core实现MCP Streamable HTTP 豆包生成C#微博API HTTP调用实例代码 豆包生成C#即梦API HTTP调用实例代码 SQL Server - sp_spaceused 子网掩码和IP地址范围 [VS Code] Run JavaScript [VS Code] Copy所有包含关键字的行 [数据结构学习笔记25] 归并排序(Merge Sort) [VS Code] 使用dotnet CLI安装和管理NuGet包 [数据结构学习笔记24] 选择排序(Selection Sort) [数据结构学习笔记23] 插入排序(Insertion Sort) [数据结构学习笔记22] 冒泡排序(Bubblesort) [数据结构学习笔记20] 深度优先搜索(DFS)和广度优先搜索(BFS) [数据结构学习笔记19] 二叉树遍历(Binary Tree Traversal) [数据结构学习笔记18] 二分查找(Binary Search) [数据结构学习笔记17] 线性查找(Linear Search) [数据结构学习笔记16] 汉诺塔(Towers of Hanoi) [数据结构学习笔记15] 斐波那契数列(Fibonacci) [数据结构学习笔记14] 递归简介(Recursion)
[数据结构学习笔记21] 快速排序(Quicksort)
Eagle6970 · 2025-02-07 · via 博客园 - Eagle6970

快速排序(Quicksort)真的很快,因为它用了分而治之的思想。

基本思想:

1. 选一个中间点的值作为中心点(pivot)

2. 以中心点为基准

  2.1 小于中心点的值,放中心点左边

  2.2 大于中心点的值,放中心点右边

3. 对左右数列,重复1,2,最终会得到排好序的数列。

数列举例

4,10,7,3,5,12,40,1,33

中间的数取5(pivot)

第一轮排序

1,4,3,5,12,40,33,10,7 

第二轮排5左右两边的数列

1,4,3,5,12,40,33,10,7 

1,3,4,5,12,10,7,33,40 

第三轮

1,345,12,10,7,3340 

1,345,7,10,12,3340 

代码实现(javascript)

function quickSortHelper(arrayInput, left, right) {
  let i = left;
  let j = right;
  let pivotPoint = arrayInput[Math.round((left + right) / 2)];

  // loop
  while (i <= j) {
     while (arrayInput[i] < pivotPoint) {
        i++;
     }
     while (arrayInput[j] > pivotPoint) {
         j--;
     }

     if (i <= j) {
         let tempStore = arrayInput[i];
         arrayInput[i] = arrayInput[j]'
         i++;
         arrayInput[j] = tempStore;
         j--;
      }
  }

  if (left < j) {
        quickSortHelper(arrayInput, left, j);
   }
  if (i < right) {
        quickSortHelper(arrayInput, i, right);
   }

   return arrayInput;
}

function quickSort(input) {
  return quickSortHelper(input, 0, input.length - 1);  
}

调用

let myData = [24, 10, 17, 9, 5, 9, 1, 23, 300];
quickSort(myData);

性能分析

场景 时间复杂度 空间复杂度
最好 O(n log n) O(log n)
最坏 O(n^2) O(1)
平均 O(n log n) O(log n)

最好情况:中间点选择正好把数列平均分开,每次基本上都是一半对一半,这样有log(n)次递归,每次递归要遍历n个元素,所以复杂度为O(n log n)。

平均情况:和最好情况类似。

最坏情况:每次pivot选择的都是最大或者最小,导致分区极不均衡,这种情况下为O(n^2)。

快速排序不是稳定排序。这意味着,相同值的元素的位置在排序过程中可能会变化。