常见的js算法_javascript数据结构与算法
常见的几种js算法
(一)快速排序算法 1.1: 先从数列中取出一个数作为“基准”。 1.2: 分区过程:将比这个“基准”大的数全放到“基准”的右边,小于或等于“基准”的数全放到“基准”的左边。 1.3: 再对左右区间重复第二步,直到各区间只有一个数。
代码实现:
var quickSort = function(arr) {
if (arr.length <= 1) {
return arr; }
var pivotIndex = Math.floor(arr.length / 2); //基准位置(理论上可任意选取)
var pivot = arr.splice(pivotIndex, 1)[0]; //基准数
var left = [];
var right = [];
for (var i = 0; i < arr.length; i ){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right)); //链接左数组、基准数构成的数组、右数组
};
(二)希尔排序,也称递减增量排序算法 1.1: 选择一个增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1; 1.2: 按增量序列个数 k,对序列进行 k 趟排序; 1.3: 每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。 代码实现:
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len/3) {
//动态定义间隔序列
gap = gap*3+1;
}
for (gap; gap > 0; gap = Math.floor(gap/3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j >= 0 && arr[j] > temp; j -= gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}
(三)选择排序算法 1.1: 选择一个增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1; 1.2: 从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。 1.3: 重复第二步,直到所有元素均排序完毕。 代码实现:
function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
// 寻找最小的数
minIndex = j; // 将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
(四)归并排序算法 1.1: 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个典型的应用。 合并排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。 代码实现:
function merge(leftArr, rightArr){
var result = [];
while (leftArr.length > 0 && rightArr.length > 0){
if (leftArr[0] < rightArr[0])
result.push(leftArr.shift()); //把最小的最先取出,放到结果集中
else
result.push(rightArr.shift());
}
return result.concat(leftArr).concat(rightArr); //剩下的就是合并,这样就排好序了
}
function mergeSort(array){
if (array.length == 1) return array;
var middle = Math.floor(array.length / 2); //求出中点
var left = array.slice(0, middle); //分割数组
var right = array.slice(middle);
return merge(mergeSort(left), mergeSort(right)); //递归合并与排序
}
var arr = mergeSort([32,12,56,78,76,45,36]);
console.log(arr); // [12, 32, 36, 45, 56, 76, 78]
(五)冒泡排序算法 1.1: 先从数列中取出一个数作为“基准”。 1.2: 第一轮的时候最后一个元素应该是最大的一个。 1.3: 按照步骤一的方法进行相邻两个元素的比较,这个时候由于最后一个元素已经是最大的了,所以最后一个元素不用比较。 代码实现:
function sortarr(arr){
for(i=0;i<arr.length-1;i++){
for(j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
var temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
return arr;
}
(六)插入排序算法 1.1: 从第一个元素开始,该元素可以认为已经被排序; 1.2: 取出下一个元素,在已经排序的元素序列中从后向前扫描,如果该元素(已排序)大于新元素,将该元素移到下一位置; 1.3: 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置,将新元素插入到该位置后; 1.4: 重复步骤2~5。 代码实现:
function insertSort(arr){
var len = arr.length;
for (var i = 1; i < len; i++) {
var key = arr[i];
var j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
(七)二分插入排序算法 1.1: 从第一个元素开始,该元素可以认为已经被排序; 1.2: 取出下一个元素,在已经排序的元素序列中二分查找到第一个比它大的数的位置; 1.3: 将新元素插入到该位置后; 1.4: 重复上述两步; 代码实现:
function insertSort(arr){
var len = arr.length;
for (var i = 1; i < len; i++) {
var key = arr[i];
var j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/185989.html原文链接:https://javaforall.cn
相关文章
- 使用 JavaScript 下载文件
- html js 全局 变量,JS定义全局变量
- js数据转换为html,JavaScript怎么进行类型转换?「建议收藏」
- Js排序算法_js 排序算法
- JavaScript数组求和_js获取对象数组的第一个元素
- JavaScript刷LeetCode拿offer-js版字典_2023-02-28
- >JavaScript中几个操作元素对象的函数方法
- [javascript] Promise简单学习使用详解编程语言
- 数据库JavaScript 的 Oracle 数据库连接技术简介(js如何连接oracle)
- MySQL数据库不支持存储JavaScript脚本(mysql不存js)
- Oracle中JS的优势让数据库性能提升(oracle中 js)
- 设置和读取cookie的javascript代码
- JavaScript入门教程(3)js面向对象
- javascript表单验证常见正则
- JavaScript对象链式操作测试代码
- javascript数字数组去重复项的实现代码
- javascript之querySelector和querySelectorAll使用介绍
- JavaScript高级程序设计阅读笔记(十六)javascript检测浏览器和操作系统-detect.js
- JavaScript高级程序设计阅读笔记(二十)js错误处理
- JavaScript(js)设置默认输入焦点(focus)
- Javascript模块化编程(三)require.js的用法及功能介绍
- JavaScript运行时库属性一览表
- javascript文件中引用依赖的js文件的方法
- JavaScript中对象属性的添加和删除示例
- javascript记录文本框内文字个数检测文字个数变化
- JavaScript学习笔记之JS事件对象