function selectSort (arr) {
    // 如果数组长度小于2，则返回原数组
    if (arr && arr.length < 2) {
        return arr;
    }

    let index, temp;
    const len = arr.length;
    for (let i = 0; i < len - 1; i++) { // 这里使用len-1是因为最后一次最后一个值肯定是最大的了，所以没必要再执行一次循环操作
        index = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[index]) { // 找出最小值
                index = j; // 保存最小值的索引
            }
        }
        // 交换两个值
        temp = arr[i];
        arr[i] = arr[index];
        arr[index] = temp;
    }
    return arr;
}

var arr = [3, 1, 5, 9, 4, 8, 7, 10, 2, 6];
selectSort(arr); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

function BubbleSort (arr) {
    // 如果数组长度小于2，则返回原数组
    if (arr && arr.length < 2) {
        return arr;
    }

    let temp;
    const len = arr.length;

    for (let i = 0; i < len - 1; i++) { // 外层循环只需比较length-1次
        for (let j = 0; j < len - 1 - i; j++) { // 内层循环，只需遍历比较未排序的
            if (arr[j] > arr[j + 1]) { // 两两比较
                // 交换值，大的值放后面
                // [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]; // 可以用es6数组语法交换值
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

var arr = [3, 1, 5, 9, 4, 8, 7, 10, 2, 6];
BubbleSort(arr); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

function quickSort(arr) {
    // 如果数组长度小于2，则返回原数组
    if (arr && arr.length < 2) {
        return arr;
    }

    let leftArr = []; // 存储小于分界值的数组
    let rightArr = []; // 存储大于等于分界值的数组
    const prev = arr.splice(0, 1)[0]; // 取出数组的第一个值作为分界值(这个分界值可以是数组中的任意一个值)
    const len = arr.length; // 数组长度必须在取出分界值之后获取
    for (let i = 0; i < len; i++) {
        arr[i] < prev ? leftArr.push(arr[i]) : rightArr.push(arr[i]);
    }
    return quickSort(leftArr).concat(prev, quickSort(rightArr));
}

var arr = [3, 1, 5, 9, 4, 8, 7, 10, 2, 6];
quickSort(arr); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

function quickSort (arr) {
    // 如果数组长度小于2，则返回原数组
    if (arr && arr.length < 2) {
        return arr;
    }

    const [prev, ...rest] = arr;
    return [
        ...quickSort(rest.filter(value => value < prev)), // 筛选出比prev的值小的值放在prev的左边，然后再进行递归操作
        prev,
        ...quickSort(rest.filter(value => value >= prev)), // 筛选出比prev的值大的放在prev的右边，然后再进行递归操作
    ]
}

var arr = [3, 1, 5, 9, 4, 8, 7, 10, 2, 6];
quickSort(arr); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

function insertSort (arr) {
    let res = [];
    res.push(arr[0]);
    for (let i = 1; i < arr.length; i++) {
        let cur = arr[i];
        for (let j = res.length; j >= 0; j++) {
            if (cur > res[j]) {
                res.splice(j + 1, 0, cur);
                break;
            }
            if (j === 0) {
                res.unshift(res[j]);
            }
        }
    }
    return res;
}
var arr = [3, 1, 5, 9, 4, 8, 7, 10, 2, 6];
insertSort(arr); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

var reverseWords = function (str) {
        if (!str) return;
        let left = 0;
        let right = str.length - 1;
        let queue = [];
        let word = "";
        // 去除字符串两端的空格
        while (str.charAt(left) === " ") left++;
        while (str.charAt(right) === " ") right--;
        // 逐个读取字符串中的每个单词，依次放入双端队列的队头
        while (left <= right) {
          let char = str.charAt(left);
          if (char === " " && word) {
            queue.unshift(word);
            word = "";
          } else if (char !== " ") {
            word += char;
          }
          left++;
        }
        queue.unshift(word);
        return queue.join(" ");
      };

      // 测试结果：
      reverseWords("  hello world!  "); // "world! hello"
      reverseWords("a good   example"); // "example good a"

var str = "abcabcabcbbccccc";

function findMaxChar(str) {
  var num = 0;
  var char = "";

  // 使其按照一定的次序排列
  str = str.split("").sort().join("");
  // "aaabbbbbcccccccc"

  // 定义正则表达式
  var re = /(\w)\1+/g;
  str.replace(re, ($0, $1) => {
    if (num < $0.length) {
      num = $0.length;
      char = $1;
    }
  });
  console.log(`字符最多的是${char}，出现了${num}次`); // 字符最多的是c，出现了8次
  return {
    char,
    num,
  };
}

var isValidStr = function (str) {
  var map = {
    "{": "}",
    "[": "]",
    "(": ")",
  };
  var stack = [];
  for (let i = 0; i < str.length; i++) {
    if (map[str[i]]) {
      stack.push(str[i]);
    } else if (str[i] !== map[stack.pop()]) {
      return false;
    }
  }
  // 当遍历完成时，所有已匹配的字符都已匹配出栈，如果此时栈为空，则字符串有效，如果栈不为空，说明字符串中还有未匹配的字符，字符串无效
  return stack.length === 0;
};

// 测试结果：
isValidStr("{[()]}"); // true
isValidStr("{}()"); // true
isValidStr("{[)]}"); // false
isValidStr("([]}"); // false

function deleteRepeatChar(str) {
  var stack = [];
  for (let s of str) {
    var prev = stack.pop();
    if (s !== prev) {
      stack.push(prev);
      stack.push(s);
    }
  }
  return stack.join("");
}

// 测试结果：
var str = "abbaca";
deleteRepeatChar(str); // ca
str = "abccdddaacb";
deleteRepeatChar(str); // abdcb

/**
 * 洗牌算法：
 * 1. 生成一个0到arr.length的随机数
 * 2. 交换该随机数位置元素和数组的最后一个元素，并把改随机位置的元素放入结果数组中
 * 3. 生成一个0～arr.length-1的随机数
 * 4. 交换该随机数位置元素和数组的倒数第二个元素，并把该随位置的元素放入结果数组中
 * 以此类推，直至取完所需的n个元素
 */
function xipai(arr, size) {
  let result = [];
  for (let i = 0; i < size; i++) {
    let index = Math.floor(Math.random() * (arr.length - i));
    result.push(arr[index]);
    [arr[index], arr[arr.length - i - 1]] = [
      arr[arr.length - i - 1],
      arr[index],
    ];
  }
  return result;
}