首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

JS手撕(十一) 选择排序、快速排序

JS手撕(十一) 选择排序、快速排序 选择排序 原理 选择排序原理就是每次从未排序序列中选择最小元素,放到已排序序列末尾。 那么如何选择最小元素,并把最小元素放到已排序序列末尾?...图片来自菜鸟教程 JS实现 function selectSort(arr) { const len = arr.length; let minIndex; // 保存最小数索引...稍微举例子说明一下为什么是不稳定。 上面一开始2*是在2之后排序完之后2*变成在2之前了,所以选择排序是不稳定。...它是不稳定关键就是让最小数和已排序序列末尾互换位置时,可能把大小相同在前面的移动到了后面去。 快速排序 原理 快速排序原理就是: 从数组挑出一个元素,称为基准(pivot)。...该操作称为分区操作(partition) 递归地把小于基准值地子序列和大于基准值地子序列排序 图片来自菜鸟教程 JS实现 function quickSort(arr, l, r) { if

2.3K20

js 实现选择排序及优化

// 选择排序 // 原理:进行 n-1 趟 循环,每趟循环中遍历所有未排好序数,第一趟循环,从第0个元素开始向后遍历,找到 最小元素,与第1 一个元素进行交换,第二趟,从第 1 个元素开始向后遍历...< 2) { return arr; } // 定义 count 代表执行了趟循环 let count = 0; // 维护每趟循环中排序序列最小值...j : minIndex; // 将最小数索引保存 } // 交换最小与未排序序列开始遍历第一个值 temp = arr[i]; arr...return arr; } // 定义 count 代表执行了趟循环 let count = 0; // 维护每趟循环中排序序列最小值,默认设为第一个值...} } // 交换最小与未排序序列开始遍历第一个值 // 减少交换次数 if (arr[i] !

4.5K10
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    js实现常用排序算法 --冒泡排序,选择排序, 插入排序,快速排序,

    JavaScript实现十大常用排序算法 冒泡排序 选择排序 插入排序 快速排序 归并排序 希尔排序排序 计数排序排序 计数排序 冒泡排序: 原理 选择排序: 原理: 第一次从待排序数据元素中选出最小...(或最大)一个元素,存放在序列起始位置,然后再从剩余排序元素寻找到最小(大)元素,然后放到已排序序列末尾。...以此类推,直到全部待排序数据元素个数为零。选择排序是不稳定排序方法。...代码如下: // 使用选择排序 const selectSort = (arr) => { let len = arr.length let minIndex,temp for(let i...([2,5,3,7,5,9,3,5,7,2,1]) console.log(`最终排序结果${res}`) 执行结果如下 插入排序 原理: 每步将一个待排序记录,按其关键码值大小插入前面已经排序文件适当位置上

    2K20

    排序——选择排序

    选择排序 --- 简单选择排序 基本思想 每一趟在后面 n-i +1个中选出关键码最小对象, 作为有序序列第 i 个记录 算法实现 void SelectSort(SqList &L){ // 对记录序列...L.length]作简单选择排序 for(i = 1; i <= L.length; i++){ // 选择第 i 小记录,并交换到位 k = i; for(j = i + 1; j <...算法分析 含有n个叶子节点完全二叉树深度为log2 n+1,则选择排序每一趟都需作log2n次比较,排序时间复杂度O(nlog2n)。...需要辅助存储空间较多(n-1),和最大值作多余比较等等。 改进:简单选择排序没有利用上次选择结果,是造成速度满重要原因。如果,能够加以改进,将会提高排序速度。...--- 堆排序 堆:把待排序数据元素存放在数组r1…n,把r看成是一棵完全二叉树,每个结点表示一个记录。ri结点左孩子是r2i,右孩子是r2i+1。

    889125

    选择排序(简单选择排序、堆排序

    选择排序 选择排序基本思想是:每一趟在待排序元素中选取关键字最小(或最大)元素加入有序子序列。...简单选择排序 概念 假设排序表为L[1…N],,第i趟排序即从L[1…N]中选择关键字最小元素与L(i)交换,每一趟排序可以确定一个元素最终位置,这样经过n-1趟排序就可以使得整个排序表有序...= i) swap(A[i],A[min]); } } 堆排序 概念 堆排序要结合顺序存储完全二叉树特性进行学习。...堆排序思路很简单:首先将存放在L[1…N]N个元素建成初始堆,由于堆本身特点(以大根堆为例),堆顶元素就是最大值。...输出堆顶元素后,通常将堆底元素送入堆顶,此时根节点已不满足大顶堆性质,对被破坏,将堆顶元素向下调整使其继续保持大顶堆性质,再输出堆顶元素。如此重复,直到堆仅剩一个元素为止。

    54810

    js数组sort()方法排序

    返回一个数组引用,不会创建新数组对象而是将原数组改变成排序数组。 无参调用: 如果调用该方法时没有使用参数,将按字母顺序对数组元素进行排序,按照字符编码顺序进行排序。...sort()方法会根据函数返回值来进行数组元素交换。返回值如下: 若 a 小于 b,在排序数组 a 应该出现在 b 之前,则返回一个小于 0 值。 若 a 等于 b,则返回 0。...:"+newArr); 以上两种只是排序函数中最简单常用,都可以将数组元素排序。...三.对sort(sortby)方法理解: sort()方法主要依靠其回调函数来进行排序,回调函数需要两个参数,在执行sort()方法时会调用回调函数,这时会将调用sort()方法数组元素作为实参两两依次作为回调函数实参传入...以上是关于JSsort函数小结,后续遇到新问题再继续更新!

    6.4K20

    选择排序之简单选择排序

    1.引言 一听到选择排序词第一反应都是要通过选择排序,那么我们第一反应是不是对呢,我们接下来验证一下,了解一下它定义。...简单选择排序:最简单选择方法是顺序扫描序列元素,记住遇到最小元素(一次扫描完毕就找到了一个最小元素。反复扫描就能完成排序工作)。...显然就是我们理解那个意思,每次选择出序列最小元素依次进行排序。 2.问题 给定一个序列,我们将如何用简单选择排序来将它排序好呢,下面将一一讲述。...此题我们是用简单选择排序来实现它,根据简单排序定义,首先是找出序列中最小,然后再找出第二小(也就是除了上一次找出来元素,从剩下元素找出最小),重复去寻找直到排序完成,下面将由图示来展示这个过程...4.结语 方法是用到了直接选择排序算法简单交换,也就是上述交换两个元素位置。这是我对简单选择排序理解,或许还有更好理解,我会继续研究。

    44410

    选择排序

    选择排序 选择排序是冒泡排序升级版 基本原理 每次排序(互换位置)前,先从没排序数列里面选出最小值,然后再把选中最小值和目标值交换位置 比如,第一次排序,所有元素(n)都是未排序,就在所有元素里选出最小值...复杂度 最好复杂度O(n²) 最差复杂度O(n²) 因为选择排序是每次先找出一个最值,然后再进行互换位置,虽然比较次数还是O(n²),但是交换次数由O(n²)减到O(n) 稳定性 稳定算法,所有相同元素相对位置都不变...,就优先从用时最短开始办起,于是乎排个序; 如果是稳定排序,则应该是:D2,A5,C5,B8,E9,合情合理、相安无事; 如果是不稳定,就如上面提到选择排序,那排序结果就变成:D2,C5,A5,B8...选择排序,如果当前元素(a)比一个对比元素(b)小,而该对比元素(b)又出现在一个和当前元素(a)相等元素后面,那么交换后稳定性就被破坏了。...// 将选择j值和找到最小值互换位置 var temp = arr[j] arr[j] = arr[min] arr[min] = temp

    30720

    选择排序

    排序系列: 冒泡排序 ---- 选择排序(Select Sort) 是直观排序,通过一个中间量从带排序找出最大或最小交换到对应位置。再选择次之。选择排序和冒泡排序一样,都有两层循环。...让我们通过动态图来看一下选择排序过程图: 让我们通过动态图来看一下选择排序过程图: 这个动态图演示了一个无序数组使用选择排序转变为一个从大到小有序数组,让我们来观察一下,在进入内循环之前...,会记录一个值,这个值是当前外层循环A[i]值,之后拿着这个值,在内循环遍历数组时候,跟数组元素一个一个比较,如果这个值比当前下标的元素大,那么就双方值继续交换,内循环完成后,将这个值再赋值给...和冒泡排序不一样是冒泡排序如果两个不一样当场就交换,而选择排序是将值给了一个中间变量,让这个中间变量加入内循环,等内循环结束,把真正最大或者最小值赋值给外出循环A[i]。...---- 选择排序原理总结 [1]记录数组第一个元素值(数组长度n)。 [2]遍历n-1次,用该值与其他元素比较,找到最大或者最小一个数交换。 [3]记录数组第二个元素值。

    29240

    选择排序

    前面我们探讨了冒泡排序,今天我们接着讲讲选择排序,其实跟冒泡有点像,但概念上不一样,童鞋,你听我慢慢跟你说。 什么是选择排序?...此时,富人推着一个圆滚滚巨石,将它推入坑,因为直径比坑大,所有刚好卡在了上面,富人巧妙地通过了神坑。...关键是我们要怎样去做好选择,走好每一步,这就引出了我们今天的话题“选择排序”。...所有,我们给出一个定义,给定一组数据集,对这组数据集进行遍历、每次从对应下标开始往后遍历找出最小那位,将其与最开始下标所在元素进行交换位置,形如这样排序,我们将其称为“选择排序”。...://www.cnblogs.com/cnroadbridge/p/13524099.html 优化选择排序 跟之前讲冒泡排序一次冒两个泡泡一个道理,你一次选择两个,一个最大一个最小,最大与最后一个元素换位置

    58470

    排序算法-选择排序

    算法简介 选择排序就是找到数组中最小元素将其和数组第一个元素交换位置,然后在剩下元素中找到最小元素并将其与数组第二个元素进行交换,以此类推,直至整个数组排序结束。...算法描述 找到数组中最小元素并将其和数组第一个元素交换位置 在剩下元素中找到最小元素并将其与数组第二个元素交换,直至整个数组排序 ?...代码实现 /** * 选择 * * @param array */ private static void selectionSort(int[]...由于每次都是选取未排序序列R最小元素 a 与 R 第一个元素交换,很可能破坏了元素间相对位置,因此选择排序是不稳定。...排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性 选择排序 \(O(n^2)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) 不稳定

    1.6K40
    领券