用typescript实现排序-递增

var arr= [1,3,5,9,2,7,4,6,8]
arr.sort()  --默认是从小到大排序

// 冒泡排序 bubbleSort
function sortFun(arr:Array<number>):Array<number>{
	for(let i=0;i<arr.length;i++){
		for(let j=0;j<arr.length - i;j++){
			let temp
			if (arr[j] < arr[j+1]){
				temp = arr[j]
				arr[j] = arr[j+1]
				arr[j+1] = temp
			}
		}
	}
	return arr
}

// 快速排序，quickSort
function quickSort(arr: Array<number>): Array<number> {
    let final: Array<number> = new Array(...arr);

    function tureQuickSort(arr: Array<number>, left: number, right: number): Array<number> {
        if (left >= right) {
            return;
        }
        let i: number = left, j: number = right;
        let mark: number = arr[i];
        // 用mark作为中间值，将数组左右对半分
        while (i < j) {
            // 寻找右边比mark更小的
            while (i < j && arr[j] >= mark) {
                j--;
            }
            arr[i] = arr[j];
            // 寻找左边比mark更大的
            while (i < j && arr[i] <= mark) {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = mark;

        // 递归分左右两个子数组
        tureQuickSort(arr, left, i - 1);
        tureQuickSort(arr, i + 1, right);
    }

    tureQuickSort(final, 0, final.length - 1);

    return final;
}

插入排序是维护一个长度为i的有序序列，每次i自增1，为下标为i的数向前找插入位置。
// 插入排序 insertSort
function insertSort(arr: Array<number>): Array<number> {
    let final: Array<number> = new Array(...arr);

    for (let i = 1; i < final.length; i++) {
        let mark: number = final[i];
        let j: number;
        // 寻找插入位置
        for (j = i - 1; j >= 0; j--) {
            if (final[j] < mark) {
                // 插入位置找到
                break;
            } else {
                final[j + 1] = final[j];
            }
        }
        // 进行插入操作
        final[j + 1] = mark;
    }

    return final;
}