// 随机生成一个乱序数组
let arr = Array.from(new Array(10), () => ~~(Math.random() * 100))

console.log('Source array is [ %s ]\n', arr.join(', '))

// 选择排序
function selectionSort(arr) {
    const len = arr.length
    let minIndex // 最小值的 index
    for (let i = 0; i < len - 1; i++) {
        minIndex = i;
        for (let j = i + 1; j < len; j++) {
            // 遍历未排序元素，选出最小值 index
            if (arr[minIndex] > arr[j]) minIndex = j;
        }
        // 在确定最小值坐标之后，再交换元素位置，把最小值放到未排序元素最前面，提高效率
        if (minIndex !== i) {
            [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]]
        }
        console.log('Step %d: [ %s ] (%s)', i + 1, arr.join(', '), minIndex !== i ? 'Swapped' : 'No swap')
    }
    console.log('\nSorted array is [ %s ]', arr.join(', '))
}

selectionSort(arr)

// config/plugin.js
exports.alinode = {
  enable: true,
  package: 'egg-alinode'
};

// config/config.default.js
exports.alinode = {
  enable: true,
  server: 'wss://agentserver.node.aliyun.com:8080',
  appid: '***',  // Node.js 性能平台给您的项目生成的 appid
  secret: '***',  // Node.js 性能平台给您的项目生成的 secret
  logdir: '***',  // Node.js 性能平台日志输出地址绝对路径，与 NODE_LOG_DIR 保持一致。如：/tmp/，也可以不写
  error_log: [
    // '您的应用在业务层面产生的异常日志的路径，数组，可选，可配置多个',
    // '例如：/root/.logs/error.#YYYY#-#MM#-#DD#.log',
    // '不更改 Egg 默认日志输出路径可不配置本项目',
  ],
  agentidMode:'IP',  // 可选，如果设置，则在实例ID中添加部分IP信息，用于多个实例 hostname 相同的场景（以容器为主）
};

// 随机生成一个乱序数组
let arr = Array.from(new Array(10), () => ~~(Math.random() * 100))

console.log('Source array is [ %s ]\n', arr.join(', '))

// 希尔排序
function shellSort(arr) {
    const len = arr.length
    let step = 1
    let gap = len >> 1
    let temp
    for (; gap > 0; gap >>= 1) {
        console.log('Gap is %d:', gap)
        let log = ''
        arr.forEach((v, i) => {
            log += `${v}\t${(i + 1) % gap === 0 ? '\n' : ''}`
        })
        console.log('Initial: \n%s', log)

        for (let i = gap, j; i < len; i++) {
            temp = arr[i]
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
                arr[j + gap] = arr[j]
            }
            arr[j + gap] = temp

            log = ''
            arr.forEach((v, i) => {
                log += `${v}\t${(i + 1) % gap === 0 ? '\n' : ''}`
            })
            console.log('Step %d: \n%s', step++, log)
        }
    }
    console.log('\nSorted array is [ %s ]', arr.join(', '))
}

shellSort(arr)

// 随机生成一个乱序数组
let arr = Array.from(new Array(10), () => ~~(Math.random() * 100))

console.log('Source array is [ %s ]\n', arr.join(', '))

// 鸡尾酒排序
function cocktailSort(arr) {
    const len = arr.length
    let swapped // 是否有过交换，一旦没有任何元素交换，排序结束
    let step = 1
    let i, left = 0, right = len - 1;
    while (left < right) {
        // 先从左扫到右，把最大的放到最右边
        for (i = left; i < right; i++) {
            swapped = false
            if (arr[i] > arr[i + 1]) {
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]
                swapped = true
            }
        }
        console.log('Step %d: [ %s ] ( left -> right )', step++, arr.join(', '))
        right--;
        // 再从右扫到左，把最小的放到最左边
        for (i = right; i > left; i--) {
            if (arr[i - 1] > arr[i]) {
                [arr[i], arr[i - 1]] = [arr[i - 1], arr[i]]
            }
        }
        left++;
        console.log('Step %d: [ %s ] ( right -> left )', step++, arr.join(', '))
        if (!swapped) break
    }
    console.log('\nSorted array is [ %s ]', arr.join(', '))
}

cocktailSort(arr)

let sumBubble = 0
let sumCocktail = 0

for (let i = 0; i < 10000; i++) {
    arr = Array.from(new Array(10), () => ~~(Math.random() * 100))
    sumBubble += bubbleSort(arr)
    sumCocktail += cocktailSort(arr)
}

console.log('Bubble sort average steps: %s', sumBubble / 10000)
console.log('Cocktail sort average steps: %s', sumCocktail / 10000)

// 随机生成一个乱序数组
let arr = Array.from(new Array(10), () => ~~(Math.random() * 100))

console.log('Source array is [ %s ]\n', arr.join(', '))

// 冒泡排序
function bubbleSort(arr) {
    const len = arr.length
    let swapped // 是否有过交换，一旦没有任何元素交换，排序结束
    let step = 1
    for (let i = 0; i < len; i++) {
        swapped = false
        // 注意这里是len - i，每一轮都会把最大的元素放在最后，所以 len - i 后面的元素不用再比较
        for (let j = 0; j < len - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换元素位置，这里是es6的方式
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
                swapped = true
            }
        }
        console.log('Step %d: [ %s ]', step++, arr.join(', '))
        if (!swapped) break
    }
    console.log('\nSorted array is [ %s ]', arr.join(', '))
}

bubbleSort(arr)

// 随机生成一个乱序数组
let arr = Array.from(new Array(10), () => ~~(Math.random() * 100))

console.log('Source array is [ %s ]\n', arr.join(', '))

// 插入排序
function insertionSort(arr) {
    const len = arr.length
    let step = 1;
    // i 为未排序序列 index，j 为已排序序列 index，起始 arr[0] 作为已排序序列，所以 i 从 1 开始
    for (let i = 1; i < len; i++) {
        // 选取 arr[i] 作为待排序元素，从右到左依次与左侧的已排序序列比较
        let insertItem = arr[i]
        for (let j = i - 1; j >= -1; j--) {
            // j === -1 代表已经比较到第一个元素，都没有发现更小的，则需要插入到最前端
            // 这里采用直接插入的方式，也可以选择依次交换的方式
            if (j === -1 || arr[j] < insertItem) {
                if (j + 1 !== i) {
                    // 把元素从 i 插入到 j + 1 位置
                    arr.splice(j + 1, 0, insertItem); // 插入元素
                    arr.splice(i + 1, 1); // 删除元素
                }
                console.log('Step %d: [ %s ] (insert %s from %d to %d, %s)', step++, arr.join(', '), insertItem, i, j + 1, j + 1 !== i ? 'Moved' : 'No move')
                break;
            }
        }
    }
    console.log('\nSorted array is [ %s ]', arr.join(', '))
}

insertionSort(arr)