经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » Java相关 » Java » 查看文章
【JavaScript快速排序算法】不同版本原理分析
来源：cnblogs　　作者：刀法如飞　　时间：2023/3/27 14:49:52　　对本文有异议

说明

快速排序（QuickSort），又称分区交换排序（partition-exchange sort），简称快排。快排是一种通过基准划分区块，再不断交换左右项的排序方式，其采用了分治法，减少了交换的次数。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归或迭代进行，以此让整个数列变成有序序列。

实现过程

  1. 在待排序区间找到一个基准点(pivot)，便于理解一般是位于数组中间的那一项。
  2. 逐个循环数组将小于基准的项放左侧，将大于基准的项放在右侧。一般通过交换的方式来实现。
  3. 将基准点左侧全部项和基点右侧全部项分别通过递归(或迭代)方式重复第1项，直到所有数组都交换完成。

示意图

 

解释：以某个数字为基点，这里取最右侧的数字8，以基点划分为两个区间，将小于8的数字放在左侧区间，将大于8的数字放在右侧区间。再将左侧区间和右侧区间分别放到递归，按照最右侧为基点，继续分解。直到分解完毕，排序完成。这是其中一种常见的分区递归法，除了这种方式外，还有其他实现方式。

性能分析

平均时间复杂度：O(NlogN)
最佳时间复杂度：O(NlogN)
最差时间复杂度：O(N^2)
空间复杂度：根据实现方式的不同而不同，可以查看不同版本的源码

代码

快排方式1, 新建数组递归版本。无需交换，每个分区都是新数组，数量庞大。

这个版本利用了JS数组可变且随意拼接的特性，让每个分区都是一个新数组，从而无需交换数组项。
这个方式非常简单易懂，但理论上来讲不是完全意义上的快排，效率较差。

  1. function quickSort1(arr) {
  2.   // 数组长度为1就不再分解
  3.   console.log('origin array:', arr)
  4.   if (arr.length <= 1) {
  5.     return arr
  6.   }
  8.   var pivot
  9.   const left = []
  10.   const right = []
  11.   // 设置中间数，取最中间的项
  12.   var midIndex = Math.floor(arr.length / 2)
  13.   pivot = arr[midIndex]
  15.   for (var i = 0, l = arr.length; i < l; i++) {
  16.     console.log('i=' + i + ' midIndex=' + midIndex + ' pivot=' + pivot + ' arr[]=' + arr)
  17.     // 当中间基数等于i时跳过。基数数待递归完成时合并到到新数组。
  18.     if (midIndex === i) {
  19.       continue
  20.     }
  21.     // 当前数组里面的项小于基数则添加到左侧
  22.     if (arr[i] < pivot) {
  23.       left.push(arr[i])
  24.       // 大于等于则添加到右侧
  25.     } else {
  26.       right.push(arr[i])
  27.     }
  28.   }
  30.   arr = quickSort1(left).concat(pivot, quickSort1(right))
  31.   console.log('sorted array:', arr)
  32.   // 递归调用遍历左侧和右侧，再将中间值连接起来
  33.   return arr
  34. }

 

递归的过程

  1. // 基于中间位置进行递归分解：
  2.       f([7, 11, 9, 10, 12, 13, 8])
  3.             /       10                f([7, 9, 8])           f([11, 12, 13])
  4.         /   9    \             /    12        f([7, 8])    f([])       f([11])       f[13]
  5.    /   8  f([7]) f([])
  6.   [7]
  7. // 将递归后的最小单元和基数连接起来
  8. // 得到：[7, 8, 9, 10, 11, 12, 13]

 

快排方式2, 标准分区递归版本。左右分区递归交换排序，无需新建数组。

这个版本是最常见的标准分区版本，简单好懂。先写一个分区函数，依据基准值把成员项分为左右两部分。基准值可以是数列中的任意一项，为了交换方便，基准值一般最左或最右侧项。把小于基准值的放在左侧，大于基准值的放在右侧，最后返回分区索引。这样就得到一个基于基准值的左右两个部分。再将左右两个部分，分别进行分区逻辑的递归调用，当左右值相等，也就是最小分区只有1项时终止。

  1. // 分区函数，负责把数组分按照基准值分为左右两部分
  2. // 小于基准的在左侧，大于基准的在右侧最后返回基准值的新下标
  3. function partition(arr, left, right) {
  4.   // 基准值可以是left与right之间的任意值，再将基准值移动至最左或最右即可。
  5.   // 直接基于中间位置排序，则需要基于中间位置左右交换，参加基于中间位置交换的版本。
  6.   // var tmpIndex = Math.floor((right - left) / 2)
  7.   // ;[arr[left + tmpIndex], arr[right]] = [arr[right], arr[left + tmpIndex]]
  8.  
  9.   var pivotIndex = right
  10.   var pivot = arr[pivotIndex]
  11.   var partitionIndex = left - 1
  12.   for (var i = left; i < right; i++) {
  13.     // 如果比较项小于基准值则进行交换，并且分区索引增加1位
  14.     // 也就是将大于基准值的全部往右侧放，以分区索引为分割线
  15.     if (arr[i] < pivot) {
  16.       partitionIndex++
  17.       if (partitionIndex !== i) {
  18.         [arr[partitionIndex], arr[i]] = [arr[i], arr[partitionIndex]]
  19.       }
  20.     }
  21.   }
  22.   partitionIndex++;
  23.   [arr[partitionIndex], arr[pivotIndex]] = [arr[pivotIndex], arr[partitionIndex]]
  24.   return partitionIndex
  25. }
  27. // 分区递归版本，分区递归调用。
  28. function quickSort2(arr, left, right) {
  29.   left = left !== undefined ? left : 0
  30.   right = right !== undefined ? right : arr.length - 1
  31.   if (left < right) {
  32.     var pivot = partition(arr, left, right)
  33.     quickSort2(arr, left, pivot - 1)
  34.     quickSort2(arr, pivot + 1, right)
  35.   }
  36.   return arr
  37. }

 

快排方式3, 标准左右交换递归版本。基于中间位置不断左右交换，无需新建数组。

此版本基于中间位置，建立双指针，同时从前往后和从后往前遍历，从左侧找到大于基准值的项，从右侧找到小于基准值的项。
再将大于基准值的挪到右侧，将小于基准值的项挪到左侧，直到左侧位置大于右侧时终止。左侧位置小于基准位置则递归调用左侧区间，右侧大于基准位置则递归调用右侧区间，直到所有项排列完成。

  1. function quickSort3(arr, left, right) {
  2.   var i = left = left !== undefined ? left : 0
  3.   var j = right = right !== undefined ? right : arr.length - 1
  4.   // 确定中间位置，基于中间位置不停左右交换
  5.   var midIndex = Math.floor((i + j) / 2)
  6.   var pivot = arr[midIndex]
  8.   // 当左侧小于等于右侧则表示还有项没有对比，需要继续
  9.   while (i <= j) {
  10.     // 当左侧小于基准时查找位置右移，直到找出比基准值大的位置来
  11.     while (arr[i] < pivot) {
  12.       console.log('arr[i] < pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot)
  13.       i++
  14.     }
  15.     // 当前右侧大于基准时左移，直到找出比基准值小的位置来
  16.     while (arr[j] > pivot) {
  17.       console.log('arr[j] > pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot)
  18.       j--
  19.     }
  21.     console.log('  left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + ' midIndex=' + midIndex + ' pivot=' + pivot + ' arr[]=' + arr)
  23.     // 当左侧位置小于等于右侧时，将数据交换，小的交换到基准左侧，大的交换到右侧
  24.     if (i <= j) {
  25.       [arr[i], arr[j]] = [arr[j], arr[i]]
  26.       // 缩小搜查范围，直到左侧都小于基数，右侧都大于基数
  27.       i++
  28.       j--
  29.     }
  30.   }
  32.   // 左侧小于基数位置，不断递归左边部分
  33.   if (left < j) {
  34.     console.log('left < j:recursion:  left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]' + arr)
  35.     quickSort3(arr, left, j)
  36.   }
  37.   // 基数位置小于右侧，不断递归右侧部分
  38.   if (i < right) {
  39.     console.log('i < right:recursion:  left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]' + arr)
  40.     quickSort3(arr, i, right)
  41.   }
  43.   return arr
  44. }

 

快排方式4, 非递归左右交换版本。基于中间位置不断左右交换，利用stack或queue遍历。

这种方式标准左右交换递归版本的非递归版本，其原理一样，只是不再递归调用，而是通过stack来模拟递归效果。这种方式性能最好。

  1. function quickSort4(arr, left, right) {
  2.   left = left !== undefined ? left : 0
  3.   right = right !== undefined ? right : arr.length - 1
  4.  
  5.   var stack = []
  6.   var i, j, midIndex, pivot, tmp
  7.   // 与标准递归版相同，只是将递归改为遍历栈的方式
  8.   // 先将左右各取一个入栈
  9.   stack.push(left)
  10.   stack.push(right)
  12.   while (stack.length) {
  13.     // 如果栈内还有数据，则一并马上取出，其他逻辑与标准递归版同
  14.     j = right = stack.pop()
  15.     i = left = stack.pop()
  16.     midIndex = Math.floor((i + j) / 2)
  17.     pivot = arr[midIndex]
  18.     while (i <= j) {
  19.       while (arr[i] < pivot) {
  20.         console.log('arr[i] < pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot + 'arr[]=' + arr)
  21.         i++
  22.       }
  23.       while (arr[j] > pivot) {
  24.         console.log('arr[j] > pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot + 'arr[]=' + arr)
  25.         j--
  26.       }
  28.       if (i <= j) {
  29.         tmp = arr[j]
  30.         arr[j] = arr[i]
  31.         arr[i] = tmp
  32.         i++
  33.         j--
  34.       }
  35.     }
  36.     if (left < j) {
  37.       // 与递归版不同，这里当左侧小于基数位置时添加到栈中，以便继续循环
  38.       console.log('left < j:recursion:  left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]=' + arr)
  39.       stack.push(left)
  40.       stack.push(j)
  41.     }
  42.     if (i < right) {
  43.       // 当右侧大于等于基数位置时添加到栈中，以便继续循环
  44.       console.log('i < right:recursion:  left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]=' + arr)
  45.       stack.push(i)
  46.       stack.push(right)
  47.     }
  48.   }
  49.   return arr
  50. }

 

测试

  1. (function () {
  2.   const arr = [7, 11, 9, 10, 12, 13, 8]
  3.   // 构建数列，可以任意构建，支持负数，也不限浮点
  4.   // const arr = [17, 31, 12334, 9.545, -10, -12, 1113, 38]
  6.   console.time('sort1')
  7.   const arr1 = arr.slice(0)
  8.   console.log('sort1 origin:', arr1)
  9.   console.log('\r\nquickSort1 sorted:', quickSort1(arr1))
  10.   console.timeEnd('sort1')
  12.   console.time('sort2')
  13.   const arr2 = arr.slice(0)
  14.   console.log('sort2 origin:', arr2)
  15.   console.log('\r\nquickSort2 sorted:', quickSort2(arr2))
  16.   console.timeEnd('sort2')
  18.   console.time('sort3')
  19.   const arr3 = arr.slice(0)
  20.   console.log('sort3 origin:', arr3)
  21.   console.log('\r\nquickSort3 sorted:', quickSort3(arr3))
  22.   console.timeEnd('sort3')
  24.   console.time('sort4')
  25.   const arr4 = arr.slice(0)
  26.   console.log('sort4 origin:', arr4)
  27.   console.log('\r\nquickSort4 sorted:', quickSort4(arr4))
  28.   console.timeEnd('sort4')
  29. })()
  31. /**
  32. // 测试结果
  33. jarry@jarrys-MacBook-Pro quicksort % node quick_sort.js
  34. sort1 origin: [
  35.    7, 11, 9, 10,
  36.   12, 13, 8
  37. ]
  38. origin array: [
  39.    7, 11, 9, 10,
  40.   12, 13, 8
  41. ]
  42. i=0 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
  43. i=1 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
  44. i=2 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
  45. i=3 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
  46. i=4 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
  47. i=5 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
  48. i=6 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
  49. origin array: [ 7, 9, 8 ]
  50. i=0 midIndex=1 pivot=9 arr[]=7,9,8
  51. i=1 midIndex=1 pivot=9 arr[]=7,9,8
  52. i=2 midIndex=1 pivot=9 arr[]=7,9,8
  53. origin array: [ 7, 8 ]
  54. i=0 midIndex=1 pivot=8 arr[]=7,8
  55. i=1 midIndex=1 pivot=8 arr[]=7,8
  56. origin array: [ 7 ]
  57. origin array: []
  58. sorted array: [ 7, 8 ]
  59. origin array: []
  60. sorted array: [ 7, 8, 9 ]
  61. origin array: [ 11, 12, 13 ]
  62. i=0 midIndex=1 pivot=12 arr[]=11,12,13
  63. i=1 midIndex=1 pivot=12 arr[]=11,12,13
  64. i=2 midIndex=1 pivot=12 arr[]=11,12,13
  65. origin array: [ 11 ]
  66. origin array: [ 13 ]
  67. sorted array: [ 11, 12, 13 ]
  68. sorted array: [
  69.    7,  8,  9, 10,
  70.   11, 12, 13
  71. ]
  73. quickSort1 sorted: [
  74.    7,  8,  9, 10,
  75.   11, 12, 13
  76. ]
  77. sort1: 9.824ms
  78. sort2 origin: [
  79.    7, 11, 9, 10,
  80.   12, 13, 8
  81. ]
  82. partitioned arr= [
  83.    7,  8,  9, 10,
  84.   12, 13, 11
  85. ] partitionIndex: 1 left= [ 7 ] arr[partitionIndex]= 8 right= [ 8, 9, 10, 12, 13, 11 ] [
  86.    7,  8,  9, 10,
  87.   12, 13, 11
  88. ]
  89. partitioned arr= [
  90.    7,  8,  9, 10,
  91.   11, 13, 12
  92. ] partitionIndex: 4 left= [ 9, 10 ] arr[partitionIndex]= 11 right= [ 11, 13, 12 ] [
  93.    7,  8,  9, 10,
  94.   11, 13, 12
  95. ]
  96. partitioned arr= [
  97.    7,  8,  9, 10,
  98.   11, 13, 12
  99. ] partitionIndex: 3 left= [ 9 ] arr[partitionIndex]= 10 right= [ 10 ] [
  100.    7,  8,  9, 10,
  101.   11, 13, 12
  102. ]
  103. partitioned arr= [
  104.    7,  8,  9, 10,
  105.   11, 12, 13
  106. ] partitionIndex: 5 left= [] arr[partitionIndex]= 12 right= [ 12, 13 ] [
  107.    7,  8,  9, 10,
  108.   11, 12, 13
  109. ]
  111. quickSort2 sorted: [
  112.    7,  8,  9, 10,
  113.   11, 12, 13
  114. ]
  115. sort2: 1.15ms
  116. sort3 origin: [
  117.    7, 11, 9, 10,
  118.   12, 13, 8
  119. ]
  120. arr[i] < pivot:  i=0 j=6 pivot=10
  121.   left=0 right=6 i=1 j=6 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
  122. arr[i] < pivot:  i=2 j=5 pivot=10
  123. arr[j] > pivot:  i=3 j=5 pivot=10
  124. arr[j] > pivot:  i=3 j=4 pivot=10
  125.   left=0 right=6 i=3 j=3 midIndex=3 pivot=10 arr[]=7,8,9,10,12,13,11
  126. left < j:recursion:  left=0 right=6 i=4 j=2arr[]7,8,9,10,12,13,11
  127. arr[i] < pivot:  i=0 j=2 pivot=8
  128. arr[j] > pivot:  i=1 j=2 pivot=8
  129.   left=0 right=2 i=1 j=1 midIndex=1 pivot=8 arr[]=7,8,9,10,12,13,11
  130. i < right:recursion:  left=0 right=6 i=4 j=2arr[]7,8,9,10,12,13,11
  131. arr[i] < pivot:  i=4 j=6 pivot=13
  132.   left=4 right=6 i=5 j=6 midIndex=5 pivot=13 arr[]=7,8,9,10,12,13,11
  133. left < j:recursion:  left=4 right=6 i=6 j=5arr[]7,8,9,10,12,11,13
  134.   left=4 right=5 i=4 j=5 midIndex=4 pivot=12 arr[]=7,8,9,10,12,11,13
  136. quickSort3 sorted: [
  137.    7,  8,  9, 10,
  138.   11, 12, 13
  139. ]
  140. sort3: 0.595ms
  141. sort4 origin: [
  142.    7, 11, 9, 10,
  143.   12, 13, 8
  144. ]
  145. arr[i] < pivot:  i=0 j=6 pivot=10arr[]=7,11,9,10,12,13,8
  146. arr[i] < pivot:  i=2 j=5 pivot=10arr[]=7,8,9,10,12,13,11
  147. arr[j] > pivot:  i=3 j=5 pivot=10arr[]=7,8,9,10,12,13,11
  148. arr[j] > pivot:  i=3 j=4 pivot=10arr[]=7,8,9,10,12,13,11
  149. left < j:recursion:  left=0 right=6 i=4 j=2arr[]=7,8,9,10,12,13,11
  150. i < right:recursion:  left=0 right=6 i=4 j=2arr[]=7,8,9,10,12,13,11
  151. arr[i] < pivot:  i=4 j=6 pivot=13arr[]=7,8,9,10,12,13,11
  152. left < j:recursion:  left=4 right=6 i=6 j=5arr[]=7,8,9,10,12,11,13
  153. arr[i] < pivot:  i=0 j=2 pivot=8arr[]=7,8,9,10,11,12,13
  154. arr[j] > pivot:  i=1 j=2 pivot=8arr[]=7,8,9,10,11,12,13
  156. quickSort4 sorted: [
  157.    7,  8,  9, 10,
  158.   11, 12, 13
  159. ]
  160. sort4: 0.377ms
  161.  */

 

链接

多种语言实现快速排序算法源码：https://github.com/microwind/algorithms/tree/master/sorts/quicksort

其他排序算法源码：https://github.com/microwind/algorithms

原文链接：https://www.cnblogs.com/letjs/p/17260989.html

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

Java热门文章

  • 【IDEA】Application context not configured for this file
  • [IDEA] chapter_reader - idea看小说插件 idea阅读插件 idea摸鱼插件
  • thrift常见异常及原因分析
  • Java 调用 PaddleDetection 模型
  • JVM 详解，大白话带你认识 JVM
  • spring-boot-2.0.3不一样系列之番外篇 - @Configuration、Condition与@Conditional
  • Java Comparator.comparing比较导致空指针异常的解决
  • Java使用EasyExcel进行单元格合并的问题详解
  • 死磕 java集合之ArrayBlockingQueue源码分析
  • Java基础之集合Set详解

    • Java推荐文章

  • 面试场景题：一次关于线程池使用场景的讨论。
  • 前端黑科技：使用 JavaScript 实现网页扫码功能
  • 聊一聊 Netty 数据搬运工 ByteBuf 体系的设计与实现
  • 简单设计一个JAVA并行处理工具类
  • 【杂谈】JPA乐观锁改悲观锁遇到的一些问题与思考
  • 认识netty的基本组件
  • Jenkins如何使用CrumbIssuer防御CSRF攻击
  • 如何平稳地从nacos迁移到r-nacos？
  • 线程池遇到父子任务，有大坑，要注意！
  • Java JVM——12. 垃圾回收理论概述

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号