首页 > 代码库 > 排序算法的归纳

排序算法的归纳

2024-08-16 08:19:36   222人阅读

o(n2)
冒泡排序：两两比较相邻记录的关键字，按小到大排序；从后到前，相邻两位都进行一次排序，每次循环都能把较小的数值往前推；优化部分做了一个标志，当不再进行位置互换时，利用flag直接结束。
技术分享
 
ps：取一位作为比较值与后面每一位数值进行比较，大则进行交换，这种排序很像冒泡排序，但严格意义上它并不算冒泡排序。只是简单的排序，因为这样做你会发现，每次循环都只是把当前最小值找到并往前排（交换），确并没有对其他数值的排序作出任何改变。
技术分享
function  bubbleSort(dataArray){
    var temp,flag=true;
    for(var i=0;i<dataArray.length-1&&flag;i++){
        flag=false;
        for(var j=dataArray.length-1;j>i;j--){
            if(dataArray[j]<dataArray[j-1]){
                temp=dataArray[j];
                dataArray[j]=dataArray[j-1];
                dataArray[j-1]=temp;
                flag=true;
            }
        }
    }
return dataArray;
}
 
选择排序：每一次从待排序的数组中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。（ 每次循环都选出当前最小值的下标min，并将min下标对应的数值放在靠前的i位置。）但是选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。
技术分享
 
function  selectSort(dataArray){
    var min,temp;
    for(var i=0;i<dataArray.length-1;i++){
        min=i;
        for(var j=i+1;j<dataArray.length-1;j++){
            if(dataArray[min]>dataArray[j])
                min=j;
        }
        if(i!=min){
            temp=dataArray[min];
            dataArray[min]=dataArray[i];
            dataArray[i]=temp;
        }
    }
return  dataArray;
}
 

插入排序：按数值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止，是稳定的排序算法。把待排序的值用index存放，在已排好序的数组中找到index的位置，然后插入。而这个index就是监视哨。

技术分享
function  insertionSort ( dataArray ){
    var j,index;
    for ( var i=0 ; i<dataArray.length ; i++ ){
        index = dataArray[i];
        j=i;
        while((j>0)&&(dataArray[j-1]>index)){
            dataArray[j]=dataArray[j-1];
            j-=1;
        }
        dataArray[j]=index;
    }
return  dataArray;
}
 
希尔排序：把数组按一定增量分组，对每组用插入排序算法排序。改变增量的大小，直至增量减少到1。运用到插入排序，也是不稳定排序。
技术分享
 
function  shellSort ( dataArray ){
    var temp,increment=Math.floor(dataArray.length/3);
    while(increment>0){
        for(var i=increment;i<dataArray.length;i++){
            for(var j=i;j>=increment&&dataArray[j]<dataArray[j-increment];j-=increment){
                temp=dataArray[j];
                dataArray[j]=dataArray[j-increment];
                dataArray[j-increment]=temp;
            }
        }
        increment=Math.floor(increment/3);
    }
return  dataArray;
}  
 
o(nlog(n))
堆排序：将待排序的数组构造成一个大顶堆（完全二叉树——每个结点的值都大于或等于其左右孩子结点的值），根据大顶堆的特性，最大值就是堆顶的根，排序时把根取出（取出的过程就是将根即最大值和数组的最后一个值交换位置），将剩下的n-1个数重新构成大顶堆，如此往复。
技术分享
技术分享
 
 
function  heapSort(dataArray){
    //首先创建大顶堆
    var length= dataArray.unshift(0);     //根据树结点的特性，父节点是第i个结点，则子节点是第i*2个结点和第i*2+1个结点，但是结点是从1开始计算，数组是0，所以这里为传入的数组                                                                                      //开始位置添加了一个元素     
    for(var i=Math.floor((length-1)/2);i>0;i--){
        dataArray= heapAdjust(dataArray,i,length-1);             //找出所有父节点i对应的子树，把每棵子树都构成大顶堆
    }
    for(var i=length-1;i>1;i--){
        dataArray= swap(dataArray,1,i);                                        //把根取出
        dataArray= heapAdjust(dataArray,1,i-1);                        //把剩下的[1..i-1]项重新构成大顶堆
    }
    return dataArray;
}
function heapAdjust(dataArray,i,l){
    var temp=dataArray[i];                                                                    //构建大顶堆前，先把父节点放在temp
    for(var j=i*2;j<=l;j*=2){                                                              //循环找到每棵子树的子节点j
        if(j<l&&dataArray[j]<dataArray[j+1])                                //子节点j少于数组长度，以防j+1越界，并在子树的左右结点找到较大值，记录在下标j中
            ++j;
        if(temp>=dataArray[j])                                                            //在父节点i和左右结点中的较大值中找出最大值
            break;
        dataArray[i]=dataArray[j];                                                        //如果左右结点的较大值比父节点i大，把父节点和较大值交换
        i=j;
    }
    dataArray[i]=temp;
return dataArray;
}
function swap(arr,i,j){
    var temp;
    temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
    return arr;
}
    var arr = [50, 10, 90, 30, 70, 40, 80, 60, 20];
    arr=heapSort(arr);
    arr.shift();                                                                                  //把数组添加的值删除
 
归并排序：
function  mergeSort(dataArray){
    if(dataArray.length==1) return dataArray;
    var mid=Math.floor(dataArray.length/2);
    var left=dataArray.slice(0,mid);
    var right=dataArray.slice(mid);
    return  MSort(mergeSort(left),mergeSort(right));
}
function MSort(left,right){
    var array=[];
    while(left.length>0&&right.length>0){
        if(left[0]<right[0]){
            array.push(left.shift());
        }else{
            array.push(right.shift());
        }
    }
    return  array.concat(left).concat(right);
}
 
快速排序：
function quickSort(dataArray, left, right){
        if(left < right){
                var key = dataArray[left];
                var low = left;
                var high = right;
                while(low < high){
                        while(low < high && dataArray[high] > key){
                                high--;
                        }
                        dataArray[low] = dataArray[high];
                        while(low < high && dataArray[low] < key){
                                low++;
                        }
                        dataArray[high] = dataArray[low];
                }
                dataArray[low] = key;
                quickSort(dataArray,left,low-1);
                quickSort(dataArray,low+1,right);
        }
}  
 
 
 
 

排序算法的归纳


联系
我们