JavaScript算法-排序算法

var dataAry = [5, 4, 3, 7, 1, 2, 8, 6, 9]; // 测试数组

/**
 *【工具方法】交换数组中两个值
 * @param ary 数组
 * @param i 下标i
 * @param j 下标j
 */
function swap(ary, i, j) {
    var temp = ary[i];
    ary[i] = ary[j];
    ary[j] = temp;
}

function bubbleSort(dataAry) {
	var len = dataAry.length;
	for(var i = 0; i < len - 1; i++) {
        for(var j = 0; j < len - i - 1; j++) {
            if(dataAry[j] > dataAry[j+1]) {
                swap(dataAry, j, j+1);
            }
        }
    }
    return dataAry;
}
// 测试
console.log(bubbleSort(dataAry)); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

function bubbleSort(dataAry) {
	var len = dataAry.length;
 	for(var i = 0; i < len - 1; i++) {
         var isSorted = true;
         for(var j = 0; j < len - i - 1; j++) {
             if(dataAry[j] > dataAry[j+1]) {
                 swap(dataAry, j, j+1);
               	isSorted = false;
             }
         }
         if (isSorted) break;
     }
     return dataAry;
 }

function bubbleSort(dataAry) {
	var len = dataAry.length;
  	// 记录最后一次交换的位置
  	var lastExchangeIndex = 0
  	// 无序边界（每次比较截止位置）
  	var sortBorder = len - 1
	for(var i = 0; i < len - 1; i++) {
        var isSorted = true;
        for(var j = 0; j < sortBorder; j++) {
            if(dataAry[j] > dataAry[j+1]) {
                swap(dataAry, j, j+1);
              	isSorted = false;
              	// 更新最后一次交换元素的位置
              	lastExchangeIndex = j
            }
        }
    	sortBorder = lastExchangeIndex
        if (isSorted) break;
    }
    return dataAry;
}

function selectionSort(dataAry) {
    var len = dataAry.length;
    for(var i = 0; i < len - 1; i++) {
        for(var j = i + 1; j < len; j++) {
            if(dataAry[i] > dataAry[j]) {
                swap(dataAry, i , j);
            }
        }
    }
    return dataAry;
}
// 测试
console.log(selectionSort(dataAry)); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

function insertionSort(dataAry) {
    var temp, inner;
  	// 外循环(跳过第一个值，因为第一个直接放到最左侧)
    for(var outer = 1, len = dataAry.length; outer < len; outer++) {
        temp = dataAry[outer];
        inner = outer;
        // 内循环，比左侧值小就移动让位
      	while(inner > 0 && (dataAry[inner - 1] >= temp)) {
            dataAry[inner] = dataAry[inner - 1];
            inner--;
        }
        dataAry[inner] = temp;
    }
  	return dataAry
}
// 测试
console.log(insertionSort(dataAry)); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

/**
 * 希尔排序
 * @param dataAry 数据数组
 * @param gaps    间隔数组
 */
function shellSort(dataAry, gaps) {
    var temp, inner, currentGap;
    // 遍历间隔
    for(var g = 0, gLen = gaps.length; g < gLen; g++) {
        // 当前间隔
        currentGap = gaps[g];
        // 直接插入法外循环
        for(var outer = currentGap, len = dataAry.length; outer < len; outer++) {
           temp = dataAry[outer];
           inner = outer;
           // 直接插入法内循环（注意对比间隔值）
           while(inner >= currentGap && (dataAry[inner - currentGap] >= temp)) {
               dataAry[inner] = dataAry[inner - currentGap];
               inner = inner - currentGap;
           }
           dataAry[inner] = temp;
        }
    }
    return dataAry;
}
// 测试
console.log(shellSort(dataAry, [3, 2, 1])); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

function mergeSort(dataAry) {
    if(dataAry.length === 1) {
        return dataAry;
    }
    var mid = Math.floor(dataAry.length/2);
    var leftAry = dataAry.slice(0, mid);
    var rightAry = dataAry.slice(mid);
    return merge(mergeSort(leftAry), mergeSort(rightAry));
}
/**
 * 合并数组
 * @param dataAry
 */
function merge(leftAry, rightAry) {
    var result = [];
    while(leftAry.length > 0 && rightAry.length > 0) {
        if(leftAry[0] < rightAry[0]) {
            result.push(leftAry.shift());
        }else {
            result.push(rightAry.shift());
        }
    }
    return result.concat(leftAry).concat(rightAry);
}
// 测试
console.log(mergeSort(dataAry)); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

function mergeSort(dataAry) {
    if(dataAry.length < 2) {
        return dataAry;
    }
    var step = 1; // 控制子序列大小
    var left, right; // 左、右下标
    while(step < dataAry.length) {
        left = 0;
        right = step;

        while((right + step) <= dataAry.length) {
            mergeArrays(dataAry, left, left+step, right, right+step);
            left = right + step;
            right = left + step;
        }
        // 不能被分组的元素
        if(right < dataAry.length) {
            mergeArrays(dataAry, left, left+step, right, dataAry.length);
        }
        step = step * 2;
    }
    return dataAry;
}

/**
 * 合并数组<包含头，不包含尾>
 * @param ary
 * @param startLeft 
 * @param endLeft
 * @param startRight
 * @param endRight
 */
function mergeArrays(ary, startLeft, endLeft, startRight, endRight) {
    var leftAry = new Array(endLeft - startLeft + 1),
        rightAry = new Array(endRight - startRight + 1);

    var k = startLeft;
    for(var i = 0; i < (leftAry.length - 1); i++) {
        leftAry[i] = ary[k];
        k++;
    }
    leftAry[leftAry.length - 1] = Infinity; // 哨兵值

    k = startRight;
    for(var j = 0; j < (rightAry.length - 1); j++) {
        rightAry[j] = ary[k];
        k++;
    }
    rightAry[rightAry.length - 1] = Infinity; // 哨兵值

    // 对比左右元素大小
    var m = 0, n = 0;
    for(var k = startLeft; k < endRight; k++) {
        if(leftAry[m] <= rightAry[n]) {
            ary[k] = leftAry[m];
            m++;
        }else {
            ary[k] = rightAry[n];
            n++;
        }
    }
}
// 测试
console.log(quickSort(dataAry)); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

function quickSort(dataAry) {
    if(dataAry.length === 0) {
        return [];
    }
    var left = [], right = [];
    var pivot = dataAry[0];
    for(var i = 1; i < dataAry.length; i++) {
        dataAry[i] < pivot ? left.push(dataAry[i]) : right.push(dataAry[i]);
    }
    return quickSort(left).concat(pivot, quickSort(right));
}
// 测试
console.log(quickSort(dataAry)); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

function quickSort(arr, left, right) {
    if (left > right) return;
    var temp,
        i = left,
        j = right;
    // 设基准值
    var pivot = arr[left];
    while (i != j) {
        // 先从右侧开始(找到小于基值的第一个数据)
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        // 然后从左侧开始(找到大于基值的第一个数据)
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        // 交换数据上述两个元素，继续查找，直到i和j相遇
        if (i < j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
  	// 将基值与相遇数据进行交换<确保了基值位于元素中央位置>
    temp = arr[i];
    arr[i] = arr[left];
    arr[left] = temp;
  	// 基值左侧数组按上述方式递归执行
    quickSort(arr, left, i - 1);
 	// 基值右侧数组按上述方式递归执行
    quickSort(arr, i + 1, right);
    return arr;
}
// 测试
console.log(quickSort(dataAry, 0, dataAry.length - 1)); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

function countSort(dataAry) {
    // 获取最大数，并创建数组
    let maxNumber = Math.max.call(undefined, ...dataAry)
    let countArray = new Array(maxNumber+1).fill(0)
    // 填充统计数组
    for (let data of dataAry) {
        countArray[data]++
    }
    // 遍历统计结果数组
    let sortedArray = new Array(dataAry.length)
    let index = 0
    for (let i = 0, len = countArray.length;i < len; i++) {
        for (let j = 0; j < countArray[i]; j++) {
            sortedArray[index++] = i
        }
    }
    return sortedArray
}
/ 测试
console.log(countSort(dataAry)); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]