Biegral Blog

1.思想：

快速排序应该是最常用的排序算法了。它的时间复杂度比冒泡排序，直接插入排序等低，且它的性能通常比其他的排序算法要好。和归并排序一样，快排也使用了分而治之的思想。将原始数组分为小数组

1）首先，选取数组中间元素作为基准点

2）创建两个新数组left和right，遍历原始数组，把比中间元素小的元素放在left数组， 把比中间元素大的元素放在right数组

3）left数组，中间元素，right数组合并

4） 使用递归，重复步骤1）和步骤2），直到left和right数组的长度都为1， 退出递归

function quickSort( arr ){
        // 递归退出条件
        if( arr.length <= 1 ){
            return arr;
        }
        // 获取中间元素下标
        var midIndex = Math.floor( arr.length / 2 );
        // 获取中间元素并从原数组剔除
        var midValue = arr.splice( midIndex, 1);
        var left = [];
        var right = [];

        for( var i=0; i < arr.length; i++ ){
            if( arr[i] < midValue ){
                left.push( arr[i] );
            }
            else{
                right.push( arr[i] );
            }
        }

        return quickSort( left ).concat( midValue, quickSort( right ) );
    }

---

冒泡排序

   var arr = [4,1,2,8,11,2,43,21,33,5 ];


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

         console.log( arr );
     }

     bubbleSort(arr);

---

选择排序

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

        console.log(arr);
    }

var arr = [4,1,2,8,11,2,43,21,33,5];
selectSort(arr)

---

直接插入排序

function insertSort2(arr){
    for( var i=1; i<arr.length; i++ ){
        if( arr[i] < arr[i-1] ){
           var temp = arr[i];
            for(var j=i-1; arr[j] > temp; j-- ){
                arr[j+1] = arr[j]
            }
            arr[j+1] = temp;
        }
    }
    console.log(arr);
}

 var arr2 = [2,1,22,6,4,2,8,9,14];

insertSort2( arr2 );

希尔排序

“`

var arr = [4,2,8,21,33,5,8,7,6,1,1,1,2,2,3,5,6,7,3,77,99,12,31,4 ]; function shellSort( arr ){ var gap = arr.length; console.log(arr); do{ gap = parseInt( gap/2 ); console.log( 'gap:'+gap ); for( var i=gap; i