912. Sort an Array

2020-08-25 本文已影响0人 jluemmmm

排序方法	平均时间复杂度	最坏	最好	空间复杂度	稳定性
直接插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定
直接选择排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	不稳定
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(n)$	稳定
希尔排序	$O(nlog_2n)$	$O(n^2)$	$O(n)$	$O(1)$	不稳定
快速排序	$O(nlog_2n)$	$O(n^2)$	$O(nlog_2n)$	$O(nlog_2n)$	不稳定
归并排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(n)$	稳定
堆排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(1)$	不稳定

希尔排序

插入排序的一种，又称缩小增量排序，按下标增量进行分组，对每组使用直接插入算法排序，随着增量逐渐减少，每组包含的关键字越来越多，减至1时，整个文件被分为1组算法终止

Runtime: 6396 ms, faster than 5.03%
Memory Usage: 40.1 MB, less than 98.23%

var sortArray = function(nums) {
    let len = nums.length
    let step = Math.floor(len / 2)
    while(step > 0) {
        let sublen = Math.floor(len / step)
        for(let i = 0; i < sublen; i++) {
            for(let j = i + step; j < len; j = j+step) {
                if(nums[i] > nums[j]) [nums[j], nums[i]] = [nums[i], nums[j]]
            }
        }
        step = Math.floor(step / 2)
    }
    return nums
};

图解希尔排序

归并排序

采用分治策略，将问题分解成一些小的问题递归求解，治阶段将分阶段得到的各答案组合在一起

Runtime: 244 ms, faster than 30.33%
Memory Usage: 49.9 MB, less than 21.87%

var sortArray = function(nums) {
    let len = nums.length
    if (len < 2) return nums
    let mid = Math.floor(len / 2)
    return merge(sortArray(nums.slice(0, mid)), sortArray(nums.slice(mid)))
};

let merge = function(left, right) {
    let res = []
    while(left.length && right.length) {
        if (left[0] > right[0]) {
            res.push(right.shift())
        } else {
            res.push(left.shift())
        }
    }
    return res.concat(left, right)
}

直接选择排序

在所有记录中选择关键字最小的进行记录，于第一个记录进行位置交换，在其余的记录中选择关键值次小的记录与第二个记录进行交换

Runtime: 1104 ms, faster than 17.96%
Memory Usage: 42.2 MB, less than 58.98%

var sortArray = function(nums) {
    let len = nums.length
    for(let i = 0; i < len; i++) {
        let min = i
        for(let j = i + 1; j < len; j++) {
            if(nums[j] < nums[min]) min = j
        }
        [nums[min], nums[i]] = [nums[i], nums[min]]
    }
    return nums
};

堆排序

堆可以看作是一棵树的数组对象，满足
- 堆中的某个节点总是不大于或不小于其父节点的值
- 堆总是一颗完全二叉树

根节点是所有节点中关键字最大的，称为大根堆，一般升序排序使用大根堆，降序排序使用小根堆。是因为，升序排序是采用大根堆把最大的元素交换至根节点，然后沉到底部。

JS实现堆排序

Runtime: 164 ms, faster than 40.30%
Memory Usage: 41.7 MB, less than 77.40%

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    let len = nums.length
    if (len < 2) return nums
    let mid = Math.floor(len / 2 - 1)
    //从第一个非叶子节点开始进行推排序
    for(let i = mid; i >= 0; i--) {
        heap_sort(nums, i, len)
    }
    //排序一轮之后进行交换，对剩下的部分进行堆排序
    for(let j = len - 1; j >= 0; j--) {
        [nums[j], nums[0]] = [nums[0], nums[j]]
        heap_sort(nums, 0, j)
    }
    return nums
};

var heap_sort = function(nums, index, boundary) {
    let max = index
    let left = index * 2 + 1
    let right = index * 2 + 2
    
    if(left < boundary && nums[left] > nums[max]) max = left
    if(right < boundary && nums[right] > nums[max]) max = right
    
    if(max > index) {
        [nums[index], nums[max]] = [nums[max], nums[index]]
        heap_sort(nums, max, boundary)
    }
}

快速排序

https://leetcode.com/problems/sort-an-array/discuss/279017/JS-BubbleSort-SelectionSort-insertionSort-MergeSort-and-QuickSort

Runtime: 192 ms, faster than 33.80%
Memory Usage: 57.5 MB, less than 5.07%

var sortArray = function(nums) {
    if(nums.length < 2) return nums
    let pilot = nums.pop()
    let less = sortArray(nums.filter(item => item < pilot))
    let more = sortArray(nums.filter(item => item >= pilot))
    return less.concat([pilot], more)
};

冒泡排序

Runtime: 6284 ms, faster than 5.08%
Memory Usage: 41.2 MB, less than 90.58%

var sortArray = function(nums) {
    let len = nums.length
    for(let i = 0; i < len; i++) {
        for(j = 0; j < len - i - 1; j++) {
            if(nums[j] > nums[j + 1]) [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]]
        }
    }
    return nums
};

直接插入排序

对第一次循环的i+1开始进行倒循环

Runtime: 7352 ms, faster than 5.08%
Memory Usage: 41 MB, less than 93.59%

var sortArray = function(nums) {
    let len = nums.length
    for(let i = 0; i < len; i++) {
        for(let j = i + 1; j > 0; j--) {
            if(nums[j] < nums[j - 1]) [nums[j - 1], nums[j]] = [nums[j], nums[j - 1]]
        }
    }
    return nums
};

sort排序

Runtime: 172 ms, faster than 37.66%
Memory Usage: 42.4 MB, less than 55.36%

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    nums.sort(function(a,b){
      if(a < b) return -1
      else return 1
    })
    return nums
};

原址交换的快排

Runtime: 116 ms, faster than 67.96%
Memory Usage: 43.3 MB, less than 90.66%

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    quickSort(nums, 0, nums.length - 1)
    return nums
};

var quickSort = function(nums, i, j) {
    if(j - i < 1) return nums
    let flag = nums[i]
    let start = i + 1
    let end = j
    while(start <= end) {
        if(nums[start] <= flag) {
            start++
        } else {
            swap(nums, start, end)
            end--
        }
    }
    swap(nums, i, start - 1)
    if (start - 1 <= j)quickSort(nums, i, start - 2)
    quickSort(nums, start, j)
}


var swap = function(nums, m, n) {
    let temp = nums[m]
    nums[m] = nums[n]
    nums[n] = temp
}