Javascript 排序算法

Posted on

冒泡排序

（1）算法说明：是最慢的算法之一，也是最容易实现的排序算法。使用冒泡排序时，数据值会像气泡一样从数组的一端浮到另一端，算法每次比较相邻到元素，如果顺序错误就交换。
（2）javascript实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//如果某一次没有任何交换，则之后不需要再交换
function bubbleSort(arr){
    var len = arr.length;
    for(var i = 0; i < len;i++){
        var isExchange = false;
        for(var j = 0; j < len-i;j++){
            if(arr[j] > arr[j+1]){
                var temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                isExchange = true;
            }
        }
        if(isExchange == false){
            break;
        }
    }
    return arr;
}
（3）算法分析
    时间复杂度：O(n的平方)
    空间复杂度：O(1)
    稳定性：稳定

选择排序

（1）算法说明：从待排序的数据元素中选择最小（或最大）的元素，存放在序列的起始位置，直到全部待排元素排完。
（2）javascript实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function selectionSort(arr){
    var len = arr.length;
    var minIndex,temp;
    for(var i = 0; i < len;i++){
        minIndex = i;
        for(var j = i; j < len;j++){
            if(arr[minIndex] > arr[j]){
                minIndex = j;
            }
        }
        temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
    return arr;
}

（3）算法分析
时间复杂度：O(n的平方)
空间复杂度：O(1)
稳定性：不稳定

插入排序

（1）算法说明：将一个数据插入到已经排好的有序的有序数据中。
（2）javascript实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
function insertSort(arr){
    var len = arr.length;
    for(var i = 1; i < len;i++){
        var key = arr[i];
        var j = i-1;
        while(j>=0 && arr[j] > key){
            arr[j+1] = arr[j];
            j–;
        }
        arr[j+1] = key;
    }
    return arr;
}

（3）算法分析
时间复杂度：O(n的平方)
空间复杂度：O(1)
稳定性：稳定

归并排序

（1）算法说明：将一系列排好序的子序列合并成一个大的完整有序序列。
（2）javascript实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function mergeSort(arr){
    var len = arr.length;
    if(len < 2){
        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(leftArr,rightArr){
    var result = [];
    while(leftArr.length && rightArr.length){
        if(leftArr[0] > rightArr[0]){
            result.push(rightArr.shift())
        }else{
            result.push(leftArr.shift());
        }
    }
    while(leftArr.length){
        result.push(leftArr.shift());
    }
    while(rightArr.length){
        result.push(rightArr.shift());
    }
    return result;
}

（3）算法分析
时间复杂度：O(nlogn)
空间复杂度：O(1)
稳定性：稳定

快速排序

（1）算法说明：快速排序是处理大数据集最快的排序算法之一，是一种分而治之的算法，通过递归的方法将数据依次分解为包含较小元素和较大元素的不同子序列，不断重复这个步骤直到所有数据都是有序的。
（2）算法步骤：

  • 在数据集之中，选择一个元素作为”基准”（pivot）。
  • 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。
  • 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
    （3）javascript实现：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    function quickSort(arr){
        if(arr.length === 0){
            return [];
        };
        var pivot = arr[0],
             left = [],
             right = [];
        for(var i = 1; i < arr.length; i++){
            if(arr[i] < pivot){
                left.push(arr[i]);
            }else{
                right.push(arr[i]);
            }
        };
        return quickSort(left).concat([pivot],quickSort(right));
    }

（4）算法分析
时间复杂度：O(nlogn) 最差O(n方)
空间复杂度：O(1)
稳定性：不稳定