排序算法.md

排序算法

快速排序

var quickSort = function (arrays, start, end) {
    if (start < end) {
        // pivot 是分割点，pivot左边的比nums[pivot]小，右边的比nums[pivot]大
        let pivot = partition(arrays, start, end);
        quickSort(arrays, start, pivot - 1);
        quickSort(arrays, pivot + 1, end);
    }
    return arrays;
}

var partition = function (nums, start, end) {
    let target = nums[end];
    let i = start;
    // 将小于target移到数组前面
    for (let j = start; j < end; j++) {
        if (nums[j] < target) {
            [nums[i], nums[j]] = [nums[j], nums[i]]
            i++;
        }
    }
    // 把中间的值换为用于比较的基准值
    [nums[i], nums[end]] = [nums[end], nums[i]]
    return i;
}

let arrays = [72, 6, 57, 88, 60, 42, 83, 73, 48, 85]
console.log(quickSort(arrays, 0, arrays.length - 1))

下面这种分治的算法较好理解，挖坑填数。

var partition = function (nums, left, right) {
    let pivot = nums[left];
    while (left < right) {
        while (left < right && nums[right] > pivot) { //从右向左找到比基准小的
            right--;
        }
        if (left < right) {
            nums[left] = nums[right]; //覆盖基准的值
            left++; //左指针前进一位
        }
        while (left < right && nums[left] < pivot) {
            left++;
        }
        if (left < right) {
            nums[right] = nums[left];
            right--;
        }
    }
    nums[left] = pivot; //left === right
    return left;
}

归并排序

var mergeSort = function (nums, start, end) {
    if (start < end) {
        let mid = (start + end) >> 1;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid + 1, end);
        nums = merge(nums, start, mid, end);
    }
    return nums;
}

var merge = function (nums, left, mid, right) {
    let arr = [];
    let i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (nums[i] < nums[j]) {
            arr.push(nums[i]);
            i++;
        } else {
            arr.push(nums[j]);
            j++;
        }
    }
    while (i <= mid) {
        arr.push(nums[i++]);
    }
    while (j <= right) {
        arr.push(nums[j++]);
    }
    return arr;
}

let nums = [2, 3, 5, 9, 4, 6, 8];
console.log(mergeSort(nums,0,nums.length-1))

堆排序

用数组表示的完美二叉树 complete binary tree

动画展示

var move = function (nums, low, high) {
    let i = low, j = 2 * i + 1;
    let temp = nums[i];
    while (j <= high) {
        if (j < high && nums[j] < nums[j + 1]) {
            j++;
        }
        if (temp < nums[j]) {
            nums[i] = nums[j];
            i = j;
            j = 2 * i + 1;
        } else {
            break;
        }
    }
    nums[i] = temp;
}

var heapSort = function (nums) {
    let i, temp;
    let n = nums.length - 1;
    for (i = n >> 1; i >= 0; i--) {
        move(nums, i, n);
    }
    for (i = n; i >= 1; i--) {
        temp = nums[0];
        nums[0] = nums[i];
        nums[i] = temp;
        move(nums, 0, i - 1);
    }
    return nums;
}

let arr = [2,4,1,5,8,6,7,9]
console.log(heapSort(arr))

参考

十大经典排序

二叉堆

练习

• 手写快排、归并、堆排序