数据结构的js描述

沈冬冬

图片.png

冒泡排序

时间复杂度O（n^2） 稳定

function bubbleSort(arr) {
    var len = arr.length;  
      for (var i = 0; i < len - 1; i++) { 
        for (var j = 0; j < len - i - 1; j++) { //第一次排序后最后一个已经为最大的数了
            if (arr[i] > arr[i + 1]) {
                var temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
    return arr;
    }

2.gif

选择排序

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

function selectSort(arr) {
    var len = arr.length;
    var minIndex,temp;
    for( var i = 0; i<len - 1; i++){
        minIndex = i;
        for(var j = i+1; j < len; j++){
            if(arr[i] > arr[j]){
                minIndex = j;               
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;   
    }
return arr;
}

3.gif

插入排序

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

function insertSort(arr) {
    var len = arr.length;
    var preIndex,temp;
    for(var i = 1; i < len; i++){
        preIndex = i - 1;
        temp = arr[i];
        while(preIndex >= 0 && arr[preIndex] > temp ){
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
    arr[preIndex+1] = temp;         
    }
    
    return arr;
}

4.gif

希尔排序

时间复杂度为O(nlogn) 不稳定
插入排序改进版，间隔序列可以自己设定

function shellSort(arr) {
    var len = arr.length;
    var gap = 1;
    while(gap > len/3){
        gap = gap*3 +1;
    }
    for(gap; gap > 0; gap = Math.floor(gap/3) ) {
        for(var i = gap; i < len; i++ ){
            for(var j = i; j>=gap && arr[j-gap]>arr[j]; j-=gap){
                swap(arr,j,j-gap);
            }
        }
    }
}
function swap(data,j,j){ //调换数组中的两个数
    var temp;
    temp = data[i];
    data[i] = data[j];
    data[j] = temp;
}

快速排序

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

function quickSort(arr) {
    var len = arr.lenth;
    if(len <= 1){
        return arr;
    }
    var pivotIndex = Math.floor(len / 2);
    var pivot = arr.splice(pivetIndex, 1);//选取中间的数为基数
    var left = [];
    var right = [];
    for(var i = 0; i < len; i++){
        arr[i] > pivot? right.push(arr[i]) : left.push(arr[i]);// 比基数大的放入右边数组，大的放右边数组
    }
    return quickSort(left).concat([pivot], right);
}

归并排序

时间复杂度为O(nlogn) 稳定

function mergeSort(arr) {
    var len = arr.length;
    if(len <= 1){
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    var newArr = [];
    while(left.length > 0 && right.length > 0){
        left[0] >= right[0] ? newArr.push(right.shift()) : newArr.push(left.shift());
    }
    if(left.length > 0) 
        newArr.concat(left);  //最后左右的数组的长度不一样
    if(right.length > 0)
    return newArr.concat(right);
}

5.gif