一些简单的数组排序算法

arraySort 数组排序

这里为大家整理了一些简单的数组排序的算法

冒泡排序 --- 比较两个相邻的元素,替换成正确的位置(你选择的正序还是倒序)
快速排序 --- 基线条件 --- 只剩一个元素的时候就是有序的数组
选择排序 --- 无序中选择极值,进行排序
插入排序 --- 无序中循环,插入到有序中

冒泡排序

重复地走访过要排序的元素列,一次比较两个相邻的元素,重复地进行直到没有相邻元素需要交换,也就是说该元素已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

1. 从数组的第一项 **arr[0]** 项开始,与 **arr[1]** 进行对比,大的往后移动
2. 对每一个相邻的元素,都进行以上操作,直到没有相邻元素进行对比,最后一对相邻  **arr[length-2]-arr[length-1]** 
3. 两两对比一轮之后,发现数组最后一个元素是最大的
4. 每走一轮,大的元素都到冒泡到了最后面,所以 ***n个元素,n-1个循环(n-1轮)(n-1个外循环)***(最后第二轮结束的时候,最小的元素已经在最前面了) 
5. 每走一轮,最后的元素已经排好序,所以每走一轮,**比较相邻元素的次数少了一次  arr.length-1-当前外循环 **

冒泡排序

function bubbleSort(arr){
    var length = arr.length;
    for(var i = 0;i<length-1;i++){
        for(var j=0;j<length-i-1;j++){
            var left = arr[j];
            var right = arr[j+1];
            if(left>right){
                arr[j]=right;
                arr[j+1]=left;
            }
        }
    }
    return arr;
}
冒泡排序的优点:每进行一趟排序,就会少比较一次,因为每进行一趟排序都会找出一个较大值。
每进行一趟比较,每一趟少比较一次,一定程度上减少了算法的量。

快速排序 -递归-分而治之

通过一趟排序将要排序的数据分割成独立的两部分,然后再按此方法对这两部分数据分别进行快速排序,每次返回一个有序数组。

1. 基数条件(不再进行递归的操作):数组长度等于1
2. 递归条件:数组长度大于1
3. 选择一个基准值 **base**
4. 大于基准值的放一边,小于基准值的放一边 **left right**
5. 分开的每边 再次挑选基准值,重复3之后的步骤
6. 最后将返回的数组合并在一起
function quickSort(arr){
    if(arr.length<2){
        return arr;
    }
    var base = arr.splice(Math.floor(arr.length/2),1); //基准值
    var left = [];
    var right = [];
    for(var i=0;i<arr.length;i++){
        if(arr[i]<base){
            left.push(arr[i]); //小于基准值
        }else{
            right.push(arr[i]); //大于基准值
        }
    }
    return [].concat(quickSort(left),base,quickSort(right));
}

选择排序 无序中选择极值进行排序

1. 在数组中选择出 ** 最小的一项 极值 **(也就是没有排序的当中)
2. 将其插入到数组的开头(有序的开头)
3. 再把选出来的最小一项删除掉
3. 上面两部就行成了 (有序的开头+无序的数组)
4. 每走一轮,前面的有序+1,后面的无序-1,所以,n个元素,***n-1轮*** 第n轮已经找不到无序的了

图片描述

function selectSort(arr){
    var length = arr.length;
    for(var i = 0;i<length-1;i++){
        var min = arr[i];
        var minIndex = i;
        for(var j = i+1;j<length;j++){ //无序中选择最极值
            if(arr[j]<min){
                min = arr[j];
                minIndex = j;
            }
        }
        arr.splice(i,0,min); //将极值插入到有序中
        arr.splice(minIndex+1,1);//将原先的位置删除
    }
    return arr;
}

插入排序 无序中循环,插入到有序中

图片描述

1.假设**arr[0]**为有序的第一项,arr[0]之后的都为无序 (有序+无序)
2.从arr[0]之后无序进行循环,插入到**有序**相应的位置中
3.每走一轮,有序+1,无序-1

n.arr[n]和arr[n-1]对比,满足 arr[n-1] > arr[n], =>=> 在有序中找到相应的位置插入  

图片描述

function insertSort(arr){
    var length = arr.length;
    for(var i = 1;i<length;i++){
        var insert = arr[i]; //插入元素
        var insertIndex = i; // 插入位置
        if(arr[i-1]>arr[i]){ //判断能不能动,只要前面那一项比他大就能动
            for(var j = i-1;j>=0;j--){
                if(arr[j]>insert){ //前面那一项比他大,那么将前面那一项的位置记录下来,
                    insertIndex = j;
                }
            }
            arr.splice(insertIndex,0,insert); //插入到前面去
            arr.splice(i+1,1); //原来位置上的删除,因为插入了一项,要在原来的位置上加1
        }

    }
    return arr;
}

再来对比一下这四个排序
ms \ 数组长度 6 10 3000
冒泡排序 0.19 0.56 19.6
快速排序 0.28 0.29 0.27
选择排序 0.22 0.82 12.6
插入排序 0.34 0.44 11
数组越长,快速排序>插入排序>选择排序>冒泡排序

评论

暂无评论