leetcode练习：912. 排序数组

    1. const arr = Array(11).fill().map(() => ~~(Math.random() * 100));
    3. console.log('bubbleSort(arr): ', ...bubbleSort(arr.slice()));
    4. console.log('selectionSort(arr): ', ...selectionSort(arr.slice()));
    5. console.log('insertionSort(arr): ', ...insertionSort(arr.slice()));
    6. console.log('shellSort(arr): ', ...shellSort(arr.slice()));
    7. console.log('countingSort(arr): ', ...countingSort(arr.slice()));
    8. console.log('mergeSort1(arr): ', ...mergeSort1(arr.slice()));
    9. console.log('quickSort1(arr): ', ...quickSort1(arr.slice()));
    10. console.log('heapSort(arr): ', ...heapSort(arr.slice()));
    11. console.log('bucketSort(arr): ', ...bucketSort(arr.slice()));
    12. console.log('radixSort(arr): ', ...radixSort(arr.slice()));
    14. function bubbleSort(arr) {
    15.     const len = arr.length;
    16.     for (let i = 0; i < len; i++) {
    17.         for (let j = 0; j < len - i - 1; j++) {
    18.             if (arr[j] > arr[j + 1]) {
    19.                 [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
    20.             }
    21.         }
    22.     }
    23.     return arr;
    24. }
    26. function selectionSort(arr) {
    27.     const len = arr.length;
    28.     for (let i = 0; i < len; i++) {
    29.         let temp = i;
    30.         for (let j = i + 1; j < len; j++) {
    31.             if (arr[temp] > arr[j]) {
    32.                 temp = j;
    33.             }
    34.         }
    35.         [arr[temp], arr[i]] = [arr[i], arr[temp]];
    36.     }
    37.     return arr;
    38. }
    40. function insertionSort(arr) {
    41.     const len = arr.length;
    42.     for (let i = 1; i < len; i++) {
    43.         const current = arr[i];
    44.         let preIndex = i - 1;
    45.         while (preIndex >= 0 && arr[preIndex] > current) {
    46.             arr[preIndex + 1] = arr[preIndex];
    47.             preIndex--;
    48.         }
    49.         arr[preIndex + 1] = current;
    50.     }
    51.     return arr;
    52. }
    54. function shellSort(arr) {
    55.     const len = arr.length;
    56.     let increment = ~~(len / 2);
    57.     while (increment > 0) {
    58.         for (let i = increment; i < len; i++) {
    59.             const current = arr[i];
    60.             let preIndex = i - increment;
    61.             while (preIndex >= 0 && arr[preIndex] > current) {
    62.                 arr[preIndex + increment] = arr[preIndex];
    63.                 preIndex -= increment;
    64.             }
    65.             arr[preIndex + increment] = current;
    66.         }
    67.         increment = ~~(increment / 2);
    68.     }
    69.     return arr;
    70. }
    72. function countingSort(arr) {
    73.     const maxValue = Math.max(...arr);
    74.     const countArr = Array(maxValue + 1).fill(0);
    75.     arr.forEach(element => {
    76.         countArr[element]++;
    77.     });
    78.     let sortedIndex = 0;
    79.     countArr.forEach((count, index) => {
    80.         while (count--) {
    81.             arr[sortedIndex++] = index;
    82.         }
    83.     });
    84.     return arr;
    85. }
    87. function mergeSort1(arr) {
    88.     if (arr.length < 2) return arr;
    89.     const mid = ~~(arr.length / 2);
    90.     return merge(mergeSort1(arr.slice(0, mid)), mergeSort1(arr.slice(mid)))
    91. }
    93. function merge(left, right) {
    94.     let i = 0, j = 0;
    95.     const newArr = [];
    96.     while (i < left.length && j < right.length) {
    97.         if (left[i] <= right[j]) {
    98.             newArr.push(left[i++]);
    99.         } else {
    100.             newArr.push(right[j++]);
    101.         }
    102.     }
    103.     while (i < left.length) {
    104.         newArr.push(left[i++]);
    105.     }
    106.     while (j < right.length) {
    107.         newArr.push(right[j++]);
    108.     }
    109.     return newArr;
    110. };
    112. function quickSort1(arr, left = 0, right = arr.length - 1) {
    113.     if (left < right) {
    114.         const partitionIndex = partition1(arr, left, right);
    115.         quickSort1(arr, left, partitionIndex - 1);
    116.         quickSort1(arr, partitionIndex + 1, right);
    117.     }
    118.     return arr;
    119. }
    121. function partition1(arr, left, right) {
    122.     const current = arr[left];
    123.     while (left < right) {
    124.         while (left < right && arr[right] >= current) {
    125.             right--;
    126.         }
    127.         arr[left] = arr[right];
    128.         while (left < right && arr[left] < current) {
    129.             left++;
    130.         }
    131.         arr[right] = arr[left];
    132.     }
    133.     arr[left] = current;
    134.     return left;
    135. }
    137. function quickSort2(arr, left = 0, right = arr.length - 1) {
    138.     if (left < right) {
    139.         const partitionIndex = quickSort2(arr, left, right);
    140.         quickSort2(arr, left, partitionIndex - 1);
    141.         quickSort2(arr, partitionIndex + 1, right);
    142.     }
    143.     return arr;
    144. }
    146. function partition2(arr, left, right) {
    147.     const pivot = arr[left];
    148.     let index = left + 1;
    149.     for(let i = index; i <= right; i++) {
    150.         if(arr[i] < pivot) {
    151.             [ arr[i], arr[index] ] = [ arr[index], arr[i] ];
    152.             index++;
    153.         }
    154.     }
    155.     [ arr[left], arr[index - 1] ] = [ arr[index - 1], arr[left] ];
    156.     return index - 1;
    157. }
    159. function heapSort(arr) {
    160.     const len = arr.length;
    161.     for (let i = Math.floor(len / 2); i >= 0; i--) {
    162.         sift(arr, i, len - 1);
    163.     }
    164.     for (let i = len - 1; i > 0; i--) {
    165.         [arr[0], arr[i]] = [arr[i], arr[0]];
    166.         sift(arr, 0, i - 1);
    167.     }
    168.     return arr;
    169. }
    171. function sift(arr, low, high) {
    172.     const current = arr[low];
    173.     let i = low, j = 2 * i + 1;
    174.     while (j <= high) {
    175.         if (j < high && arr[j] < arr[j + 1]) {
    176.             j = j + 1;
    177.         }
    178.         if (current < arr[j]) {
    179.             arr[i] = arr[j];
    180.             i = j;
    181.             j = 2 * i;
    182.         } else break;
    183.     }
    184.     arr[i] = current;
    185. }
    187. function bucketSort(arr) {
    188.     const len = arr.length;
    189.     let maxValue = arr[0], minValue = arr[0];
    190.     for (const num of arr) {
    191.         if (num > maxValue) maxValue = num;
    192.         if (num < minValue) minValue = num;
    193.     }
    194.     const bucketSize = 5;
    195.     const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
    196.     const bucket = Array(bucketCount).fill().map(() => []);
    197.     for (let i = 0; i < len; i++) {
    198.         bucket[Math.floor((arr[i] - minValue) / bucketCount)].push(arr[i]);
    199.     }
    200.     const newArr = [];
    201.     for (let i = 0; i < bucketCount; i++) {
    202.         if (bucket[i].length) {
    203.             newArr.push(...insertionSort(bucket[i]));
    204.         }
    205.     }
    206.     return newArr;
    207. }
    209. function radixSort(arr, radixBase = 10) {
    210.     let maxValue = arr[0], minValue = arr[0];
    211.     for (const num of arr) {
    212.         if (num > maxValue) maxValue = num;
    213.         if (num < minValue) minValue = num;
    214.     }
    215.     let currentDigit = 1;
    216.     while ((maxValue - minValue) / currentDigit >= 1) {
    217.         arr = countingSortForRadix(arr, radixBase, currentDigit, minValue);
    218.         currentDigit *= radixBase;
    219.     }
    220.     return arr;
    221. }
    223. function countingSortForRadix(arr, radixBase, currentDigit, minValue) {
    224.     const len = arr.length;
    225.     for (const num of arr) {
    226.         const bucketIndex = Math.floor((num - minValue) / currentDigit) % radixBase;
    227.         bucket[bucketIndex]++;
    228.     }
    229.     for (let i = 1; i < len; i++) {
    230.         bucket[i] += bucket[i - 1];
    231.     }
    232.     const res = [];
    233.     for (let i = len - 1; i >= 0; i--) {
    234.         const bucketIndex = Math.floor((arr[i] - minValue) / currentDigit) % radixBase;
    235.         res[--bucket[bucketIndex]] = arr[i];
    236.     }
    237.     return res;
    238. }