经验首页 前端设计 程序设计 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. }
  7. var pivot
  8. const left = []
  9. const right = []
  10. // 设置中间数,取最中间的项
  11. var midIndex = Math.floor(arr.length / 2)
  12. pivot = arr[midIndex]
  13. for (var i = 0, l = arr.length; i < l; i++) {
  14. console.log('i=' + i + ' midIndex=' + midIndex + ' pivot=' + pivot + ' arr[]=' + arr)
  15. // 当中间基数等于i时跳过。基数数待递归完成时合并到到新数组。
  16. if (midIndex === i) {
  17. continue
  18. }
  19. // 当前数组里面的项小于基数则添加到左侧
  20. if (arr[i] < pivot) {
  21. left.push(arr[i])
  22. // 大于等于则添加到右侧
  23. } else {
  24. right.push(arr[i])
  25. }
  26. }
  27. arr = quickSort1(left).concat(pivot, quickSort1(right))
  28. console.log('sorted array:', arr)
  29. // 递归调用遍历左侧和右侧,再将中间值连接起来
  30. return arr
  31. }

 

递归的过程

  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. }
  26. // 分区递归版本,分区递归调用。
  27. function quickSort2(arr, left, right) {
  28. left = left !== undefined ? left : 0
  29. right = right !== undefined ? right : arr.length - 1
  30. if (left < right) {
  31. var pivot = partition(arr, left, right)
  32. quickSort2(arr, left, pivot - 1)
  33. quickSort2(arr, pivot + 1, right)
  34. }
  35. return arr
  36. }

 

快排方式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]
  7. // 当左侧小于等于右侧则表示还有项没有对比,需要继续
  8. while (i <= j) {
  9. // 当左侧小于基准时查找位置右移,直到找出比基准值大的位置来
  10. while (arr[i] < pivot) {
  11. console.log('arr[i] < pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot)
  12. i++
  13. }
  14. // 当前右侧大于基准时左移,直到找出比基准值小的位置来
  15. while (arr[j] > pivot) {
  16. console.log('arr[j] > pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot)
  17. j--
  18. }
  19. console.log(' left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + ' midIndex=' + midIndex + ' pivot=' + pivot + ' arr[]=' + arr)
  20. // 当左侧位置小于等于右侧时,将数据交换,小的交换到基准左侧,大的交换到右侧
  21. if (i <= j) {
  22. [arr[i], arr[j]] = [arr[j], arr[i]]
  23. // 缩小搜查范围,直到左侧都小于基数,右侧都大于基数
  24. i++
  25. j--
  26. }
  27. }
  28. // 左侧小于基数位置,不断递归左边部分
  29. if (left < j) {
  30. console.log('left < j:recursion: left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]' + arr)
  31. quickSort3(arr, left, j)
  32. }
  33. // 基数位置小于右侧,不断递归右侧部分
  34. if (i < right) {
  35. console.log('i < right:recursion: left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]' + arr)
  36. quickSort3(arr, i, right)
  37. }
  38. return arr
  39. }

 

快排方式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)
  11. while (stack.length) {
  12. // 如果栈内还有数据,则一并马上取出,其他逻辑与标准递归版同
  13. j = right = stack.pop()
  14. i = left = stack.pop()
  15. midIndex = Math.floor((i + j) / 2)
  16. pivot = arr[midIndex]
  17. while (i <= j) {
  18. while (arr[i] < pivot) {
  19. console.log('arr[i] < pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot + 'arr[]=' + arr)
  20. i++
  21. }
  22. while (arr[j] > pivot) {
  23. console.log('arr[j] > pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot + 'arr[]=' + arr)
  24. j--
  25. }
  26. if (i <= j) {
  27. tmp = arr[j]
  28. arr[j] = arr[i]
  29. arr[i] = tmp
  30. i++
  31. j--
  32. }
  33. }
  34. if (left < j) {
  35. // 与递归版不同,这里当左侧小于基数位置时添加到栈中,以便继续循环
  36. console.log('left < j:recursion: left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]=' + arr)
  37. stack.push(left)
  38. stack.push(j)
  39. }
  40. if (i < right) {
  41. // 当右侧大于等于基数位置时添加到栈中,以便继续循环
  42. console.log('i < right:recursion: left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]=' + arr)
  43. stack.push(i)
  44. stack.push(right)
  45. }
  46. }
  47. return arr
  48. }

 

测试

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

 

链接

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

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

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

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

本站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号