加载中......
搜索
注册登录 快速发布
输入验证码，即可复制
微信扫码下载好向圈APP, 登陆后即可进入消息页面查看验证码
只需要3秒时间
使用道具
莪是_贾赛

2021-02-23 15:58

JavaScript排序算法

1：基本概念

时间复杂度：算法执行所耗费的时间。

这个复杂度直接和样本的个数有关，复杂度反映了算法的性能，一般来说，复杂度越低，算法所消耗的时间越短。
/* O(N1) */for (var i = 0; i < data.length; i++) { ...}​/* O(N2) */for (var i = 0; i < data.length; i++) { for (var j = 0; j < data.length; j++) { ... }}
空间复杂度：运行一个程序所需内存的大小。

空间复杂度和时间复杂度是对立的，比如说，时间复杂度越高，空间复杂度越低；反之则相反。

内排序：所有排序操作都在内存中完成。

2：常用的排序算法

冒泡排序（Bubble Sort）

基本概念：依次比较相邻的两个数,将小数放在前面，大数放在后面。

时间复杂度：O(N2)。

实现原理：重复的走访要排序的数列，一次比较两个元素，大的元素放后面，如果它们的顺序错误就把它们交换过来。

代码实现：有两层循环嵌套，外循环遍历数组的每一项，内循环用于两两元素的比较，每次内循环减1。
function bubbleSort(arr) { var length = arr.length; for (var i = 0; i < length; i++) { for (var j = 0; j < length - 1 - i; j++) { if (arr[j] > arr[j+1]) { [arr[j], arr[j+1]] = [arr[j+1], arr[j]];  } } } return arr;}
选择排序（Selection Sort）

时间复杂度：O(N2)。

实现原理：从未排序的序列中找到最小(大)的元素存放到指定的起始位置，再从未排序的序列元素中重复上一步，直至排序完成。

代码实现：两层循环嵌套，外循环遍历数组的每一项，内循环用于找到样本里面的最小值或者最大值，每次内循环减1。
function selectionSort(arr) { var length = arr.length; var minIndex, temp; for (var i = 0; i < length - 1; i++) { minIndex = i; for (var j = i + 1; j < length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } [arr[minIndex], arr] = [arr, arr[minIndex]]; } return arr;}
快速排序（Quick Sort）

时间复杂度：O(N * log2N)。

实现原理：通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。

代码实现：找到一个数作为参考，然后比这个数字大的放在数字左边，比它小的放在右边，分别再对左右两边的序列做相同的操作。
function partition(arr, low, high) { let pivot = arr[low]; while (low < high) { while (low < high && arr[high] > pivot) { --high; } arr[low] = arr[high]; while (low < high && arr[low] <= pivot) { ++low; } arr[high] = arr[low]; } arr[low] = pivot; return low;}function quickSort(arr, low, high) { if (low < high) { let pivot = partition(arr, low, high); quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } return arr;}
插入排序（Insertion Sort）

时间复杂度：O(N2)。

实现原理：构建一个有序序列，未排序数据在已排序序列中从后向前扫描，找到正确位置插入。

代码实现：两层循环嵌套，创建已排序数组, 起始包含数组的第一个元素，比这个数字大的放在数字左边， 比它小的放在右边。
# js8种排序 # js实现选择排序 # 用js写一个排序
程序员圈
28456 查看 1 0 反对

说说我的看法高级模式

您需要登录后才可以回帖 登录|立即注册

全部评论
  • v4734750

    2021-2-24 09:54:01 使用道具

    来自： 北京朝阳来自： 北京朝阳来自： 北京朝阳来自： 北京朝阳
    转发了
    回复 0

相关阅读

程序员圈

程序员圈

帖子 221033

 加入 529329
百度地图|小黑屋|看往APP（原好向圈） |网站地图
版权所有 © 上海看往信息科技有限公司 | 侵权举报 | 本站法律顾问：上海品道事务所 |违法和不良信息举报电话：17317527721 |举报邮箱：2100458018@qq.com | Wxb | Weifa | 亲爱的市民朋友，上海警方反诈劝阻电话“962110”系专门针对避免您财产被骗受损而设，请您一旦收到来电，立即接听 |封禁账号 | 沪ICP备2022028193号-1