几大排序算法js实现

冒泡排序

1 具体实现

// 冒泡排序
function bubbleSort(arr) {
    let len = arr.length;
    let temp;
    for (var i=0; i<len; i++) {
        for(var j = 0; j<len-i-1; j++ ) {
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp; 
            }
        }
    }
}

2 分析

耗时

通过函数图像很容易得到：

函数图

由以上可以得到冒泡排序的时间复杂度为：
F(n) = O(n^2)

选择排序

1 具体实现

// 选择排序
function selectSort(arr) {
    let len = arr.length;
    for(var i=0; i<len-1; i++) {
        let smallIndex = i;
        let temp;
        for(var j=i+1; j<len; j++) {
            if (arr[j] < arr[smallIndex]) {
                smallIndex = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[smallIndex];
        arr[smallIndex] = temp;
    }
}

2 分析
很明显，可以看出选择排序和冒泡排序的时间复杂度一致，都是 O(n^2) 。

插入排序

1 具体实现

function insertSort(arr) {
    let len = arr.length;
    for(var i=1; i<len; i++) {
        let temp = arr[i];
        for(var j=i-1; j>=0; j--) {
            if(temp<arr[j]) {
                arr[j+1] = arr[j];
                if(j==0) {
                    arr[j] = temp;
                }
            } else {
                arr[j+1] = temp;
                break;
            }
        }
    }
}

2 分析
很明显，可以看出插入排序和冒泡排序的时间复杂度一致，都是 O(n^2) 。

快速排序

1. 具体实现

... 未完待续