阅读 38

JavaScript数据结构与算法(排序算法)

比较排序算法一般有三个指标

  • 时间复杂度, 算法执行完成所需要的时间
  • 空间复杂度, 算法执行完成所需要的空间
  • 稳定性,当二个元素的值相同的时候,排序之后二个元素的前后位置是否发生改变

以下的排序都为升序

冒泡排序

冒泡排序是面试官最喜欢问新手程序员的.冒泡排序就像名字一样,冒泡排序第一次冒出最大的,第二次冒出第二大的,第三次冒出第三大的.....直到冒出倒数第二大的.

const array = [12, 2, 3, 10, 8, 8, 9, 21]
function BubbleSort(array){
    let len = array.length;
    if (len == 0 || len == 1) {
        return array;
    }
    for (let i = 0; i < len-1; i++) {
        for (let j = 0; j < len-1-i; j++) {  // 减i是因为第0到第i大已经冒出来了 不需要再比较了
            if (array[j] > array[j+1]) {
                [array[j], array[j+1]] = [array[j+1], array[j]];
            }
        }
    }
    return array
}
BubbleSort(array)  //[2, 3, 8, 8, 9, 10, 12, 21]
复制代码

时间复杂度为O(n^2),空间复杂度为O(1),稳定

仅仅面试考察,实际运用是不会用到的,因为冒泡排序是非常没效率的,因为不仅时间复杂度高而且有O(n^2)的交换,交换所耗的性能远大于比较

选择排序

选择排序是第一位找到最小的,第二位找到第二小的,第三位找到第三小的.....

const array = [12, 2, 3, 10, 8, 8, 9, 21]
function SelectionSort(array){
    let len = array.length;
    if (len == 0 || len == 1) {
        return array;
    }
    for (let i = 0; i < len-1; i++) {
        let min = i;
        for (let j = i+1; j < len-1-i; j++) {
            if (array[j] < array[min]) {
                min = j
            }
        }
        [array[i], array[min]] = [array[min], array[i]];
    }
    return array 
}
SelectionSort(array)  //[2, 3, 8, 8, 9, 10, 12, 21]

复制代码

时间复杂度为O(n^2),空间复杂度为O(1),稳定

仅仅面试考察,实际运用跟冒泡一样,也不会用到,因为效率也非常低. 但是比冒泡好点,因为元素如果再正确的位置上不会交换。

插入排序

就是,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入

const array = [12, 2, 3, 10, 8, 8, 9, 21]
function InsertionSort(array){
        let len = array.length;
        if (len == 0 || len == 1) {
            return array;
        }
        for (let i = 1; i < len; i++) {
            for (let j = 0; j < i; j++) {        // 查找的部分可以使用二分查找
                if (array[j] > array[i]) {
                    this.splice(j, 0, array[i]); // 插入进来
                    this.splice(i+1, 1);         // 删除已插入的元素 
                    break;
                }
            }
        }
        return array;
    }
InsertionSort(array)  //[2, 3, 8, 8, 9, 10, 12, 21]
复制代码

时间复杂度为O(n^2),空间复杂度为O(1),不稳定

效率也不高,通常也不会使用,但是如果数据接近线性排列.那么使用二分查找插入排序是一个非常好的选择

快速排序

这个也是经常被问到,是递归算法的经典使用场景

const array = [12, 2, 3, 10, 8, 8, 9, 21]
function quickSort(array){
    let len = array.length;
    if (len == 0 || len == 1) {
        return array;
    }
    let mid = array[0],
        left =[],
        right = [];
    for (let i = 1; i < len; i++) {
        if (array[i] < mid) {
            left.push(array[i])
        } else {
            right.push(array[i])
        }
    }
    return quickSort(left).concat(mid, quickSort(right))
}
quickSort(array)  //[2, 3, 8, 8, 9, 10, 12, 21]
复制代码

时间复杂度为O(nlogn),空间复杂度为O(n),不稳定

平均时间复杂度低 ,占用空间小,快速排序是使用得最多得排序算法

归并排序

归并排序是分治算法得经典应用,归并算法得核心是将两个已经排序的序列合并成一个序列.

const array = [12, 2, 3, 10, 8, 8, 9, 21]
function mergeSort(array){
    let len = array.length;
    if (len == 0 || len == 1) {
        return array;
    }
    function merge(left, right) {
        let final = [];
        while (left.length && right.length) {
            final.push(left[0] <= right[0] ? left.shift() : right.shift());
        }
		return final.concat(left.concat(right));
    }
    let mid = Math.floor(len-1/2);
    let left = array.slice(0, mid)
    let right = array.slice(mid);
    return merge(mergeSort(left), mergeSort(right))
}
mergeSort(array)  //[2, 3, 8, 8, 9, 10, 12, 21]

复制代码

时间复杂度为O(nlogn),空间复杂度为O(n),不稳定

时间复杂度和空间复杂度与快速排序是一样的,其实二个性能是相当的,毕竟二种排序都出现在浏览器内核中。为什么要快速排序使用较大,可能快速排序在各种数据量下表现得更为稳定吧. 但是如果数据呈分段有序时,使用归并排序效率更高

堆排序

具体如何实现,在这一章已经讲过,我直接贴上代码了

 // 最大堆调整
  function maxHeapfiy(array, i, heapSize){
        let left = 2*i+1,
            right = 2*i+2,
            mid = i;
        if (left < heapSize && array[left] > array[mid]) {
            mid = left;
        }
        if (right < heapSize && array[right] > array[mid]) {
            mid = right;
        }
        if (mid != i) {
            [array[i], array[mid]] = [array[mid], array[i]]
            maxHeapfiy(array, mid, heapSize)
        }
    }  
    // 构建最大堆
    const buildMaxHeapfiy = (array, heapSize) => {
        let parent = Math.floor(heapSize/2)
        for (parent; parent >= 0; parent--) {
            maxHeapfiy(array, parent, heapSize)
        }
    }
    
    // 堆排序
    const array = [12, 2, 3, 10, 8, 8, 9, 21];
    let heapSize = array.length;
    buildMaxHeapfiy(array, heapSize)
    for (let i = heapSize-1; i >=0; i--) {
        [array[0], array[i]] = [array[i], array[0]];
        this.maxHeapfiy(array, 0, i);
    }
    // [2, 3, 8, 8, 9, 10, 12, 21]

复制代码

时间复杂度为O(nlogn),空间复杂度为O(n),不稳定

堆排序虽然,时间复杂度和空间复杂度都较低,但是堆排序的有个缺点在于当堆中的一个数据发生改变,都需要进行堆调整来维护最大堆(最小堆),需要额外的维护开销,由于在实际运用中,数据变动是很频繁的,所以实际上堆排序不是很适合实际的运用。

关注下面的标签,发现更多相似文章
评论