js 排序算法

一、比较算法的复杂性

• 算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度

1.1、时间复杂度

• 算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。

1.2、空间复杂度

• 空间复杂度是指执行这个算法所需要的内存空间。

二、常见的排序算法

2.1、冒泡排序

• 时间复杂度 O(n^2)
• 空间复杂度 O(1)

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) { //相邻元素两两对比
                var temp = arr[j+1]; //元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

2.2、 选择排序

• 时间复杂度 O(n^2)
• 空间复杂度 O(1)

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    console.time('选择排序耗时');
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) { //寻找最小的数
                minIndex = j; //将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    console.timeEnd('选择排序耗时');
    return arr;
}

2.3、插入排序

• 时间复杂度 O(n^2)
• 空间复杂度 O(1)

function insertionSort(array) {
    console.time('插入排序耗时：');
    for (var i = 1; i < array.length; i++) {
        var key = array[i];
        var j = i - 1;
        while ( array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
    console.timeEnd('插入排序耗时：');
    return array;
}

2.4、 希尔排序

• 时间复杂度 O(nlogn)
• 空间复杂度 O(1)

function shellSort(arr) {
    var len = arr.length,
    temp,
    gap = 1;
    console.time('希尔排序耗时:');
    while(gap < len/5) { //动态定义间隔序列
        gap =gap*5+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/5)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    console.timeEnd('希尔排序耗时:');
    return arr;
}

2.5、 快速排序

• 时间复杂度 O(nlogn)
• 空间复杂度 O(logn)

function quickSort(array, left, right) {
    console.time('1.快速排序耗时');
    if (left < right) {
        var x = array[right], i = left - 1, temp;
        for (var j = left; j <= right; j++) {
            if (array[j] <= x) {
                i++;
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        console.log(array) ;
        console.log(left,i) ;
        quickSort(array, left, i - 1);
        console.log(array)
        console.log(i,right)
        quickSort(array, i + 1, right);
    }
    console.timeEnd('1.快速排序耗时');
    console.log(array)
    return array;
}

2.6、 堆排序

• 时间复杂度 O(nlogn)
• 空间复杂度 O(1)

function heapSort(array) {
    console.time('堆排序耗时');
    //建堆
    var heapSize = array.length, temp;
    for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {  
        heapify(array, i, heapSize);
    }
    //堆排序
    for (var j = heapSize - 1; j >= 1; j--) {
        temp = array[0];
        array[0] = array[j];
        array[j] = temp;
        console.log(array)
        heapify(array, 0, --heapSize);
    }
    console.timeEnd('堆排序耗时');
    return array;
}

function heapify(arr, x, len) {
    var l = 2 * x + 1, r = 2 * x + 2, largest = x, temp;
    if (l < len && arr[l] > arr[largest]) {
        largest = l;
    }
    if (r < len && arr[r] > arr[largest]) {
        largest = r;
    }
    if (largest != x) {
        temp = arr[x];
        arr[x] = arr[largest];
        arr[largest] = temp;
        console.log(arr)
        heapify(arr, largest, len);
    }
}