手写数据结构 排序算法 篇（上）https://developer.aliyun.com/article/1392187
快速排序
// 快速排序入口 function quickSort(arr, left = 0, right = arr.length - 1) { // 定义递归边界，若数组只有一个元素，则没有排序必要 if (arr.length > 1) { // lineIndex表示下一次划分左右子数组的索引位 const lineIndex = partition(arr, left, right) // 如果左边子数组的长度不小于1，则递归快排这个子数组 if (left < lineIndex - 1) { // 左子数组以 lineIndex-1 为右边界 quickSort(arr, left, lineIndex - 1) } // 如果右边子数组的长度不小于1，则递归快排这个子数组 if (lineIndex < right) { // 右子数组以 lineIndex 为左边界 quickSort(arr, lineIndex, right) } } return arr } // 以基准值为轴心，划分左右子数组的过程 function partition(arr, left, right) { // 基准值默认取中间位置的元素 let pivotValue = arr[Math.floor(left + (right - left) / 2)] // 初始化左右指针 let i = left let j = right // 当左右指针不越界时，循环执行以下逻辑 while (i <= j) { // 左指针所指元素若小于基准值，则右移左指针 while (arr[i] < pivotValue) { i++ } // 右指针所指元素大于基准值，则左移右指针 while (arr[j] > pivotValue) { j-- } // 若i<=j，则意味着基准值左边存在较大元素或右边存在较小元素，交换两个元素确保左右两侧有序 if (i <= j) { swap(arr, i, j) i++ j-- } } // 返回左指针索引作为下一次划分左右子数组的依据 return i } // 快速排序中使用 swap 的地方比较多，我们提取成一个独立的函数 function swap(arr, i, j) { [arr[i], arr[j]] = [arr[j], arr[i]] } let arr = [3, 4, 2, 8, 5, 5, 2, 0, 6, 6, 3] console.log(quickSort(arr));
时间复杂度
快速排序的时间复杂度分析 快速排序的时间复杂度的好坏，是由基准值来决定的。 最好时间复杂度：它对应的是这种情况——我们每次选择基准值，都刚好是当前子数组的中间数。这时，可以确保每一次分割都能将数组分为两半，进而只需要递归 log(n) 次。这时，快速排序的时间复杂度分析思路和归并排序相似，最后结果也是 O(nlog(n))。 最坏时间复杂度：每次划分取到的都是当前数组中的最大值/最小值。大家可以尝试把这种情况代入快排的思路中，你会发现此时快排已经退化为了冒泡排序，对应的时间复杂度是 O(n^2)。 平均时间复杂度： O(nlog(n))
计数排序
function countingSort(array) { // 如果待排序的数组为空或只有一个元素，则不需要运行排序算法。 if (array.length < 2) { return array; } // 数组中的最大值 const maxValue = findMaxValue(array); // 对于计数排序算法，我们需要创建计数数组，从索引 0 开始直到最大值索引 value + 1 const counts = new Array(maxValue + 1); array.forEach(element => { // 如果 counts 数组中用来计数某个元素的位置一开始没有用 0 初始化的话，我们将其赋值为 0 if (!counts[element]) { counts[element] = 0; } // 迭代数组中的每个位置并在 counts 数组中增加元素计数值 counts[element]++; }); // 从小到大挨个取出数组元素 let sortedIndex = 0; counts.forEach((count, i) => { while (count > 0) { array[sortedIndex++] = i; count--; } }); return array; } // 遍历查找数组最大元素 function findMaxValue(array) { let max = array[0]; for (let i = 1; i < array.length; i++) { if (array[i] > max) { max = array[i]; } } return max; } let arr = [3, 4, 2, 8, 5, 5, 2, 0, 6, 6, 3] console.log(countingSort(arr));
时间复杂度
它是用来排序整数的优秀算法（它是一个整数排序算法），时间复杂度为 O(n+k)，其中 k 是 临时计数数组的大小；但是，它确实需要更多的内存来存放临时数组。
桶排序
function bucketSort(array, bucketSize = 5) { // 指定需要多少桶来排序各个元素 if (array.length < 2) { return array; } const buckets = createBuckets(array, bucketSize); // 创建桶并将元素分布到不同的桶中 return sortBuckets(buckets); // 对每个桶执行插入排序算法和将所有桶合并为排序后的结果数组 } function createBuckets(array, bucketSize) { let minValue = array[0]; let maxValue = array[0]; for (let i = 1; i < array.length; i++) { // 迭代原数组并找到最大值和最小值 if (array[i] < minValue) { minValue = array[i]; } else if (array[i] > maxValue) { maxValue = array[i]; } } const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1; // 计算每个桶中需要分布的元素个数 const buckets = []; for (let i = 0; i < bucketCount; i++) { // 初始化每个桶 buckets[i] = []; } for (let i = 0; i < array.length; i++) { // 迭代数组中的每个元素 const bucketIndex = Math.floor((array[i] - minValue) / bucketSize); // 计算要将元素放到哪个桶中 对比bucketCount buckets[bucketIndex].push(array[i]); } return buckets; } function sortBuckets(buckets) { const sortedArray = []; // 创建一个用作结果数组的新数组 for (let i = 0; i < buckets.length; i++) { // {10} if (buckets[i] != null) { insertSort(buckets[i]); // 迭代每个可迭代的桶并应用插入排序 sortedArray.push(...buckets[i]); // 将排好序的桶中的所有元素加入结果数组中 } } return sortedArray; } function insertSort(arr) { // 缓存数组长度 const len = arr.length // temp 用来保存当前需要插入的元素 let temp // i用于标识每次被插入的元素的索引 for (let i = 1; i < len; i++) { // j用于帮助 temp 寻找自己应该有的定位 let j = i temp = arr[i] // 判断 j 前面一个元素是否比 temp 大 while (j > 0 && arr[j - 1] > temp) { // 如果是，则将 j 前面的一个元素后移一位，为 temp 让出位置 arr[j] = arr[j - 1] j-- } // 循环让位，最后得到的 j 就是 temp 的正确索引 arr[j] = temp } return arr } let arr = [3, 4, 2, 8, 5, 5, 2, 0, 6, 6, 3] console.log(bucketSort(arr));
时间复杂度
1. 时间复杂度：O(N + C)，C=N*(logN-logM) 对于待排序序列大小为 N，共分为 M 个桶，主要步骤有： N 次循环，将每个元素装入对应的桶中 M 次循环，对每个桶中的数据进行排序（平均每个桶有 N/M 个元素） 一般使用较为快速的排序算法，时间复杂度为 O(NlogN)，实际的桶排序过程是以链表形式插入的。 整个桶排序的时间复杂度为： O(N)+O(M∗(N/M∗log(N/M))) = O(N)+O(N∗(log(N/M)) = O(N)+O(C）= O(N∗(log(N/M)+1)) 当 N = M 时，复杂度为 O(N) 2. 额外空间复杂度：O(N + M) 3、稳定性分析 桶排序的稳定性取决于桶内排序使用的算法。
基数排序
function radixSort(array, radixBase = 10) { if (array.length < 2) { return array; } const minValue = findMinValue(array); const maxValue = findMaxValue(array); let significantDigit = 1; // 基数排序也用来排序整数，我们就从最后一位开始排序所有的数 while ((maxValue - minValue) / significantDigit >= 1) { // {2} array = countingSortForRadix(array, radixBase, significantDigit, minValue); // {3} significantDigit *= radixBase; // {4} } return array; } function countingSortForRadix(array, radixBase, significantDigit, minValue) { let bucketsIndex; const buckets = []; const aux = []; for (let i = 0; i < radixBase; i++) { // 基于基数初始化桶 buckets[i] = 0; } // 基于数组中（行{6}）数的有效位（行{7}）进行计数排序（行{8}） for (let i = 0; i < array.length; i++) { // {6} bucketsIndex = Math.floor(((array[i] - minValue) / significantDigit) % radixBase); // {7} buckets[bucketsIndex]++; // {8} } for (let i = 1; i < radixBase; i++) { // 计算累积结果来得到正确的计数值 buckets[i] += buckets[i - 1]; } for (let i = array.length - 1; i >= 0; i--) { // 使用一个临时数组（aux）来帮助我们。对原始数组中的每个值 // 对原始数组中的每个值（行{10}），我们会再次获取它的有效位（行{11}）并将它的值移动到 // aux 数组中（从 buckets 数组中减去它的计数值——行{12}）。最后一步是可选的（行{13}）， // 我们将 aux 数组中的每个值转移到原始数组中 bucketsIndex = Math.floor(((array[i] - minValue) / significantDigit) % radixBase); // {11} aux[--buckets[bucketsIndex]] = array[i]; // {12} } for (let i = 0; i < array.length; i++) { // {13} array[i] = aux[i]; } return array; } function findMaxValue(array) { let max = array[0]; for (let i = 1; i < array.length; i++) { if (array[i] > max) { max = array[i]; } } return max; } function findMinValue(array) { let min = array[0]; for (let i = 1; i < array.length; i++) { if (array[i] < min) { min = array[i]; } } return min; } let arr = [3, 4, 2, 8, 5, 5, 2, 0, 6, 6, 3] console.log(radixSort(arr));
