数据结构和算法的js描述
先摘抄书中的一段推荐序：
在前端工程师中，常常有一种声音：“我为什么要学习数据结构与算法？没有数据结构与 算法，我一样很好地完成了工作？” 实际上，算法是一个十分宽泛的概念，我们写的任何程序都可称为算法，甚至往冰箱里面 放一头大象，也要经过开门、放入、关门这样的规划，这也可以视为一种简单的算法。可 以说，简单的算法是人类的本能。而算法知识的学习则是吸取前人的经验，对复杂的问题 进行归类、抽象，帮助我们脱离刀耕火种时代，系统掌握算法的一个过程。 随着自身成长和职业发展，不论是做前端、服务端还是客户端，任何一个程序员都会开始 面对更加复杂的问题，算法和数据结构知识就变得不可或缺了。 我一直认为前端工程师则是最需要重视算法和数据结构基础的人。因为历史原因，不少前 端工程师是从视觉设计、网站编辑转过来的，在学校没有学过相应的基础课程，而数据结 构与算法的经典名著大部分又没照顾到入门的需要，所以前端工程师如果自身不重视算法 和数据结构这样的基础知识，很可能陷入数年从事单一重复劳动毫无成长这样的职业发展 困境。在移动浪潮到来之后，用户体验要求越来越高，对前端提出了更高的要求，前端这 个职能，必须提高自身才能继续发展，未来的网页UI，绝对不是靠几个选择器操作加超链 接就能应付的。
程劭非
阿里无线事业部高级技术专家
2014 年7 月
冒泡排序
时间复杂度O（n^2） 稳定
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - i - 1; j++) { //第一次排序后最后一个已经为最大的数了
if (arr[i] > arr[i + 1]) {
var temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
return arr;
}
选择排序
时间复杂度为O(n^2) 不稳定
function selectSort(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[i] > arr[j]){
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
插入排序
时间复杂度为O(n^2) 稳定
function insertSort(arr) {
var len = arr.length;
var preIndex,temp;
for(var i = 1; i < len; i++){
preIndex = i - 1;
temp = arr[i];
while(preIndex >= 0 && arr[preIndex] > temp ){
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = temp;
}
return arr;
}
希尔排序
时间复杂度为O(nlogn) 不稳定 插入排序改进版，间隔序列可以自己设定
function shellSort(arr) {
var len = arr.length;
var 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++ ){
for(var j = i; j>=gap && arr[j-gap]>arr[j]; j-=gap){
swap(arr,j,j-gap);
}
}
}
}
function swap(data,j,j){ //调换数组中的两个数
var temp;
temp = data[i];
data[i] = data[j];
data[j] = temp;
}
快速排序
时间复杂度为O(nlogn) 不稳定
function quickSort(arr) {
var len = arr.lenth;
if(len <= 1){
return arr;
}
var pivotIndex = Math.floor(len / 2);
var pivot = arr.splice(pivetIndex, 1);//选取中间的数为基数
var left = [];
var right = [];
for(var i = 0; i < len; i++){
arr[i] > pivot? right.push(arr[i]) : left.push(arr[i]);// 比基数大的放入右边数组，大的放右边数组
}
return quickSort(left).concat([pivot], right);
}
归并排序
时间复杂度为O(nlogn) 稳定
function mergeSort(arr) {
var len = arr.length;
if(len <= 1){
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
var newArr = [];
while(left.length > 0 && right.length > 0){
left[0] >= right[0] ? newArr.push(right.shift()) : newArr.push(left.shift());
}
if(left.length > 0)
newArr.concat(left); //最后左右的数组的长度不一样
if(right.length > 0)
return newArr.concat(right);
}
