行排序算法

行排序算法

统计信息：字数 3936 阅读8分钟

简单排序：单列排序

单行数据结构如下

row = {
  _id,
  key1: value1,
  key2: value2,
  ...
}

全部行是一个数组

rows = [row1, row2]

排序数据结构：假设排序列是 key1，排序方式是升序或者降序 increase decrease

let sort = {
  column_key: key1,
  type: 'increase',
}

实际排序中，可能不同列的数据结构不一样，即 value1 value2 的数据结构不同，那么需要不同的排序函数。这里为了简化，设置 value 都是合法的数值，那么排序函数可以简写成：

/**
 * [compareNumber use sort type to compare two number]
 * @author Michael An
 * @DateTime 2022-01-14T11:11:13+0800
 * @param    {[string]}                 type [sort type]
 * @param    {[number]}                 num1 [first row value number]
 * @param    {[number]}                 num2 [second row value number]
 * @return   {[boolean]}                      [num1 and num2 sequence]
 */
function compareNumber(row1, row2) {
  // sort 直接从外部函数拿到
  const { column_key, type } = sort;
  const num1 = row1[column_key];
  const num2 = row2[column_key];
  if (type === 'increase') {
    return num1 > num2 ? true : false;
  } else {
    return num1 < num2 ? true : false;
  }
}

然后对全部行进行排序（最好先把原始的行深复制一次，避免直接更改原始数组）排序算法是原地算法

function sortRows(rows, sort) {
  const { column_key, type } = sort;
  rows.sort(compareNumber);
}

实例（测试正常）

function sortRows(rows, sort) {
  function compareNumber(row1, row2) {
    const { column_key, type } = sort;
    const num1 = row1[column_key];
    const num2 = row2[column_key];
    if (type === 'increase') {
      return num1 > num2 ? 1 : -1;
    } else {
      return num1 < num2 ? 1 : -1;
    }
  }
  rows.sort(compareNumber);
}

const rows = [{'0000': 1},{'0000': 2},{'0000': 100},{'0000': 30},{'0000': 20}];
const sort = { column_key: '0000', type: 'increase' };
sortRows(rows, sort);
console.log(rows);

复杂排序：多列排序

对多列进行排序，多列的数据类型不同。假设 sort1 的权重大于 sort2，第一个相同时，才执行第二个排序

let sorts = [ sort1, sort2, sort3 ];

思路：递归。如果第一层排序得出结果，直接返回；如果第一层没有得出结果，再进行第二层排序。其他不变。

实例（测试正常）

function sortRows(row1, row2, sort_index) {
  const { column_key, type } = sorts[sort_index];
  const num1 = row1[column_key];
  const num2 = row2[column_key];

  // 如果当前排序结果相同
  if (num1 === num2) {
    // 如果存在下一个排序，递归比较
    if (sorts[sort_index + 1]) {
      return sortRows(row1, row2, sort_index + 1);
    }
    // 如果不存在下一个排序，直接返回1（这两行排序不变）
    return 1;
  }
  // 如果当前结果不同，直接比较并返回
  if (type === 'increase') {
    return num1 > num2 ? 1 : -1;
  } else {
    return num1 < num2 ? 1 : -1;
  }
}

const rows = [
  {'0000': 1, '1111': 4},
  {'0000': 1, '1111': 3},
  {'0000': 100, '1111': 2},
  {'0000': 1, '1111': 2},
  {'0000': 20, '1111': 5},
];

// 按照 0000 升序，1111 列降序
const sorts = [
  { column_key: '0000', type: 'increase' },
  { column_key: '1111', type: 'decrease' }
];

rows.sort((row1, row2) => {
  const initIndex = 0;
  return sortRows(row1, row2, initIndex);
});

console.log(rows);
// [                           
//   { '1111': 4, '0000': 1 }, 
//   { '1111': 3, '0000': 1 },
//   { '1111': 2, '0000': 1 },
//   { '1111': 5, '0000': 20 },
//   { '1111': 2, '0000': 100 }
// ]

算法分析

最好的情况：行个数N，条件是全部的行的第一个排序都不同

最差的情况：行个数 N * 排序列 M，条件是行的全部排序列的值都相等

---

Last update: November 9, 2024