class RandomNumArr {
    constructor(min, max,length) {
        this.min = min;
        this.max = max;
        this.length = length;
    }

    // 获取随机数字
    getRandomNum(min, max) {
        let range = max - min + 1;
        return Math.floor(Math.random() * range + min);
    }
    // 获取随机数组
    getRandomArr() {
        let [min, max,length] = [this.min, this.max, this.length];
        if (min > max) [min, max] = [max, min];
        let arr = new Array(length);

        for (let i = 0; i < length; i++) {
            arr[i] = this.getRandomNum(min, max);
        }

        return arr;
    }
}

class Sort {
    constructor(arr) {
        if (this.checkType(arr) !== 'Array') return;
        this.arr = arr;
    }
    // 数据类型检测
    checkType(data) {
        let type = Object.prototype.toString.call(data);    // 获取数据类型 '[object Array]'
        type = type.match(/\s\w+/g)[0].trim();  // 取出 'Array'
        return type;
    }
    
    // 冒泡排序
    bubbleSort() {
        let arr = this.arr;
        let len = arr.length;
        let flag = 1;   // 标志是否还要继续循环

        for (let i = 0; i < len - 1 && flag; i++) { // 进行len-1趟排序
            flag = 0;
            for (let j = 0; j < len - i - 1; j++) { // 在len-i-1个元素中找到最大的，将其放置最后
                if (arr[j] > arr[j + 1]) {
                    [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                    flag = 1;
                }
            }
        }

        return arr;
    }

    // 选择
    selectSort() {
        let arr = this.arr;
        let len = arr.length;
        let minIndex;

        for (let i = 0; i < len - 1; i++) { // len-1趟排序
            minIndex = i;   // 最小值索引
            for (let j = i + 1; j < len; j++) { // 在len-i-1个元素中找到最小索引
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {    // 最小索引不是当前索引则交换
                [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
            }
        }

        return arr;
    }

    // 插入
    insertSort(gap = 1) {
        let arr = this.arr;
        let len = arr.length;
        let temp, j;
        
        // 步长为1 -> 直接插入排序
        /*
        for (let i = 1; i < len; i++) { // len-1趟排序
            temp = arr[i];  // 存储当前待排序数据
            j = i - 1;  
            while (j >= 0 && temp < arr[j]) {   // 在已排序数列中从后向前扫描，寻找正确位置插入
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
        */

        // 根据步长来插入
        for (let i = gap; i < len; i++) {   
            temp = arr[i];  // 存储当前待排序数据
            j = i - gap;    
            while (j >= 0 && temp < arr[j]) {   // 在已排序数列中从后向前扫描，寻找正确位置插入
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = temp;
        }

        return arr;
    }

    // 希尔
    shellSort() {
        let arr = this.arr;
        let len = arr.length;
        let gap = 1;
        let temp, j;

        while (gap < len / 3) {
            gap = gap * 3 + 1;  // 动态确定间隔
        }

        for (; gap > 0; gap = Math.floor((gap - 1) / 3)) {  // 确定步长
            // 直接插入排序
            this.insertSort(gap);
            /*
            for (let i = gap; i < len; i++) {   // 依照间隔比较数据
                temp = arr[i];
                for (j = i - gap; j > 0 && temp < arr[j]; j -= gap) {
                    arr[j + gap] = arr[j];
                }
                arr[j + gap] = temp;
            }
            */
        }

        return arr;
        
    }

    // 快排
    quickSort(arr = this.arr) {
        if (arr.length <= 1) return arr;
        
        let pivotIndex = Math.floor(arr.length / 2);    // 基准值索引
        let pivot = arr.splice(pivotIndex, 1)[0];   // 基准值
        let left = [];
        let right = [];

        for (let i = 0; i < arr.length; i++) {  // 遍历数组，将小于基准值的放在left，大于则right
            if (arr[i] < pivot) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        
        return this.quickSort(left).concat(pivot, this.quickSort(right));
    }

    // 归并
    mergeSort(arr = this.arr) {
        let len = arr.length;
        if (len <= 1) return arr;
        let middle = Math.floor(len / 2);
        let left = arr.slice(0, middle);
        let right = arr.slice(middle);

        return this.merge(this.mergeSort(left), this.mergeSort(right));
    }
    merge(leftArr, rightArr) {
        let result = [];
        while (leftArr.length > 0 && rightArr.length > 0) {
            if (leftArr[0] < rightArr[0]) {
                result.push(leftArr.shift());
            } else {
                result.push(rightArr.shift());
            }
        }

        return result.concat(leftArr).concat(rightArr);
    }
}

let arr = new RandomNumArr(0, 100, 15).getRandomArr();
let sort = new Sort(arr);
console.log('冒泡', sort.bubbleSort());
console.log('选择', sort.selectSort());
console.log('插入', sort.insertSort());
console.log('希尔', sort.shellSort());
console.log('快排', sort.quickSort());
console.log('归并', sort.mergeSort());