javascript排序 查找算法大全
2013-10-10 15:08:38

[javascript]

//js插入排序

function insertSort(arr){

var result =[];

result.push(arr[0]);

for(var i = 1, len = arr.length; i < len; i++){

var el = arr[i];

if(result[i - 1] > el){

for(var j = 0; j < i; j++){

if(result[j] > el){

result.splice(j, 0, el);

break;

}

}

}else{

result.push(el);

}

}

return result;

}

[javascript]

//js的归并排序

function mergeSort(arr){

var len = arr.length;

if(len > 1){

var index = Math.floor(len / 2);

var left = arr.slice(0, index), right = arr.slice(index);

return merge(mergeSort(left), mergeSort(right));

}else{

return arr;

}

function merge(left, right){

var arr = [];

while(left.length && right.length){

if(left[0] < right[0]){

arr.push(left.shift());

}else{

arr.push(right.shift());

}

}

return arr.concat(left, right);

}

}

[javascript]

//js快排

function QuickSort(arr){

if(arr.length <= 1){

return arr;

}

var index = Math.floor(arr.length / 2);

var key = arr.splice(index, 1)[0];

var left = [], right = [];

for(var i = 0; i < arr.length; i++){

if(arr[i] < key){

left.push(arr[i]);

}else{

right.push(arr[i]);

}

}

return QuickSort(left).concat([key], QuickSort(right));

}

[javascript]

//js冒泡

function bubbleSort(arr){

var len = arr.length;

for(var i = 0; i < len; i++){

for(var j = len -1; j > i; j--){

if(arr[j] > arr[j+1]){

var temp = arr[j];

arr[j] = arr[j+1];

arr[j + 1] = temp;

}

}

}

return arr;

[javascript]

//js二分查找

function binarySearch(arr, key, low, hight){

var mid = Math.floor((low + hight) / 2);

var result = -1;

console.log(key, low, hight, mid);

if(key == arr[mid]){

result = mid;

return result;

}else if(key > arr[mid]){

hight = mid - 1;

binarySearch(arr, key, low, hight);

}else{

low = mid + 1;

binarySearch(arr, key, low, hight);

}

return result;

}

[javascript]

//js查找两个数组中相同的元素

function findSame(arr1, arr2){

var len1 = arr1.length, len2 = arr2.length;

var i = 0, j = 0, result = [];

while(i < len1 && j < len2){

if(arr1[i] == arr2[j]) {

result.push(arr1[i]);

i++;

j++;

}else if(arr1[i] < arr2[j]){

i++;

}else{

j++;

}

}

return result;

}

[javascript]

//js全排列

function sortAll(arr, flag){

var len = arr.length;

if(len == flag){

console.log(arr);

}else{

for(var i = flag; i < arr.length; i++){

swap(arr, i , flag);

sortAll(arr, flag + 1);

swap(arr, i, flag);

}

}

function swap(arr, i, flag){

var temp = arr[i];

arr[i] = arr[flag];

arr[flag] = temp;

}

}

[javascript]

//js求最大子序列

function max_sub(arr){

var max = 0, temp_sum = 0, len = arr.length;

for(var i =0; i < len; i++){

temp_sum += arr[i];

if(temp_sum > max){

max = temp_sum;

}else if(temp_sum < 0){

temp_sum = 0;

}

}

return max;

}

[javascript]

//js实现中文字段截取无乱码

/*这里应该还需要判断str的长度，因为中文字符应该占2个长度*/

function GBsubstr(str, start, len){

if(str.length < len){

return str;

}else{

var result = '';

var length = start + len;

for(var i = start; i < length; i++){

if(str.charCodeAt(i) > 255){

result += str.substr(i, 2);

i++;

}else{

result += str.substr(i, 1);

}

}

return result;

}

}