本篇文章给大家带来了关于javascript的相关知识,其中主要介绍了关于javascript实现十大排序算法的相关问题,包括了冒泡排序、选择排序、插入排序等等问题,下面一起来看一下,希望对大家有帮助。
【相关推荐:javascript视频教程、web前端】
当前解法为升序
冒泡排序的特点,是一个个数进行处理。第i个数,需要与后续的len-i-1
个数进行逐个比较。
为什么是 `len-i-1`个数?
因为数组末尾的i个数,已经是排好序的,确认位置不变的了。
为什么确认位置不变,因为它们固定下来之前,已经和前面的数字都一一比较过了。
function bubbleSort(arr){ const len = arr.length; for(let i = 0; i arr[j+1]){ const tmp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = tmp; } } } return arr; }
快速排序,使用的是分治法的思想。
通过选定一个数字作为比较值,将要排序其他数字,分为 >比较值 和 ,两个部分。并不断重复这个步骤,直到只剩要排序的数字只有本身,则排序完成。
function quickSort(arr){ sort(arr, 0, arr.length - 1); return arr; function sort(arr, low, high){ if(low >= high){ return; } let i = low; let j = high; const x = arr[i]; // 取出比较值x,当前位置i空出,等待填入 while(i = x && i <h2>希尔排序</h2><h3>概要</h3><p>希尔排序是一种<strong>插入排序</strong>的算法,它是对简单的插入排序进行改进后,更高效的版本。由希尔(Donald Shell)于1959年提出。<br> 特点是利用<strong>增量</strong>,将数组分成一组组子序列,然后对子序列进行插入排序。<br> 由于增量是从大到小,逐次递减,所以也称为<strong>缩小增量排序</strong>。</p><h3>效果图</h3><p class="img-center"><img alt="" src="https://img.php.cn/upload/article/000/000/067/61e90c90ab27d338d2e1499c46b86599-2.png"></p><h3>解法</h3><blockquote><p><strong>注意点</strong><br> 插入排序时,并不是一个分组内的数字一次性用插入排序完成,而是每个分组交叉进行。</p></blockquote><p>执行插入时,使用交换法</p><pre class="brush:php;toolbar:false">function shellSort(arr){ // 分组规则 gap/2 递减 for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)){ for(let i = gap; i = 0 && arr[j] <p>执行插入时,使用移动法</p><pre class="brush:php;toolbar:false">function shellSort(arr){ for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)){ for(let i = gap; i = 0 && x <h2>选择排序</h2><h3>排序的效果图</h3><p class="img-center"><img alt="" src="https://img.php.cn/upload/article/000/000/067/d4083e3d22760cb55b02e36857587876-3.gif"></p><h3>解法</h3><blockquote><p>当前解法为升序</p></blockquote><pre class="brush:php;toolbar:false">function selectionSort(arr){ const len = arr.length; for(let i = 0; i <h2>归并排序</h2><h3>概要</h3><p>归并排序,利用<strong>分治</strong>思想,将大的数组,分解为小数组,直至单个元素。然后,使用<strong>选择排序</strong>的方式,对分拆的小数组,进行回溯,并有序合并,直至合并为一个大的数组。</p><h3>效果图</h3><p class="img-center"><img alt="" src="https://img.php.cn/upload/article/000/000/067/d6a245e7bc11d37051408c4c3d28f0eb-4.png"></p><h3>小数组合并的过程</h3><p class="img-center"><img alt="" src="https://img.php.cn/upload/article/000/000/067/75fbf4b77f62f43e96a9ee51411c0780-5.png"></p><p class="img-center"><img alt="" src="https://img.php.cn/upload/article/000/000/067/65383097586e2a0fde0731cee0f86817-6.png"></p><h3>解法</h3><pre class="brush:php;toolbar:false">function mergeSort(arr){ return sort(arr, 0, arr.length - 1); // 注意右区间是arr.length - 1 // sort方法,进行递归 function sort(arr, left, right){ // 当left !== right时,证明还没分拆到最小元素 if(left = 0 ? [arr[left]] : []; } // 合并两个有序数组 function merge(leftArr, rightArr){ let left = 0; let right = 0; const tmp = []; // 使用双指针,对两个数组进行扫描 while(left <h2>插入排序</h2><h3>排序的效果图</h3><p class="img-center"><img alt="" src="https://img.php.cn/upload/article/000/000/067/65383097586e2a0fde0731cee0f86817-7.gif"></p><h3>解法</h3><blockquote><p>当前解法为升序</p></blockquote><pre class="brush:php;toolbar:false">function insertionSort(arr){ const len = arr.length; // 注意,i 从 1 开始 for(let i = 1; i = 0 && arr[preIndex] > current){ arr[preIndex+1] = arr[preIndex]; // 对大于current的值,往后移一位,给current的插入腾出位置 preIndex--; } arr[preIndex+1] = current; } return arr; }
堆的表示形式
逻辑结构的表示如下:
在物理数据层的表示如下:
堆排序,是选择排序的优化版本,利用数据结构——树,对数据进行管理。
以大顶堆为例:
通过构建大顶堆
将堆顶的最大数拿出,与堆底的叶子节点进行交换
接着,树剪掉最大数的叶子
再对堆进行调整,重新变成大顶堆
返回步骤2,以此循环,直至取出所有数
在实现代码时,构建大顶堆时,先保证左右子树的有序,再逐步扩大到整棵树。
构建大顶堆
从第一个非叶子节点开始,调整它所在的子树
调整下标1节点的子树后,向上继续调整它的父节点(下标0)所在的子树
最后,完成整个树的调整,构建好大顶堆。
逐个抽出堆顶最大值
堆顶数字与最末尾的叶子数字交换,抽出堆顶数字9。
此时,数字9位置固定下来,树剪掉9所在的叶子。然后,重新构建大顶堆。
大顶堆构建好后,继续抽出堆顶数字8,然后再次重新构建大顶堆。
最后,所有节点抽出完成,代表排序已完成。
以大顶堆为例,对数组进行升序排序
注意点
树的最后一个非叶子节点:(arr.length / 2) - 1
非叶子节点i
的左叶子节点:i*2+1
非叶子节点i
的右叶子节点:i*2+2
function heapSort(arr){ // 初次构建大顶堆 for(let i = Math.floor(arr.length/2) - 1; i >= 0; i--){ // 开始的第一个节点是 树的最后一个非叶子节点 // 从构建子树开始,逐步调整 buildHeap(arr, i, arr.length); } // 逐个抽出堆顶最大值 for(let j = arr.length -1 ; j > 0; j--){ swap(arr, 0, j); // 抽出堆顶(下标0)的值,与最后的叶子节点进行交换 // 重新构建大顶堆 // 由于上一步的堆顶最大值已经交换到数组的末尾,所以,它的位置固定下来 // 剩下要比较的数组,长度是j,所以这里的值length == j buildHeap(arr, 0, j); } return arr; // 构建大顶堆 function buildHeap(arr, i, length){ let tmp = arr[i]; for(let k = 2*i+1; k arr[k]){ k++; } // 将最大的叶子节点,与当前的值进行比较 if(arr[k] > tmp){ // k节点大于i节点的值,需要交换 arr[i] = arr[k]; // 将k节点的值与i节点的值交换 i = k; // 注意:交换后,当前值tmp的下标是k,所以需要更新 }else{ // 如果tmp大于左右子节点,则它们的子树也不用判断,都是小于当前值 break; } } // i是交换后的下标,更新为tmp arr[i] = tmp; } // 交换值 function swap(arr, i, j){ const tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } }
计数排序的要点,是开辟一块连续格子组成的空间,给数据进行存储。
将数组中的数字,依次读取,存入其值对应的下标中。
储存完成后,再按照空间的顺序,依次读取每个格子的数据,输出即可。
所以,计数排序要求排序的数据,必须是有范围的整数。
function countingSort(arr){ let maxValue = Number.MIN_VALUE; let minValue = Number.MAX_VALUE; let offset = 0; // 位移,用于处理负数 const result = []; // 取出数组的最大值, 最小值 arr.forEach(num => { maxValue = num > maxValue ? num : maxValue; minValue = num > minValue ? minValue : num; }); if(minValue { bucket[num+offset]++; }); // 读取格子中的数 bucket.forEach((store, index) => { while(store--){ result.push(index - offset); } }); return result; }
桶排序是计数排序的优化版,原理都是一样的:分治法+空间换时间。
将数组进行分组,减少排序的数量,再对子数组进行排序,最后合并即可得到结果。
对桶内数字的排序,本文采用的是桶排序递归。其实它的本质是退化到计数排序。
function bucketSort(arr, bucketSize = 10){ // bucketSize 每个桶可以存放的数字区间(0, 9] if(arr.length { maxValue = num > maxValue ? num : maxValue; minValue = num > minValue ? minValue : num; }); // 初始化桶的数量 const bucketCount = Math.floor((maxValue - minValue)/bucketSize) + 1; // 桶的数量 // 初始化桶的容器 // 注意这里的js语法,不能直接fill([]),因为生成的二维下标数组,是同一个地址 const buckets = new Array(bucketCount).fill(0).map(() => []); // 将数字按照映射的规则,放入桶中 arr.forEach(num => { const bucketIndex = Math.floor((num - minValue)/bucketSize); buckets[bucketIndex].push(num); }); // 遍历每个桶内存储的数字 buckets.forEach(store => { // 桶内只有1个数字或者空桶,或者都是重复数字,则直接合并到结果中 if(store.length <h2>基数排序</h2><h3>概述</h3><p>基数排序,一般是从右到左,对进制位上的数字进行比较,存入[0, 9]的10个桶中,进行排序。<br> 从低位开始比较,逐位进行比较,让每个进制位(个、十、百、千、万)上的数字,都能放入对应的桶中,形成局部有序。</p><p>为什么10个桶?</p><p>因为十进制数,是由0-9数字组成,对应的进制位上的数字,都会落在这个区间内,所以是10个桶。</p><p>基数排序有两种方式:</p>
MSD 从高位开始进行排序
LSD 从低位开始进行排序
当前解法,只适用正整数的场景。
负数场景,需要加上偏移量解决。可参考 计数排序 的解法。
function radixSort(arr){ let maxNum = arr[0]; // 求出最大的数字,用于确定最大进制位 arr.forEach(num => { if(num > maxNum){ maxNum = num; } }); // 获取最大数字有几位 let maxDigitNum = 0; while(maxNum > 0){ maxNum = Math.floor(maxNum / 10); maxDigitNum++; } // 对每个进制位上的数进行排序 for(let i = 0; i []); // 初始化10个桶 for(let k = 0; k { store.forEach(num => { res.push(num); // 注意这里,先存入桶中的数字,先取出,这样才能保持局部有序 }) }); arr = res; } return arr; /** 求出数字每个进制位上的数字,只支持正整数 @param num 整数 @param digit 位数,从0开始 */ function getDigitNum(num, digit){ return Math.floor(num / Math.pow(10, digit) % 10) } }
【相关推荐:javascript视频教程、web前端】