为什么 JS 中写第一种快排比标准快排慢 3 倍？

[dxcqcv]

自己学习算法，根据快排的定义实现了，但发现比标准的快排写法慢 3 倍，求高手指点一二

var c =[169, 1627, 1897, 2158, 2390, 3414, 3473, 4792, 5214, 5236, 9441, 10118, 13105, 13531, 13575, 14015, 14590, 15023, 15415, 15923, 16299, 18115, 18316, 18461, 19205, 21361, 21556, 23288, 23753, 24340, 24446, 27904, 30884, 32751, 34781, 35049, 37456, 37681, 39206, 40160, 41732, 42763, 43930, 47808, 49887, 52549, 54490, 55504, 56726, 57678, 58611, 58648, 58779, 59226, 63000, 63133, 63245, 63782, 67341, 67525, 67870, 69264, 71820, 71957, 72411, 73391, 73695, 76129, 76717, 77269, 77503, 77647, 78139, 79757, 80712, 81304, 82112, 82851, 83087, 83349, 83361, 83461, 83523, 85940, 86228, 86581, 88303, 88771, 92168, 92249, 93240, 93757, 93813, 95625, 97223, 97829, 97938, 98460, 98631, 100074, 101848, 104646, 105135, 105419, 106099, 106852, 107957, 108531, 108566, 109367, 110748, 111833, 112516, 112602, 114566, 114590, 116611, 116988, 116991, 117267, 117543, 119185, 119870, 120484, 121627, 122654, 124622, 126105, 127983, 129338, 131506, 131583, 131690, 134600, 135658, 136041, 136715, 139621, 141491, 143350, 145000, 145620, 149083, 149134, 149170, 149628, 151482, 152843, 152901, 155166, 156334, 157127, 158076, 160275, 161139, 162318, 162858, 164319, 165341, 167679, 168272, 168367, 168892, 169098, 169408, 169963, 171499, 173137, 173392, 174469, 174765, 175146, 178855,179161, 180929, 181881, 182064, 187512, 188700, 188961, 190416, 191565, 191566, 193335, 193949, 196654, 196866, 197042, 197238, 198676, 198877, 198978, 200316, 201203, 202769, 203688, 205351, 206069, 207420, 208652, 208959, 209464, 210498, 210604, 210938, 211114, 212049, 213893, 214710, 214795, 216503, 216908, 218207, 220878, 221062, 221293, 222132, 223234, 223257, 224713, 225510, 226143, 226924, 227899, 228448, 228816, 230023, 230785, 231007, 231463, 231832, 232421, 233177, 235297, 235671, 236017, 236866, 236903, 237372, 237889, 239718, 239729, 239918, 241429, 241442, 241744, 243873, 244333, 244758, 246396, 246736, 247072, 248741, 249240, 249554, 250872, 250878, 251125, 251211, 252733, 253500, 254004, 255636, 256360,258230, 259541, 259946, 260429, 260653, 260996, 261385, 261763, 262782, 263954, 265711, 266134, 266205, 266907, 268342, 269158, 270019, 273132, 273418, 273610, 274054, 274087, 274966, 277035, 278253, 279614, 280266, 280898, 281737, 282179, 283688, 285406, 288988, 290170, 290452, 293364, 294380, 295477, 295967, 296233, 296503, 297967, 298447, 298760, 298769, 300222, 301757, 301985, 302635, 303387, 303407, 303633, 306674, 307782, 308116, 308737, 309028, 310910, 310985, 311239, 311657, 311695, 312378, 313210, 313230, 313475, 314754, 315030, 315127, 317709, 318509, 319303, 319527, 319566, 320461, 320519, 323678, 324784, 326178, 326413, 329084, 333467, 334571, 334861, 335476, 339565, 339916, 343420, 344234, 345783, 346946,347929, 348511, 349065, 352895, 353846, 354515, 354613, 355399, 356600, 356848, 358618, 359881, 360141, 361945, 362315, 362319, 364313, 364905, 365467, 366082, 367713, 368259, 369136, 369227, 369587, 370103, 371638, 372801, 373282, 373940, 374272, 376884, 378034, 378137, 379377, 380843, 381536, 381658, 384090, 384204, 387934, 388405, 389468, 389788, 390111, 391314, 392612, 393150, 393267, 393686, 393769, 395321, 396311, 398127, 398206, 402049, 402449, 402525, 403119, 405354, 405399, 405670, 407726, 407963, 408684, 410709, 413420, 414514, 417938, 418103, 418475, 419788, 420466, 421956, 423095, 424818, 425284, 425789, 426911, 427657, 428255, 428320, 428837, 430123, 430590, 432746, 433055, 433398, 433581, 435020, 435553,436486, 437574, 438506, 441893, 443576, 443590, 443832, 443907, 444102, 444123, 445281, 445874, 447222, 448173, 448717, 448887, 450319, 450531, 451247, 452811, 452955, 453558, 453777, 454218, 455511, 455844, 456043, 459044, 461097, 461437, 461454, 462768, 463430, 464561, 464947, 466864, 469723, 469870, 470208, 471233, 473086, 474422, 475899, 476828, 477937, 479481, 479763, 482463, 484142, 485413, 485613, 486678, 487305, 487413, 487508, 488004, 488075, 488529, 492228, 492734, 492870, 495603, 495644, 497458, 499398, 499420, 499812, 501700, 502800, 504411, 504596, 504897, 505899, 506098, 506853, 507806, 509448, 512263, 513041, 515257, 516090, 516887, 517287, 521862, 522345, 524178, 524599, 524767, 525078, 525436, 526086,527544, 527567, 529203, 529384, 529427, 529945, 530508, 531770, 532826, 534538, 536564, 536568, 537053, 537164, 537198, 539187, 539470, 539627, 540509, 541412, 542761, 543537, 547892, 548043, 548699, 548968, 551014, 553255, 557607, 561935, 565756, 565856, 567677, 569202, 569487, 572064, 572425, 572997, 574197, 574451, 576150, 576204, 576465, 576810, 576851, 580382, 580826, 581104, 581421, 582138, 582665, 586380, 586759, 589020, 589174, 589257, 590585, 590587, 591112, 593598, 596144, 597034, 597385, 597646, 598219, 600171, 602016, 603264, 603449, 604600, 605177, 607217, 609658, 609853, 610388, 611575, 612661, 612706, 616371, 617201, 617245, 618066, 619775, 620742, 624304, 626801, 628077, 628555, 629730, 630479, 631546,631923, 633136, 633585, 633841, 634086, 634220, 636474, 639976, 640073, 640372, 640646, 641813, 641863, 642513, 643795, 644760, 644835, 646304, 646880, 647140, 648333, 649202, 649794, 650740, 650978, 651363, 654120, 656100, 658728, 658910, 664816, 665060, 665565, 666401, 666622, 667066, 667243, 668266, 670929, 671073, 672877, 673276, 673368, 674140, 675608, 676158, 676762, 677397, 682106, 684873, 686102, 686871, 688828, 689423, 689585, 690021, 690508, 690943, 695422, 696248, 696918, 697401, 697471, 697801, 699357, 699471, 699709, 700957, 702393, 703501, 704672, 706362, 708068, 712958, 714475, 715990, 716256, 717020, 717036, 717644, 718063, 719556, 721115, 721429, 723023, 723142, 723694, 724608, 728100, 730486, 730841,731030, 731113, 731261, 731519, 732290, 737205, 737255, 738442, 739607, 740231, 740281, 741685, 742061, 743406, 743484, 746092, 746668, 747477, 748246, 748713, 748911, 749417, 749832, 750733, 750918, 754429, 755308, 756620, 757503, 757970, 758099, 758197, 758450, 760796, 762215, 762347, 763710, 764215, 764521, 764574, 767583, 767797, 769152, 770501, 770848, 771566, 772018, 772326, 772604, 773582, 774004, 774405, 775505, 776822, 778208, 779090, 780107, 780940, 781255, 784496, 785076, 791265, 792178, 792826, 792867, 792946, 795230, 797147, 798535, 801002, 801286, 801973, 803363, 803692, 803738, 804300, 805468, 805858, 806221, 806761, 810108, 810462, 811520, 811864, 812285, 813733, 814558, 815225, 815916, 816345, 817618,818801, 819623, 820125, 820661, 823440, 825227, 826316, 826396, 826743, 826763, 827110, 829372, 829502, 829702, 829772, 831353, 835705, 836278, 836646, 837006, 837088, 837264, 838238, 838839, 839321, 841468, 844062, 845493, 845784, 846133, 846297, 846687, 848110, 848779, 849548, 850204, 851379, 853762, 853832, 855714, 856422, 858079, 862159, 863142, 864111, 866190, 866224, 867299, 867945, 868775, 869591, 869618, 871149, 872712, 872765, 873062, 873075, 875613, 876792, 876973, 877031, 878275, 878755, 879054, 879138, 882167, 882334, 882558, 883309, 884239, 884258, 884662, 885123, 886436, 887367, 888077, 888221, 888398, 888736, 888848, 889323, 890730, 891763, 892832, 894833, 896584, 897895, 898245, 899156, 901078, 901723,902449, 902509, 902933, 903502, 904457, 904668, 905805, 905883, 906472, 907565, 908693, 908980, 911023, 915301, 916708, 919324, 920306, 921521, 921873, 922672, 923498, 924447, 925247, 928422, 929082, 929103, 930263, 930686, 931175, 932073, 932160, 932691, 933092, 934983, 935787, 937158, 937384, 937980, 938564, 940569, 940975, 941711, 941755, 942025, 942343, 942855, 942856, 945399, 945819, 946287, 946456, 947211, 948576, 949851, 950906, 952454, 953783, 955121, 961126, 961223, 961935, 966076, 966190, 967199, 968125, 968286, 968866, 969295, 969487, 970386, 970541, 971665, 972314, 972889, 973896, 974013, 975422, 978006, 978444, 979556, 979749, 981014, 982749, 983569, 986925, 987093, 987595, 989842, 990708, 990750, 990911,991195, 992405, 993881, 993924, 994257, 995032, 995223, 995894]


/*
1. 终止条件 若数组只有 1 个了，那么返回第一个
2. 取基数，拿第一个
3. 从第二个开始遍历，并比较，小的放左数组，大的放右数组，递归
*/

var quickSort = originArr => {
  if(originArr.length <= 0) return 
  var baseNum = originArr[0]
  var leftArr = []
  var rightArr = []
  originArr.forEach( (item,index) => {
    if(index !== 0) {
          item > baseNum ? rightArr.push(item) : leftArr.push(item)
    }

  })

  var left = leftArr.length>=1 ? quickSort(leftArr):[]
  var right = rightArr.length>=1 ?quickSort(rightArr):[]

  return [...left, baseNum, ...right]
}
console.time()
// var s = quickSort(origin)
var s = quickSort(c)
console.timeEnd()
// console.log(s)

console.time()
var b = _quickSort(c,0,c.length-1)
console.timeEnd()
// console.log(b)

function _quickSort(arr, left, right) {
  if (left < right) {
    var pivot = arr[right];
    var i = left,
      j = right - 1;

    while (true) {
      
      while (arr[i] < pivot && i < right) i++;
     
      while (arr[j] >= pivot && j > i) j--;
       
      if (i >= j) {
        break;
      }
      swap(arr, i, j);
    }

    var mid = j;

    if(i !== right){ 
      swap(arr, j, right);
    } else{
      mid = right
    }

    _quickSort(arr, left, mid - 1);
    _quickSort(arr, mid + 1, right);
  }
}

[mcfog]

因为你写的是空间复杂度 n log n 的思路像快排的某种别的排序，在内存分配上消耗了更多性能

[dxcqcv]

@mcfog 也就是说我写的根本不是快排？

[mmmfj]

要在原数组内交换位置才是正经的

[quzard]

快排要在原数组内交换位置才是快

[Biwood]

你的写法时间复杂度是 O(n^2)，注意 forEach 没有终止条件，而且每次递归都开了新的堆栈，空间消耗也更高，确实不能算快速排序

[wanguorui123]

有一种快排是伪快排，需分配内存，降低了效率

[Leviathann]

var + lambda
这是 es 几

[aneostart173]

你每次都把数据复制到新的 arr 里了，然后还是递归。复制数据的代价是 O(n)

[zhy0216]

我怀疑楼上说不是的会不会算法复杂度分析

https://en.wikipedia.org/wiki/Quicksort 的 Average-case analysis

[dxcqcv]

@zhy0216 嗯，我主要的疑惑点是，新开 2 个数组而不是操作元数组会慢那么多呀

[otakustay]

你这个新开数组等于做数组复制，是要 O(n)遍历的

[zhy0216]

@dxcqcv 你算一下空间复杂度
要申请新的空间啊 肯定要慢一些
但第一种实现明显漂亮些