首页 > 代码库 > JavaScript新手学习笔记3——三种排序方式(冒泡排序、插入排序、快速排序)

JavaScript新手学习笔记3——三种排序方式(冒泡排序、插入排序、快速排序)

每种编程语言学到数组的时候,都会讲到排序算法,当时学C语言的时候,卡在排序算法。今天来总结一下javascript中如何实现三种排序算法。

1.冒泡排序(默认升序排列哦)

  原理:

  冒泡排序的原理,顾名思义,就是小数往上冒,大数往下沉。从第一个数开始,如果比第二个数大就交换位置,然后跟第三个数字进行比较大小,交换位置等。

  举例一下,有数组[2,4,3,5,1]

  第一次循环:2<4  不交换;4>3 交换;4<5不交换;5>1交换,故结果是[2,3,4,1,5];

  第二次循环:2<3,3<4不交换;4>1交换,4<5不交换,故结果是[2,3,1,4,5]

  同理:

  第三次循环:结果是[2,1,3,4,5]

  第四次循环:结果是[1,2,3,4,5]

  javascript代码实现:

function bubbleSort(arr){
    for(var r=1;r<arr.length-1;r++){
        for(var i=0;i<arr.length-r;i++){
            if(arr[i]>arr[i+1]){
                var temp=arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=temp;
            }
        }
    }
    return arr;
}
var arr=[2,4,3,1,5];
arr=bubbleSort(arr);
console.log(arr);//[1,2,3,4,5]    

 

2.插入排序(默认升序)

  原理:

  默认第一个数字最小,然后取出第二个数字进行插入,如果第二个数字小于第一个数字,则第一个数字后移一位,第二个数字放到第一个位置。然后取出第三个数字,从第一个位置开始比较插入,直到最后一个数字。

  举例:有一个数组[2,4,3,5,1]

  第一次插入:2<4不插入,结果为[2,4,3,5,1]

  第二次插入:3>2,2不后移,3<4,4后移一位,3插入,结果为[2,3,4,5,1]

  同理:

  第三次插入:结果为[2,3,4,5,1]

  第四次插入:结果为[1,2,3,4,5]

  javascript代码实现:

var arr=[2,4,3,5,1];
//插入排序
function insertSort(arr){
    for(var i=1;i<arr.length;i++){
        var t=arr[i];
        var p=i-1;
        while(t<arr[p]&&p>=0){
            arr[p+1]=arr[p];
            p--;
        }
        arr[p+1]=t;
    }
}
insertSort(arr);
console.log(arr);//[1,2,3,4,5]

 

3.快速排序(默认升序排列)

  原理:

  取数组中间的元素,大于中间元素的放到right数组中,小于中间元素的放到left数组中,一次递归,直至每个left和right中元素为空或只为一个元素的时候停止。最后拼接子数组即可。

  举例:现有一数组[2,4,3,5,1]

  第一次排序:left=[2,1]                                                             middle=[3]                               right=[4,5]

  第二次排序:left.left=[]    left.middle=[1]  left.right=[2]             middle=[3]          right.left=[4]   right.middle=[5]    right.right=[]

  拼接即可得:[1,2,3,4,5]

  javascript代码实现:

var arr=[2,4,3,5,1];
function quickSort(arr){
    if(arr.length<=1){
        return arr;
    }
    else{
        var c=arr.splice(Math.floor(arr.length/2),1)[0];
        var left=[],right=[];
        for(var i=0;i<arr.length;i++){
            if(arr[i]>c){right.push(arr[i])}
            else{left.push(arr[i])}
        }
        return quickSort(left).concat(c,quickSort(right));
    }
}
arr=quickSort(arr);
console.log(arr);

 

  三种排序算法如上了,如果对比之下,冒泡排序的复杂度是O(n^2),插入排序复杂度是O(1),快速排序复杂度是O(n*log(n))。

  算法讲述如有不对,希望批评指正~

JavaScript新手学习笔记3——三种排序方式(冒泡排序、插入排序、快速排序)