文件树整理与排序

作者: 小丸子啦啦啦呀 | 来源:发表于2018-05-02 07:58 被阅读0次

文件树整理与排序
常用四种排序算法的思想与实现
《算法笔记》4.1
说说如何使用 Python 遍历目录树
Xcode 使用小Tips
xcode .m .h 文件排序错乱
比较器二叉树实现(BinaryTree)
八大排序算法
ios 拖进工程中的文件顺序错乱
java归并排序

话不多说，先来个华丽的对比图：

对比图

左边乱糟糟，右边看起来舒服多了。
排序规则：

文件夹在前，文件在后
名字从第一个字符开始比较，数字在前，字母在后；如果是同一字母（A与a），大写在前，小写在后。
如果遇到非字母，数字，统一放到最后。（其实新建文件夹和文件的时候就做了数据验证，不允许输入数字和字母意外的字符作为名字，但是为了保险起见，还是做一下处理）。

数据输入格式：

const treeData = {
    name: "root",
    type: "folder", // 文件还是文件夹
    children: [{
        name: 'b', // 名字
        type: 'folder',
        children: [{ 
            name: 'f',
            type: 'file',
        }, {
            name: 'F',
            type: 'folder',
        }]
    }, {
        name: 'c', 
        type: 'file',
    }, {
        name: 'a',
        type: 'file',
    }, {
        name: 'B',
        type: 'fold'
    }, {
        name: 'A',
        type: 'fold',
    }, {
        name: 'd',
        type: 'file',
    }, {
        name: 'e',
        type: 'file',
    }, {
        name: 'E',
        type: 'fold',
    }, {
        name: '510',
        type: 'folder',
        children: [{
            name: '3',
            type: 'file',}
        ]
    }, {
        name: '234',
        type: 'folder',
    }],
}

步骤

假设有一个process方法，该方法可以对一个树节点的所有孩子进行排序处理，那么如果需要排好整棵树，就遍历一下这棵树，对每个树节点调用process方法。

const traverse = (node) => {
  if (node.children && node.children.length) {
    node.children = process(node.children);
    node.children.forEach((element) => {
      traverse(element);
    });
  }
};

process的具体实现：首先把文件夹和文件分别放到不同的列表里，然后再分别对这两个列表进行首字母ascii码排序，完成后分别对这两个列表做大小写处理，最后将这两个列表拼接起来返回。

function process(children) {
  if (children.length <= 1) return children;
  // 把文件夹和文件分开：文件夹在前，文件在后
  let foldList = [];
  let fileList = [];
  for (let i = 0; i < children.length; i += 1) {
    const node = children[i];
    if (node.type === 'folder') {
      foldList.push(node);
    } else if (node.type === 'file') {
      fileList.push(node);
    }
  }
  // 按照首字母ascii码排序
  bubbleSort(foldList);
  bubbleSort(fileList);

  // 处理大小写
  foldList = proceeBS(foldList);
  fileList = proceeBS(fileList);
  // console.log('----fold', foldList);
  // console.log('----file', fileList);
  return foldList.concat(fileList);
}

bubbleSort实现方法,用到了charCodeAt

/**
 * 首字符排序
 * @param {*} list
 * a c B A 1 3 -> 1 3 A B a c
 */
function bubbleSort(list) {
  for (let i = 0; i < list.length; i += 1) {
    for (let j = 0; j < list.length - 1 - i; j += 1) {
      if (list[j].name.charCodeAt(0) > list[j + 1].name.charCodeAt(0)) {
        const temp = list[j];
        list[j] = list[j + 1];
        list[j + 1] = temp;
      }
    }
  }
  return list;
}

处理大小写proceeBS方法实现：

/**
 * 找出大写和小写字母开头的分界点
 * @param {*} list
 * A B E c d e -> 3
 */
const getPivot = (list) => {
  for (let i = 0; i < list.length - 1; i += 1) {
    const charCode = list[i].name.charCodeAt(0);
    if (charCode < 97 && charCode >= 65) {
      const nextCharCode = list[i + 1].name.charCodeAt(0);
      if (nextCharCode >= 97 && nextCharCode <= 122) {
        return i + 1;
      }
    }
  }
  return null;
};
/**
 * 处理大小写排序
 * @param {*} list
 * A B E a e -> A a B E e
 */
function proceeBS(list) {
  // 找出大小写分界位置
  const pivot = getPivot(list);
  // 如果没有分界位置，说明全部都是大写或者小写，没有必要再做处理
  if (pivot === null) return list;
  // console.log('-----pivot', pivot);
  //  放置排好的元素 
  let mergeList = [];
  // 大写字母列表
  const bigList = list.slice(0, pivot);
  //  小写字母列表
  const smallList = list.slice(pivot, list.length);
  // console.log('-----big', bigList);
  // console.log('-----small', smallList);
  let i = 0;
  let j = 0;
  while (i < bigList.length && j < smallList.length) {
    const bigCharCode = bigList[i].name.charCodeAt(0);
    const smallCharCode = smallList[j].name.charCodeAt(0);
    // 刚好相差32  说明是一对儿
    if (smallCharCode - bigCharCode === 32) {
      mergeList.push(bigList[i]);
      mergeList.push(smallList[j]);
      i += 1;
      j += 1;
    } else if (smallCharCode - bigCharCode > 32) {
      mergeList.push(bigList[i]);
      i += 1;
    } else {
      // <32的情况
      mergeList.push(smallList[j]);
      j += 1;
    }
  }
  // console.log('----mergelist before', mergeList, i, j);
  // 看谁还没走完
  // console.log('----i,j', i, j);
  if (i < bigList.length) {
    mergeList = mergeList.concat(bigList.slice(i, bigList.length));
  }
  if (j < smallList.length) {
    mergeList = mergeList.concat(smallList.slice(j, smallList.length));
  }
  // console.log('----mergelist after', mergeList);
  return mergeList;
}

改进

排序的时候只考虑了首字母，如果首字母一样该怎么处理呢？那就继续取出下一个字符再比较，直到某个字符串没有字符可取为止。

/**
 * 按位比较字符串 abx abs -> true
 * @param {*} strA
 * @param {*} strB
 * strA 比 strB 大的时候返回true
 */
function compare(strA, strB) {
  // eslint-disable-next-line
  // debugger;
  let i = 0;
  let j = 0;
  while (i < strA.length && j < strB.length) {
    const aCharCode = strA.charCodeAt(i);
    const bCharCode = strB.charCodeAt(j);
    if (aCharCode > bCharCode) return true;
    if (aCharCode === bCharCode) {
      i += 1;
      j += 1;
    }
    if (aCharCode < bCharCode) return false;
  }
  if (i < strA.length) return true;
  return false;
}

咨询算法小伙伴，他认为在做排序和大小写处理的时候，其实总到了每个节点的name, 所以没有必要带上整个节点进行排序，可以做一个mapping, 排好之后再mapping 回去。

引申

数据处理放前端做还是放后端做？
这个问题我迷惑了好一阵了，有时候从接口取出来的数据并不能直接应用到视图上，需要做一些处理。那什么时候放前端处理比较合适呢？
我想了想，如果一套数据为了适应不同的视图需要转换成不同的格式，那么放在前端做比较合适，因为不这样做的话，每次都要重新从后端取出来，这样做不划算。
随后我问了一下师傅，师傅说首先考虑一下数据量大小和复杂程度，如果量大，处理起来复杂，那还是放后端做，其次可以考虑我说的那一点，有道理。