js基础算法实现

冒泡排序

// 冒泡排序: 比较两个相邻的项，如果第一个大于第二个则交换他们的位置,元素项向上移动至正确的顺序，就好像气泡往上冒一样
冒泡demo:
function bubbleSort(arr) {
    let len = arr.length;
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        //相邻元素两两对比
                [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
            }
        }
    }
    return arr;
}

选择排序

/ 选择排序：大概思路是找到最小的放在第一位，找到第二小的放在第二位，以此类推 算法复杂度O(n^2)
选择demo:
function selectionSort(arr) {
	let len = arr.length;
	let minIndex;
	for (let i = 0; i < len - 1; i++) {
		minIndex = i;
		for (let j = i + 1; j < len; j++) {
			if (arr[j] < arr[minIndex]) {     //寻找最小的数
			    minIndex = j;                 //将最小数的索引保存
		    }
		}
		[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
	}
return arr;
}

排序

//冒泡排序(相邻两个数字进行比较)
function bubbleSort(arr) {
  if(!Array.isArray(arr) || arr.length <= 1) return;
  let lastIndex = arr.length - 1;
  while(lastIndex > 0) {
    let flag = true, k = lastIndex;
    for(let j = 0; j < k; j++) {
      if(arr[j] > arr[j + 1]) {
        flag = false;
        lastIndex = j;
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
    if(flag) break;
  }
  return arr;
}

//选择排序（找最小或者最大的数字作为首元素）
function selectSort(arr) {
  let length = arr.length;
  if(!Array.isArray(arr) || length <= 1) return;
  for(let i =0; i < length; i++) {
    let minIndex = i;
    for(let j = i + 1; j < length; j++) {
      if(arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
  }
  return arr;
}

//插入排序(插入到前面已经排好序的有序序列中)
function insertSort(arr) {
  let length = arr.length;
  if(!Array.isArray(arr) || length <= 1) return;
  for(let i = 1; i < length; i++) {
    let temp = arr[i];
    let j = i;
    while(j - 1 >= 0 && arr[j-1] > temp) {
      arr[j] = arr[j-1];
      j--;
    }
    arr[j] = temp;
  }
  return arr;
}

//希尔排序(把数组按下标的一定增量分组，对每组使用直接插入排序)
function hillSort(arr) {
  let length = arr.length;
  if(!Array.isArray(arr) || length <= 1) return;
  for (let gap = parseInt(length >> 1); gap >= 1; gap = parseInt(gap >> 1)) {
    for(let i = gap; i< length; i++) {
      let temp = arr[i];
      let j = i;
    	while(j - gap >= 0 && arr[j-gap] > temp) {
          arr[j] = arr[j-gap];
          j -= gap;
        }
      arr[j] = temp;
    }
  }
  return arr;
}

//归并排序（递归的将数组两两分开直到只包含一个元素，然后将数组排序合并)
function mergeSort(arr) {
  let length = arr.length;
  if(!Array.isArray(arr) || length === 0) return;
  if(length === 1) return arr;
  let mid = parseInt(length >> 1),
      left = arr.slice(0, mid),
      right = arr.slice(mid, length);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(leftArr, rightArr) {
  let result = [],
  	leftLength = leftArr.length,
  	rightLength = rightArr.length,
  	il = 0,
 	ir = 0;
  while(il < leftLength && ir < rightLength) {
    if(leftArr[il] < rightArr[ir]) {
      result.push(leftArr[il++]);
    }else {
      result.push(rightArr[ir++]);
    }
  }
  while(il < leftLength) {
    result.push(leftArr[il++]);
  }
  
  while(ir < rightLength) {
    result.push(rightArr[ir++]);
  }
  return result;
}

//快速排序最佳（将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，这个排序过程可以递归进行）
function quickSort(arr, start, end) {
  let length = arr.lenght;
  if(!Array.isArray(arr) || length <= 1 || start >= end) return ;
  let index = partition(arr, start, end);
  quickSort(arr, start, index -1);
  quickSort(arr, index+1, end);
  return arr;
}
function partition(arr, start, end) {
  let pivot = arr[start];
  while(start < end) {
    while(arr[end] >= pivot && start < end) {
      end--;
    }
    arr[start] = arr[end];
    while(arr[start] < pivot && start < end) {
      start ++;
    }
    arr[end] = arr[start];
  }
  arr[start] = pivot;
  return start;
}

let arr1 = [1,2,4,3];
let result = quickSort(arr1, 0, 3);
console.log(result)

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

int reverse(int x) {
    int num = 0;
    while(x){
        int pop = x%10;
        if (num > INT_MAX/10 || (num == INT_MAX / 10 && pop > INT_MAX % 10)) return 0;
        if (num < INT_MIN/10 || (num == INT_MIN / 10 && pop < INT_MIN % 10)) return 0;
        num = num * 10 + pop;
        x /= 10;
    }
    return num;
}

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

unordered_map<int,int> m;
for(int i=0;i<nums.size();i++)
{
    if(m.find(target-nums[i]) != m.end())      
        return {m[target-nums[i]] , i};       

    m[nums[i]]=i; 
}
return {};

判断一个整数是否是回文数

if(x < 0 || (x % 10 == 0 && x != 0)){
    return false;
}
int num = 0;
while(x > num){
    num = num * 10 + x % 10;
    x /= 10;
}

return x == num || x == num / 10;