排序算法集合

交换数据元素

function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]]
  return arr;
}

冒泡排序

function sort_bubbling(arr, desc) {
  if(!Array.isArray(arr)) throw 'input must an array';
  if(arr.length <= 1) return arr;
  let len = arr.length;
  for(let i = 0; i < len; i ++) {
    for(let j = 0 ; j < len - 1 - i; j++) {
      if(arr[i] < arr[j]){
        swap(arr, i , j);
      }
    }
  }
  return arr
}

选择排序

function sort_select(arr, desc) {
  if(!Array.isArray(arr)) throw 'input must an array';
  if(arr.length <= 1) return arr;
  let len = arr.length;
  for(let i = 0; i < len - 1; i ++) {
    let minIndex = i;
    for(let j = i +1; j < len; j++) {
      if(arr[j] < arr[minIndex]) minIndex = j;
    }
    swap(arr, i ,j);
  }
  return arr
}

插入排序

function sort_insert(arr, desc) {
  if(!Array.isArray(arr)) throw 'input must an array';
  if(arr.length <= 1) return arr;
  let len = arr.length;
  for(let i = 1; i < len; i ++) {
    let j = i,temp = arr[i];
    while(j > 0 && arr[j] > temp) {
      arr[j] = arr[j - 1];
      j --;
    }
    arr[j] = temp;
  }
  return arr
}

归并排序

自顶向下

function merge(left, right) {
  let result = [];
  while(left.length && right.length) {
    if(left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while(left.length) {
    result.push(left.shift());
  }
  while(right.length) {
    result.push(right.shift());
  }
  return result;
}
function sort_merge(arr) {
  if(!Array.isArray(arr)) throw 'input must an array';
  if(arr.length <= 1) return arr;
  let middle = parseInt(arr.length/2);
  let left = arr.slice(0, middle);
  let right = arr.slice(middle);
  return merge(sort_merge(left), sort_merge(right));
}

自底向上

function sort_merge(arr) {
  if(!Array.isArray(arr)) throw 'input must an array';
  if(arr.length <= 1) return arr;
}

快速排序

// by ruanyifeng
function sort_quick(arr) {
  if(!Array.isArray(arr)) throw 'input must an array';
  if(arr.length <= 1) return arr;
  let middle = parseInt(arr.length/2);
  let left = [], right = [], pointV = arr.splice(middle,1)[0];
  for(let i = 0; i < arr.length; i ++) {
    if(arr[i] < pointV) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return sort_quick(left).concat([pointV], sort_quick(right));
}

阮一峰写的快排会造成空间浪费，还是要在理解快排思想的情况下再做优化

// 升序
function sort_quick(arr) {
  if (!Array.isArray(arr)) throw 'input must be an arrray'
  function sort(arr, left=0, right=arr.length - 1) {
      let flag = arr[0]
      let i = left;
      let j = right;
        while(i < j) {
        while (arr[j] < flag && j > i) {
            j --
        }
        while (arr[i] > flag && i < j) {
          i ++
        }
        swap(arr, i, j);
      }
        if (arr[i] < flag) swap(arr, 0, i);
        sort(arr, 0, i-1);
      sort(arr, i, arr.length - 1); 
        return arr;
  }  
}