{{ message }}

Instantly share code, notes, and snippets.

# ideawu/quicksort

Last active Oct 19, 2019



### ideawu commented May 11, 2018

 一次典型的结果对比： ``````run test: wintercn_qsort time: 256 ms compare: 30123003 swap: 30123003 nlogn: 14208385 run test: ruanyifeng_qsort time: 748 ms compare: 22853877 swap: 25524713 nlogn: 14208385 run test: qsort_hoare time: 208 ms compare: 33571306 swap: 4960909 nlogn: 14208385 run test: qsort_lomuto time: 208 ms compare: 33104842 swap: 10504357 nlogn: 14208385 ``````

### ZTGeng commented May 11, 2018 • edited

 hoare改进版。compare和swap数量更低。 ``````function qsort_recr(arr, start, end){ var midValue = arr[start]; var h = start + 1; var t = end; while (h <= t) { while (h <= t && compare(arr[h], midValue) <= 0) { h++; } if (h > t) { break; } while (t >= h && compare(midValue, arr[t]) <= 0) { t--; } if (t < h) { break; } swap(arr, h, t); h++; t--; } swap(arr, start, t); if (t - 1 > start) { qsort_recr(arr, start, t - 1); } if (h < end) { qsort_recr(arr, h, end); } } ``````

### wintercn commented May 11, 2018 • edited

 讲真，首先我认为在时间复杂度不变的前提下，这种优化非常无聊 其次，你非要比这个憋说我欺负你： ```function wintercn_qsort(arr, start, end){ //start = start | 0; //end = end | 0 ; var midValue = arr[start]; var p1 = start + 1, p2 = end; while(p1 < p2) { while(compare(arr[p1], midValue) >= 0 && p1 < p2) { swap(arr, p1, p2--); } p1 ++; } var mid = arr[p2] <= midValue ? p2 : p2 -1; swap(arr, start, mid); if(start < mid - 1) wintercn_qsort(arr, start, mid - 1); if(mid < end) wintercn_qsort(arr, mid + 1, end); }``` 结果： ``````time: 223 ms compare: 22042901 swap: 13008246 nlogn: 14208385 run test: ruanyifeng_qsort time: 962 ms compare: 22773479 swap: 25452695 nlogn: 14208385 run test: qsort_hoare time: 243 ms compare: 32123353 swap: 4989996 nlogn: 14208385 run test: qsort_lomuto time: 251 ms compare: 33021494 swap: 10394010 nlogn: 14208385 ``````

### wintercn commented May 11, 2018 • edited

 看到我注释掉那两行没？ 这种语言特定的优化我都懒得用。

### ideawu commented May 11, 2018

 @ZTGeng 赞！目前是你的版本最快。compare明显减少，swap减少不明显。

### tidyoux commented May 11, 2018

 贴个基础版： ```function qsort_base(arr, start, end) { if (start >= end) { return } var m = start; for (var i = start + 1; i <= end; i++) { if (compare(arr[i], arr[start]) < 0) { m++; if (m != i) { swap(arr, m, i); } } } swap(arr, start, m); qsort_base(arr, start, m - 1); qsort_base(arr, m + 1, end); }```

### ZTGeng commented May 11, 2018

 再来个非递归版，和递归版其实是一样的，compare和swap数量应该与递归版完全相同（因为计算过程完全一致），耗时也许能少一丢丢？ ``````function qsort_loop(arr, start, end) { var _start = start; var _end = end; var stack = []; while (1) { var midValue = arr[_start]; var h = _start + 1; var t = _end; while (h <= t) { while (h <= t && compare(arr[h], midValue) <= 0) { h++; } if (h > t) { break; } while (t >= h && compare(midValue, arr[t]) <= 0) { t--; } if (t < h) { break; } swap(arr, h, t); h++; t--; } swap(arr, _start, t); if (h < _end) { stack.push(h); stack.push(_end); } if (t - 1 > _start) { _end = t - 1; } else if (stack.length > 0) { _end = stack.pop(); _start = stack.pop(); } else { break; } } } ``````

### shiye515 commented May 12, 2018 • edited

 耗时排名稳定在第一或者第二的位置，weibo：光挣钱不说话 ```function shiye515Sort(arr, start, end) { let divider = end; let dividerValue = arr[divider] let blank = divider let pickStart = start let pickEnd = end - 1 let isAsc = true while (pickStart <= pickEnd) { if (isAsc) { if (compare(arr[pickStart], dividerValue) > 0) { swap(arr, blank, pickStart); blank = pickStart isAsc = false } pickStart++ } else { if (compare(arr[pickEnd], dividerValue) < 0) { swap(arr, blank, pickEnd); blank = pickEnd isAsc = true } pickEnd-- } } let mid = isAsc ? (pickEnd + 1) : (pickStart - 1) if (start < mid - 1) { shiye515Sort(arr, start, mid - 1) } if (mid + 1 < end) { shiye515Sort(arr, mid + 1, end) } }```

### yyssjj33 commented May 14, 2018

 为啥没人提到要先shuffle下？quicksort最坏复杂度不是O^2吗？