实现思路

  1. 从乱序数组中，每次遍历找到最小值元素的索引，并和头部元素进行交换(升序)
  2. 指针向后走，重复第一步，直到遍历到尾部
    1. function selectionSort(arr) {
    2.  let minIndex;
    3.  for(let i = 0; i < arr.length; i++) {
    4.      minIndex = i;
    5.      for (let j = i + 1; j < arr.length; j++) {
    6.          if (arr[i] < arr[minIndex]) {
    7.              minIndex = i;
    8.          }
    9.      }
    10.      if (i !== minIndex) {
    11.          [arr[minIndex], arr[i] ] = [arr[i], arr[minIndex]]
    12.      }
    13.  }
    14.  return arr
    15. }
    16. const arr = [8,0,4,6,1,2,7,3,5,9];

双向指针优化，从左往右找最大， 从右往左找最小，性能提升一倍

  1. const arr = [8,0,4,6,1,2,7,3,5,9];
  3. function selectionSort(arr) {
  4.     let left = 0;
  5.     let right = arr.length - 1
  6.     let min, max ;
  7.     while(left < right) {
  8.         min = max = left;
  9.         for (let i = left +1; i < arr.length - left; i++) {
  10.             if (arr[i] > arr[max]) {
  11.                 max = i
  12.             }
  13.             if (arr[i] < arr[min]) {
  14.                 min = i
  15.             }
  16.         }
  17.         if (max !== right) {
  18.             swap(arr, max, right)
  19.         }
  21.         if (min === right) {
  22.             min = max;
  23.         }
  25.         if (min !== left) {
  26.             swap(arr, min, left)
  27.         }
  28.         left++;
  29.         right--;
  30.     }
  31.     return arr;
  32. }
  34. function swap(arr, i, j) {
  35.     let temp = arr[i]
  36.     arr[i] = arr[j]
  37.     arr[j] = temp; 
  38. }

练习题

N 叉树的层序遍历。
给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
例如，给定一个 3 叉树 :

  1. /*
  2.          1
  3.   3  2  1
  4.  5 6  
  6. 返回结果
  7. [
  8.     [1],
  9.   [3,2,4],
  10.   [5,6],
  11. ]
  13. 说明:
  15. 树的深度不会超过 1000。
  16. 树的节点总数不会超过 5000。
  17. */
  19. // 1. 递归
  20. function levelOrder(root) {
  21.     let result = []
  23.   function helper(node, deep) {
  24.       if (node !== null) {
  25.         result[deep] = result[deep] || [];
  26.       result[deep].push(node.val);
  27.       // [ [1], [3,2, 1], [5,6]]
  28.       if (node.children.length !== 0) {
  29.           let newDeep = deep+1;
  30.         node.children.forEach(childNode => {
  31.             helper(childNode, newDeep)
  32.         })
  33.       }
  34.     }
  35.   }
  36.   helper(root, 0)
  39.   return result;
  40. }
  41. // 2. 非递归, BFS
  42. var levelOrder = function(root) {
  44.   let result = []
  45.   if (!root) return result;
  46.   let queue = [root]
  48.   while(queue.length) {
  49.       let level = []
  50.     let len = queue.length;
  51.     for (let i = 0; i < len; i++) {
  52.         let current = queue.shift()
  53.         if (current) {
  54.             level.push(current.val)
  55.             if (current.children && current.children.length > 0) {
  56.                 queue.push(...current.children)
  57.             }
  58.         }
  60.     }
  61.     result.push(level)
  62.   }