算法: 排序: 用JavaScript实现N大排序算法 about blog

[xvno]

冒泡排序 bubbleSort

基本算法

最基本的排序算法, 比较排序, 理论时间复杂度O( n^2 )

// compare times, swap times, sort result
// 153, 29, [ 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 15, 18, 22, 30, 39, 44, 95 ]
function bubbleSort(data) {
  function swap(arr, i, j) {
    [arr[j], arr[i]] = [arr[i], arr[j]];
  }
  for (let i = data.length - 1; i > 0; i = --i) {
    for (let j = 0; j < i; j++) {
      if (data[j] > data[j + 1]) {
        swap(data, j, j + 1);
      }
    }
  }
  return data;
}

优化算法

1. 提前结束--有事奏来, 无事退朝

本例中, 添加flag标志, 用于提前结束排序, 算是一种改进

// compare times, swap times, sort result
// 62, 29, [ 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 15, 18, 22, 30, 39, 44, 95 ]
function bubbleSort(data) {
  function swap(arr, i, j) {
    [arr[j], arr[i]] = [arr[i], arr[j]];
  }
  let flag;  // 内层循环没有交换, 说明已达到有序
  for (let i = data.length - 1; i > 0; --i) {
    flag = true;
    for (let j = 0; j < i; j++) {
      cnt++;
      if (data[j] > data[j + 1]) {
        flag = false;
        swap(data, j, j + 1);
      }
    }
    if (flag) {
      return data;
    }
  }
  return data;
}

2. 未动归档

当序列中, 局部有序时, 可以忽略这一部分的对比, 通过在内层循记住最后一次交换次序位置, 外层即可直接把该位置作为已排好序的部分来"归档"

// compare times, swap times, sort result
// 52, 29, [ 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 15, 18, 22, 30, 39, 44, 95 ]
function bubbleSort(data) {
  function swap(arr, i, j) {
    [arr[j], arr[i]] = [arr[i], arr[j]];
  }
  
  let prePos = data.length - 1;
  for (let i = prePos; i > 0; i = prePos || i - 1) {
    prePos = false;
    for (let j = 0; j < i; j++) {
      if (data[j] > data[j + 1]) {
        prePos = j + 1
        swap(data, j, prePos);
      }
    }
  }
  return data;
}

双向遍历, 从左到右+从右到左交替遍历, 每次确定1个最大和1个最小

综合利用1, 2两种优化

// compare times, swap times, sort result
// 46, 29, [ 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 15, 18, 22, 30, 39, 44, 95 ]
function bubbleSort(data) {
  function swap(arr, i, j) {
    [arr[j], arr[i]] = [arr[i], arr[j]];
  }
  let prePos = data.length - 1;
  let flag;
  for (let i = prePos; i > 0; i = prePos || i - 1) {
    flag = true;
    prePos = false;
    for (let j = 0; j < i; j++) {
      if (data[j] > data[j + 1]) {
        flag = false;
        prePos = j + 1
        swap(data, j, prePos);
      }
    }
    if (flag) {
      return data;
    }
  }
  return data;
}

综合利用 2,3 种优化

// 108 29 [ 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 15, 18, 22, 30, 39, 44, 95 ]
function bubbleSort(data) {
  function swap(arr, x, y) {
    [arr[x], arr[y]] = [arr[y], arr[x]];
  }
  let l2r = 0, r2l = data.length - 1;
  let flat = true;
  while (l2r < r2l) {
    for (let i = l2r; i < r2l; i++) {
      if (data[i] > data[i + 1]) {
        swap(data, i, i + 1);
        flag = false;
      }
    }
    r2l--;

    for (let j = r2l; j > l2r; j--) {
      if (data[j - 1] > data[j]) {
        swap(data, j, j - 1);
        flag = false;
      }
    }
    l2r++;
    if (flag) {
      break;
    }
    flag = true;
  }
  return data;
}

综合1,2,3种优化

// 71 29 [ 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 15, 18, 22, 30, 39, 44, 95 ]
function bubbleSort(data) {
    function swap(arr, x, y) {
        [arr[x], arr[y]] = [arr[y], arr[x]];
    }
    let l2r = 0, r2l = data.length - 1;
    let flag;
    let l2rPos = false, r2lPos = false;
    while(l2r < r2l) {
        flag = true;
        for(let i = l2r; i < r2l; i ++){
            if(data[i] > data[i+1]) {
                flag = false;
                swap(data, i, i + 1);
                l2rPos = i + 1
            }
        }
        
        r2l = l2rPos || r2l - 1;
        l2rPos = false;
        
        for(let j = r2l - 1; j > l2r; j--) {
            if(data[j-1] > data[j]) {
                swap(data, j, j - 1);
                r2lPos = j - 1
            }
        }
        l2r = r2lPos || l2r + 1;
        rl2Pos = false;
        
    }
    return data;
}

具体测试用例之后再来补充

[xvno]

选择排序 selectionSort

最基本的排序算法之一, 选择排序, 理论O( n^2 )

基本算法

简单选择排序

每次循环得到一个最值

双端选择排序

每次循环定位一大一小两个最值