Comments (2)
冒泡排序算法
- 平均时间复杂度是O(n^2)
- 最优时间复杂度是O(n)
- 空间复杂度O(n)
var bubbleSort= function (nums) {
var len = nums.length
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
var temp = nums[j]
nums[j] = nums[j + 1]
nums[j + 1] = temp
}
}
}
return nums
};
鸡尾酒排序算法
鸡尾酒排序算法是冒泡排序算法的优化,优化点是采用双向比较
- 平均时间复杂度是O(n^2)
- 最优时间复杂度是O(n)
- 空间复杂度O(n)
function cockTailSort(nums) {
var start = 0
var end = nums.length - 1;
var temp;
while (start < end) {
//注意i的取值范围[star, end), 半开半闭
for (var i = start; i < end; i++) {
if (nums[i] > nums[i + 1]) {
temp = nums[i];
nums[i] = nums[i + 1];
nums[i + 1] = temp;
}
}
end--;
//注意i的取值范围(star, end], 半开半闭
for (var i = end; i > start; i--) {
if (nums[i - 1] > nums[i]) {
temp = nums[i];
nums[i] = nums[i - 1];
nums[i - 1] = temp;
}
}
start++;
}
return nums
}
from blog.
插入排序算法
Insertion Sort 和打扑克牌时,从牌桌上逐一拿起扑克牌,在手上排序的过程相同。
举例:
Input: {5 2 4 6 1 3}。
首先拿起第一张牌, 手上有 {5}。
拿起第二张牌 2, 把 2 insert 到手上的牌 {5}, 得到 {2 5}。
拿起第三张牌 4, 把 4 insert 到手上的牌 {2 5}, 得到 {2 4 5}。
以此类推
一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
- 从第一个元素开始,该元素可以认为已经被排序
- 取出下一个元素,在已经排序的元素序列中从后向前扫描
- 如果该元素(已排序)大于新元素,将该元素移到下一位置
- 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
- 平均时间复杂度是O(n^2)
- 最优时间复杂度是O(n)
- 空间复杂度O(n)
function insertionSort (nums) {
var len = nums.length
for (var i = 0; i < len; i++) {
var num = nums[i]
//注意j的起始值
var j = i - 1
while (j >= 0 && nums[j] > num) {
nums[j + 1] = nums[j]
j--
}
//注意此处的下标
nums[j + 1] = num
}
return nums
};
from blog.
Related Issues (20)
- ES5实现ES6的class关键字
- 实现可取消的Promise
- 实现失败可自动重试一定次数的fetchWithRetry函数
- 实现async/await
- 实现`Promise.allSettled()`
- 实现 `Promise.all()`
- 实现 `Promise.race()`
- 实现`Promise.any()`
- 实现`shuffle() `函数打乱数组,使产生的各种可能的组合概率相等
- https加密、解密、验证及传输过程
- Javascript中Event Loop与node中的Event Loop
- 常见面试题总结 HOT 2
- 二分法查找模板
- 实现柯里化(Curry)函数
- 实现Promise.finally方法
- 实现一个符合 Promises/A+ 规范的 Promise
- 实现列表与数结构互转 HOT 1
- 实现发布/订阅模式
- 实现sleep函数
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from blog.