123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132 |
- function SortTemplate(comparator) {
- function swap(ary, x, y) {
- var temp = ary[x];
- ary[x] = ary[y];
- ary[y] = temp;
- }
- function randomIntInRange(low, high) {
- return Math.round(low + (Math.random() * (high - low)));
- }
- function doQuickSort(ary, comparator, p, r) {
-
-
-
- if (p < r) {
-
-
-
-
-
-
-
-
-
-
- var pivotIndex = randomIntInRange(p, r);
- var i = p - 1;
- swap(ary, pivotIndex, r);
- var pivot = ary[r];
-
-
-
-
-
-
- for (var j = p; j < r; j++) {
- if (comparator(ary[j], pivot, false) <= 0) {
- i += 1;
- swap(ary, i, j);
- }
- }
- swap(ary, i + 1, j);
- var q = i + 1;
-
- doQuickSort(ary, comparator, p, q - 1);
- doQuickSort(ary, comparator, q + 1, r);
- }
- }
- return doQuickSort;
- }
- function cloneSort(comparator) {
- let template = SortTemplate.toString();
- let templateFn = new Function(`return ${template}`)();
- return templateFn(comparator);
- }
- let sortCache = new WeakMap();
- exports.quickSort = function (ary, comparator, start = 0) {
- let doQuickSort = sortCache.get(comparator);
- if (doQuickSort === void 0) {
- doQuickSort = cloneSort(comparator);
- sortCache.set(comparator, doQuickSort);
- }
- doQuickSort(ary, comparator, start, ary.length - 1);
- };
|