/**

*

* 冒泡排序

* 从末尾开始相邻两数相互比较大小,满足条件就交换位置。循环每进行一次，即可确定第i位数的值。

*冒泡排序的时间复杂度为O(n^2)。

*

*/

function bubbleSort(arr){

    if(arr == null || arr.length == 0) return;

    for(var i =0 ; i < arr.length-1 ;i++){      //比较n-1次即可

        for(var j = arr.length-1 ; j>i ;j--){

            if(arr[j] < arr[j-1]){

                var temp = arr[j];

                arr[j] = arr[j-1];

                arr[j-1] = temp;

            }

        }

    }

    console.log(arr);

}

/**

*

*选择排序

*第i次循环，将arr[i]与后面的数比较，用它后面最小的数和它交换。

*选择排序的时间复杂度为O(n^2)

*/

function selectSort(arr){

    if(arr == null || arr.length == 0) return;

    for(var i = 0 ; i < arr.length-1 ;i++){

        var minIndex = i;

        for(var j = i + 1; j < arr.length ; j++){

            if(arr[minIndex] > arr[j]){

                minIndex = j;

            }

        }

        if(minIndex !== i){

            var temp = arr[minIndex];

            arr[minIndex] = arr[i];

            arr[i] = temp;

        }

    }

    console.log(arr);

}

/**

*

*插入排序

*以第一个数为参照，将第i个数拿出，对第i个数前面的数整理好顺序后，将arr[i]插入正确位置。

*简单插入排序的时间复杂度也是O(n^2)。

*/

function insterSort(arr){

    if(arr == null || arr.length == 0) return;

    for(var i = 1; i < arr.length ; i++){

        var j = i;

        var target = arr[i];  //插入值

        while(j > 0 && target < arr[j-1] ){

              arr[j] = arr[j-1];

                j --;

        }

         arr[j] = target;

    }

    console.log(arr);

}

/*

var a = [15,8,14,2,6];

insterSort(a);

  运行过程

     i = 1   8 15 14 2 6

     i = 2      8 14 15 2 6

     i = 3   target = 2

              数组变化过程:      8 14 15 15 6

                          8 14 14 15 6

                              8 8 14 15 6

                          arr[0] = target 插入

                          2 8 14 15 6

     i = 4 .....

 */

/**

*快速排序

*这是阮一峰的版本，很直观，感觉写得相当棒！

*    （1）在数据集之中，选择一个元素作为"基准"（pivot）。

*

*　　（2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右

*     边。

*

*　　（3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素*     为止。

* 快速排序是不稳定的，其时间平均时间复杂度是O(nlgn)。

*/

var quickSort = function(arr) {if (arr.length <= 1) { return arr; }

    var pivotIndex = Math.floor(arr.length / 2);

    var pivot = arr.splice(pivotIndex, 1)[0];

    var left = [];

    var right =[];

    for(var i = 0; i < arr.length; i++){

        if(arr[i] < pivot){

            left.push(arr[i]);

        }else{

            right.push(arr[i]);

        }

    }

    return quickSort(left).concat([pivot], quickSort(right));

}

//快排还有一种更简便的写法

function quicksort(arr)

{

    if (arr.length == 0)

        return [];

    var left = new Array();

    var right = new Array();

    var pivot = arr[0];

    for (var i = 1; i < arr.length; i++) {

        if (arr[i] < pivot) {

           left.push(arr[i]);

        } else {

           right.push(arr[i]);

        }

    }

    return quicksort(left).concat(pivot, quicksort(right));

}