1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108
| // 归并排序 class MergeSort extends SortExample { constructor(a, b = true) { super(a); this.ascendingOrder = b; this.aux = []; }
merge(lo, mid, fi) { const { arr, aux } = this; for (let i = lo; i <= fi; i++) { aux[i] = arr[i]; } let i = lo; let j = mid + 1; // let index = lo; // while (index <= fi) { // if (i > mid) { // arr[index++] = aux[j++]; // } else if (j > fi) { // arr[index++] = aux[i++]; // } else { // if(this.less(i, j)) { // arr[index++] = aux[i++]; // } else { // arr[index++] = aux[j++];} // } // } for (let index = lo; index <= fi; index++) { if (i > mid) { arr[index] = aux[j++]; } else if (j > fi) { arr[index] = aux[i++]; } else if (!(this.ascendingOrder^(aux[i] < aux[j]))) { arr[index] = aux[i++]; } else { arr[index] = aux[j++]; } } } // 自顶而下的 sort(lo = 0, fi = this.len - 1) { console.log("lo: " + lo + "fi : " + fi) if (lo >= fi) { return; } const mid = Math.floor((lo + fi) / 2); this.sort(lo, mid); this.sort(mid + 1, fi); this.merge(lo, mid, fi); } // 自下而上的 Upsort() { let fi = this.len - 1; for (let sz = 1; sz <= fi; sz = sz + sz) { for (let lo = 0; lo <= fi - sz + 1; lo = lo + 2 * sz) { this.merge(lo, lo + sz - 1, Math.min(lo + 2 * sz - 1, fi)); } } } }
// 最基础的快速排序 class QuickSort extends SortExample { constructor(a, b = true) { super(a); this.ascendingOrder = b; this.sort(0, this.len - 1); }
sort(lo, fi) { if (lo >= fi) { return; } const p = this.partition(lo, fi); this.sort(lo, p - 1); this.sort(p+1, fi); }
partition(lo, fi) { // const { arr, len } = this; // const value = arr[lo]; let i = 0; let j = fi + 1; while (true) { while(!this.less(lo, ++i)) { if (i == fi) { break; } } while(!this.less(--j, lo)) { if (j == lo) { break; } } if (i>=j) { break; } this.exch(i, j); } this.exch(j, lo); return j; } }
const exam = new MergeSort([2,1,3,5,11,4,13,22,21,7,10,18], false); exam.sort(); exam.isSorted() ? exam.show() : console.log("wrong result");
const quickExam = new QuickSort([2,1,3,5,11,4,13,22,21,7,10,18]); quickExam.isSorted() ? exam.show() : console.log("wrong result");
|