排序算法-JS

冒泡排序

基本思路：

1.依次比较相邻的两个数，如果第一个比第二个小，不变。如果第一个比第二个大，调换顺序。一轮下来，最后一个是最大的数

2.对除了最后一个之外的数重复第一步，直到只剩一个数

function bubbleSort(arr){

var len = arr.length;

for (var i = 0; i < len - 1; i++){

             for (var j = 0, stop = len - 1 - i; j < stop; j++){

                     if (arr[j] > arr[j + 1]){

                        swap(arr, j, j + 1);

                                  }

                          }

                 }

               return arr;

}

function swap(arr, p1, p2){

var temp = arr[p1];

         arr[p1] = arr[p2];

          arr[p2] = temp;

}

快速排序

基本思路：

1.以一个数为基准(中间的数)，比基准小的放到左边，比基准大的放到右边

2.再按此方法对这两部分数据分别进行快速排序（递归进行）

3.不能再分后退出递归，并重新将数组合并

function quickSort(arr){

if(arr.length<=1)

       {

             return arr;//如果数组只有一个数，就直接返回；

           }

   var num = Math.floor(arr.length/2);//找到中间数的索引值，向下取整

   var numValue = arr.splice(num,1);//找到中间数的值,并从原数组删除

   var left =[];  var right =[];

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

             left.push(arr[i]);//基准点的左边的数传到左边数组

             }else{

            right.push(arr[i]);//基准点的右边的数传到右边数组}

      }

       return arguments.callee(left).concat(numValue,arguments.callee(right));//递归不断重复比较}

选择排序

基本思路：

1.找出最小的数，和第一个交换位置

2.在剩下的数中，找出最二小的数，放在第二个

3.依次类推，排出顺序

function selectionSort(arr){

var len=arr.length,min=0;

for(i=0;i<len;i++){

         min=i;          

for(j=i+1;j<len;j++){

     if  (arr[j]<arr[min]){

         min=j;

         }

      }

       if(i!=min){

        swap(arr,i,min);

         }

}

  return arr;

}

function swap(arr,p1,p2){

var temp=arr[p1];

arr[p1]=arr[p2];

arr[p2]=temp;

}

插入排序

基本思路：

1.把数组分为[已排序]和[未排序]两部分,第一个数为[已排序]，其余为[未排序]

2.从[未排序]抽出第一个数，和[已排序]部分比较，插入到合适的位置

function insertionSort(arr){

var len=arr.length,// 数组的长度

value,// 当前比较的值

        for(i=0;i<len;i++){

                  value=arr[i];

/*

* 当已排序部分的当前元素大于value， 就将当前元素向后移一位，再将前一位与value比较

*/

     for(j=i-1;j>-1&&arr[j]>value;j--){

      arr[j+1]=arr[j];

        }

   arr[j+1]=value;

    return arr;

}