2020-06-28【排序】

export default class SortUtil {
    /**
     * 冒泡排序: 稳定排序  
     * @param Array
     * @returns  orderly Array 
     */
    bubbleSort(arr: Array<number>) {
        let temp: number;
        let tag = true
        for (let j = 0; tag === true; j++) {
            tag = false;
            for (let i = 0; i < arr.length; i++) {
                if (arr[i] > arr[i + 1]) {
                    temp = arr[i]
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    tag = true;
                }
            }
        }
        return arr;
    }

    /**
     *  选择排序: 不稳定排序  
     *  @param Array
     *  @returns orderly Array
     */
    selectionSort(arr: Array<number>) {
        let temp: number;

        for (let i = 0; i < arr.length; i++) {
            for (let j = i + 1; j <= arr.length; j++) {
                if (arr[i] > arr[j]) {
                    temp = arr[i];
                    arr[i] = arr[j]
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
    /**
     * 插值排序: 稳定排序  可以对数组直接排序, 也可以将一组无序数组插入另一组有序数组中  
     * @param arr  
     * @param sortedArray  待排序数组,填就排序并插入arr数组,可选参数
     * @returns  orderly Array 
     */
    insertionSort(arr: number[], sortedArray?: number[]) {
        if (sortedArray) {
            for (let i = 0; i < sortedArray.length; i++) {

                for (let j = arr.length - 1; j >= 0; j--) {
                    if (sortedArray[i] >= arr[j]) {
                        arr.splice(j + 1, 0, sortedArray[i]);
                        break;
                    } else if (sortedArray[i] < arr[0]) {
                        arr.unshift(sortedArray[i])
                        break
                    }
                }
            }
            return arr;
        }

        let temp;
        for (let i = 0; i < arr.length - 1; i++) {

            for (let j = i + 1; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                } else {
                    break
                }
            }
        }
        return arr;
    }

    /**
     * 快速排序: 不稳定 效率较高  
     * @param arr, 
     * @begin 第一个元素下标
     * @end  最后一个元素下标
     * @returns  orderly Array 
     */
    quickSort(arr: number[], begin: number, end: number) {
        if (end <= begin) {
            return arr;
        }
        let i = begin;
        let j = end;
        let key = arr[begin]
        while (true) {
            while (true) {
                if (i == j)
                    break;
                if (arr[j] < key) {
                    let temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                    break;
                }
                j--;
            }
            while (true) {
                if (i == j) {
                    break;
                }
                if (arr[i] > key) {
                    let temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    break;
                }
                i++;
            }
            if (i == j)
                break;
        }
        if (end - j > 1) {
            arr = this.quickSort(arr, j + 1, end);
        }
        if (i - begin > 1) {
            arr = this.quickSort(arr, begin, i)
        }

        return arr;
    }

    /**
     * 希尔排序: 插入排序的升级版,不稳定,适合中等数组排序
     * @param arr
     * @returns orderly Array
     */
    shellSort(arr: number[]) {
        let len = arr.length;
        for (let fraction = Math.floor(len / 2); fraction > 0; fraction = Math.floor(fraction / 2)) {
            for (let i = fraction; i < len; i++) {
                for (let j = i - fraction; j >= 0 && arr[j] > arr[fraction + j]; j -= fraction) {
                    let temp = arr[j];
                    arr[j] = arr[fraction + j];
                    arr[fraction + j] = temp;
                }
            }
        }
        return arr;
    }

    /**
     * 基数排序:不稳定 适用于数组中最大值和最小值差值较小的数组排序
     * @param arr 
     * @param maxDigit  数组中最大元素的位数(最大元素为111就是3,1111就是4)
     * @returns new orderly Array
     */
    radixSort(arr: number[], maxDigit: number) {
        let counter = [];
        let mod = 10;
        let dev = 1;
        for (let i = 0; i < maxDigit; i++ , dev *= 10, mod *= 10) {
            for (let j = 0; j < arr.length; j++) {
                let bucket = parseInt(((arr[j] % mod) / dev).toString());
                if (counter[bucket] == null) {
                    counter[bucket] = [];
                }
                counter[bucket].push(arr[j]);
            }
            let pos = 0;
            for (let j = 0; j < counter.length; j++) {
                let value = null;
                if (counter[j] != null) {
                    while ((value = counter[j].shift()) != null) {
                        arr[pos++] = value;
                    }
                }
            }
        }
        return arr;
    }

    /**
     * 归并排序: 稳定排序,效率较高
     * @param arr
     */
    mergeSort(arr: number[]) {
        let len = arr.length;
        if (len < 2) {
            return arr;
        }
        let middle = Math.floor(len / 2),
            left = arr.slice(0, middle),
            right = arr.slice(middle);
        return this.merge(this.mergeSort(left), this.mergeSort(right));
    }

    merge(left: number[], right: number[]) {
        let result = [];
        while (left.length && right.length) {
            if (left[0] <= right[0]) {
                result.push(left.shift());
            } else {
                result.push(right.shift());
            }
        }
        while (left.length)
            result.push(left.shift());

        while (right.length)
            result.push(right.shift());
        return result;
    }

}