排序

参考:

• 十大排序算法

快速排序

选择一个目标值，比目标值小的放左边，比目标值大的放右边，目标值的位置已排好，将左右两侧再进行快排，利用分治思想实现排序

快排流程：

• 随机选择数组中的一个标志数 A，以这个数为基准
• 其他数字跟这个数进行比较，比这个数小的放在其左边，大的放到其右边
• 经过一次循环之后，A 左边为小于 A 的，右边为大于 A 的
• 分别对左右数组进行递归，重复上面过程，直至数组已排序为止（剩余1个元素）

function quickSort(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++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    // 递归
    return quickSort(left).concat([pivot], quickSort(right));
}

选择排序

每次排序取一个最大或最小的数字放到前面的有序序列中。

for (var i = 0; i < num; ++i){
    var min = i;
    for (var j = i + 1; j < num; ++j){
        if (arr[min] > arr[j]){
            min = j;
        }
    }
    var temp = arr[i];
    arr[i] = arr[min];
    arr[min] = temp;
}

冒泡排序

循环数组，比较当前元素和下一个元素，如果当前元素比下一个元素大，向上冒泡。下一次循环继续上面的操作，不循环已经排序好的数。

for (var i = 0; i < num; ++i){
    for (var j = 0; j < num-i; ++j){
        if (arr[j+1] < arr[j]){
            var temp = arr[j+1];
            arr[j+1] = arr[j];
            arr[j] = temp;
        }
    }
}

插入排序

把未排序子列的第一个数插入到已排序子列的正确位置

将左侧序列看成一个有序序列，每次将一个数字插入该有序序列。插入时，从有序序列最右侧开始比较，若比较的数较大，后移一位。

for (let i = 1, len = arr.length; i < len; ++i){
    let  j = i,
        key = arr[i];
    while (--j > -1) {
        if (arr[j] > key) {
            arr[j + 1] = arr[j];
        } else {
            break;
        }
    }
    arr[j + 1] = key;
}

归并排序

将大序列二分成小序列，将小序列排序后再将排序后的小序列归并成大序列。利用归并思想实现排序

堆排序

创建一个大顶堆，大顶堆的堆顶一定是最大的元素。交换第一个元素和最后一个元素，让剩余的元素继续调整为大顶堆。从后往前以此和第一个元素交换并重新构建，排序完成。