在pptv的实习结束了， 忙着找工作的事，顺便把数据结构的那本书重新复习了一遍。为了加深印象，特意把里面的常用的排序、查找算法用js写了一遍
具体的实例在我的github上，大家可以访问的： https://github.com/chenkehxx/practice js_sort.html文件
//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;
}
//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);
}
}
//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));
}
//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;
//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;
}
常用的其他算法
//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;
}
//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;
}
}
//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;
}
//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;
}
}