本文共 2964 字，大约阅读时间需要 9 分钟。

1.排序

（1）冒泡：O(n2)  O(n)

// 优化过的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;  }}// 原生的简单function bubbleSort(arr){  if(!Array.isArray(arr) || arr.length <= 1) return ;  let len = arr.length,      flag = true;  for(let i = 0; i < len; i++){    for(let j = 0; j < len-i-1; j++){      if(arr[j] > arr[j+1]){        flag = false;        [arr[j], arr[j+1]] = [arr[j+1], arr[j]]      }    }    if(flag) break;  }}

(2)选择排序：本质是从前到后从剩余的数组中选出最小的元素替换当前的元素  O(n2) O(n2) 

function selectSort(arr){  let len = arr.length;  if(!Array.isArray(arr) || len <= 1) return;  for(let i = 0; i < len-1; i++){    let minIndex = i;    for(var j = i+1; j < len; j++){      if(arr[i] > arr[j]){        minIndex = j;      }    }    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]  }}

（3）插入排序：每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止  O(n2) O(n)

function insertSort(arr){  let len = arr.length;  if(!Array.isArray(arr) || len <= 1) return;  for(let i = 1; i < len; i++){    let temp = arr[i]    let j = i;    while(arr[j-1] > temp && j-1 >= 0 ){      arr[j] = arr[j-1]      j--    }    arr[j] = temp      }}

(4)归并排序:递归与分治

function mergeSort(array) {  let length = array.length;  // 如果不是数组或者数组长度小于等于0，直接返回，不需要排序   if (!Array.isArray(array) || length === 0) return;  if (length === 1) {    return array;  }  let mid = parseInt(length >> 1), // 找到中间索引值    left = array.slice(0, mid), // 截取左半部分    right = array.slice(mid, length); // 截取右半部分  return merge(mergeSort(left), mergeSort(right)); // 递归分解后，进行排序合并}function merge(leftArray, rightArray) {  let result = [],    leftLength = leftArray.length,    rightLength = rightArray.length,    il = 0,    ir = 0;  // 左右两个数组的元素依次比较，将较小的元素加入结果数组中，直到其中一个数组的元素全部加入完则停止  while (il < leftLength && ir < rightLength) {    if (leftArray[il] < rightArray[ir]) {      result.push(leftArray[il++]);    } else {      result.push(rightArray[ir++]);    }  }  // 如果是左边数组还有剩余，则把剩余的元素全部加入到结果数组中。  while (il < leftLength) {    result.push(leftArray[il++]);  }  // 如果是右边数组还有剩余，则把剩余的元素全部加入到结果数组中。  while (ir < rightLength) {    result.push(rightArray[ir++]);  }  return result;}

(5)快排：partition+递归 我邮课本的更顺手：

function partition(left, right, arr){  let target = arr[left]  let i = left  let j = right + 1  // 右指针在每次要分化的数组尾部之后，不是在尾部  do{    do i++; while(arr[i] < target);    do j--; while(arr[j] > target);    if(i < j){      [arr[i], arr[j]] = [arr[j], arr[i]]    }  }while(i < j)  [arr[left], arr[j]] = [arr[j], arr[left]]  return j;}function QuickSort(i, j, arr){  if(i < j){    let mid = partition(i, j, arr)    QuickSort(i, mid-1, arr)    QuickSort(mid+1, j, arr)  }}let arr = [65,7,89,8,2,6,7,7,8,0]QuickSort(0, arr.length-1, arr)

1.

2.

3.

数字和下划线不影响str.toLowerCase();

转载地址：http://bzxzi.baihongyu.com/