数据结构之排序

发表于   |   分类于   |  

排序算法就是将一组数据元素按照某找顺序排列起来，便于查找
本文介绍几种常用的排序算法—插入排序、选择排序和冒泡排序，排序主要考虑的几点是时间性能、空间性能以及稳定性；

几种常见的排序方法总结

插入排序

直接插入排序

基本思想是在已经排序的序列上插入元素，使其有序； 

var a = [1,2,5,6,74,45,78,54,32,13,9,34,26,28,12];
var b = a;
var insertSort = function(a){
    var temp;
    var i;
    var j;
    for (i = 0; i < a.length; i++) {
        temp = a[i];
        for (j = i-1; j>-1 && temp<a[j]; j--) {
            a[j+1] = a[j];
        }
        a[j+1] = temp;
    }
};
insertSort(a);

平均情况下，时间复杂度为O(n^2),当待排序列基本有序时，是不错的排序方法；
其空间复杂度是O(1);
二分插入排序
二分插入排序只是减少了比较次数，而没有改变元素的移动次数，因此其时间复杂度依然为O(n^2) 

binarySort = function(a){
    var i,j,temp;
    var low,mid,high;
    for(i=0;i<a.length;i++){
        temp = a[i];
        low = 0;
        high = i-1;
        while(low<=high){
            mid = Math.floor((low+high)/2);
            if (temp<a[mid]) {
                high = mid-1;
            }else{
                low = mid;
            }
        }
        for(j=i-1;j>=low;j--){
            a[j+1] = a[j];
        }
        a[low] = temp;
    }
};

直接选择排序

选择排序的基本思想是从待排序的元素集合中选取最小（大）的元素放到带排序元素的最前（后）；使得带排序元素集合不断地缩小； 

var selectSort = function(a){
    var i, j , min;
    var temp;
    for(i = 0;i<a.length-1;i++){
        min = i;
        for(j = i+1;j<a.length;j++){
            if (a[j]<a[min]) {
                min = j;
            }
        }
        if (min!==i) {
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }
};

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

冒泡排序

冒泡排序的基本思想是通过相邻元素之间的比较和交换，使得之比较大的元素逐渐从底部移向顶部；

var bubbleSort = function(a){
    var i,j;
    var temp;
    for(i = 0;i<a.length;i++){
        for(j=0;j<a.length-i-1;j++){
            if (a[j]>a[j+1]) {
                temp = a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
};

冒泡排序的时间复杂度是O(n^2);空间复杂度是O(1);冒泡排序的移动次数较多，在这几种方法中是最慢的一种。