2.常用排序算法

2021/6/21 22:26:51

编程Tag： 数组算法排序 let function 常用 left length arr

本文主要是介绍2.常用排序算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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)