Skip to content

快速排序、堆排序、二路归并排序、插入排序 #163

Open
@TieMuZhen

Description

@TieMuZhen

image

快速排序

LeetCode 912

"快速排序"的思想很简单,整个排序过程只需要三步:

(1)在数据集之中,选择一个元素作为"基准"。
(2)所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边。
(3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function quickSort(nums, left, right){
    if(left >= right) return;
    let lp = left, 
        rp = right,
        // Math.round() 四舍五入 Math.random() 随机生成[0, 1)的数字
        flagIndex = Math.round(left + Math.random() * (right - left)),
        stand = nums[flagIndex];
    [nums[left], nums[flagIndex]] = [nums[flagIndex], nums[left]];
    while(lp < rp){
        while(nums[rp] > stand && lp < rp){
            rp--;
        }
        if(lp < rp){
            nums[lp] = nums[rp];
            lp++;
        }
        while(nums[lp] < stand && lp < rp){
            lp++;
        }
        if(lp < rp){
            nums[rp] = nums[lp];
            rp--;
        }
    }
    nums[lp] = stand;
    quickSort(nums, left, lp - 1);
    quickSort(nums, lp + 1, right);
}
var sortArray = function(nums) {
    quickSort(nums, 0, nums.length - 1);
    return nums;
};

二路归并排序

LeetCode 912

参考自:作者视频讲的特别通俗易懂

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function merge(nums, tempArr, l, r){
    let mid = l + Math.floor((r - l) / 2);
    let lp = l; // 指向左半部分数组第一个元素的指针
    let rp = mid + 1; // 指向右半部分数组第一个元素的指针
    let p = l; // 复制时用的指针
    while(lp <= mid && rp <= r){
        if(nums[lp] < nums[rp]){
            tempArr[p] = nums[lp];
            lp++;
        }else{
            tempArr[p] = nums[rp];
            rp++;
        }
        p++;
    }
    while(lp <= mid){
        tempArr[p] = nums[lp];
        p++;
        lp++;
    }
    while(rp <= r){
        tempArr[p] = nums[rp];
        p++;
        rp++;
    }
    for(let i = l; i <= r; i++){
        nums[i] = tempArr[i];
    }
}

function twoWaySort(nums, tempArr, l, r){
    if(l == r) return;
    let mid = l + Math.floor((r - l) / 2); //防止大数溢出写法
    twoWaySort(nums, tempArr, l, mid);
    twoWaySort(nums, tempArr, mid + 1, r);
    merge(nums, tempArr, l, r);
}

var sortArray = function(nums) {
    let tempArr = new Array(nums.length);
    twoWaySort(nums, tempArr, 0, nums.length - 1);
    return nums;
};

堆排序(必须是完全二叉树才能用堆排序)

LeetCode 912

参考自:作者视频讲的特别通俗易懂

image
image
image

// 堆排序必须是完全二叉树才可以用
function heapify(nums, n, index){
    let leftChild = index * 2 + 1;
    let rightChild = index * 2 + 2;
    let max = index;
    if(leftChild < n && nums[leftChild] > nums[max]){
        max = leftChild;
    }
    if(rightChild < n && nums[rightChild] > nums[max]){
        max = rightChild;
    }
    if(max != index){
        [nums[index], nums[max]] = [nums[max], nums[index]];
        heapify(nums, n, max);
    }
}

function buildHeap(nums, n){
    let lastNodeIndex = n - 1;
    let parentIndex = Math.floor((lastNodeIndex - 1) / 2);
    for(let i = parentIndex; i >= 0; i--){
        heapify(nums, n, i);
    }
}

function heapSort(nums, n){
    buildHeap(nums, n);
    for(let index = n - 1; index >= 0; index--){
        [nums[0], nums[index]] = [nums[index], nums[0]];
        buildHeap(nums, index);
    }
}

var sortArray = function(nums) {
    let n = nums.length;
    heapSort(nums, n);
    return nums;
};

插入排序

LeetCode 912

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function insetSort(nums){
    for(let i = 1; i < nums.length; i++){
        for(let j = i; j > 0; j--){
            if(nums[j] < nums[j - 1]){
                [nums[j], nums[j - 1]] = [nums[j - 1], nums[j]];
            }
        }
    }
}
var sortArray = function(nums) {
    insetSort(nums);
    return nums;
};

Metadata

Metadata

Assignees

No one assigned

    Labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions