2019-02-21

五种排序方法

最近在极客时间上看算法,看了三个夜晚的排序。记录一下吧

冒泡排序

// 从左到右循环,相邻两个元素对比,如果不符合顺序就交换位置
function bubbleSort(arr) {
  if (arr.length==1) {
    return arr;
  }
  for(var i=0;i<arr.length;i++){
    for(var j=arr.length-i;j>=0;j--){
      if(arr[j+1]<arr[j]){
        var temp = arr[j]
        arr[j]=arr[j+1]
        arr[j+1]=temp        
      }
    }
  }
}
arr=[9,8,15,6,2,8]
bubbleSort(arr)
console.log(arr)

插入排序

function insertionSort(arr) {
  //左边第二个开始,往左边的已排序区域插入,从后往前插
  for(var i=1;i<arr.length;i++){
    var j=i-1;
    var value=arr[i];
    for(;j>=0;j--){
      if(value<arr[j]){
        //放到前面,继续循环
        arr[j+1]=arr[j];
        if(j==0){
          //如果前面没有了,则这个就是最小的了
          arr[j]=value;
          break;
        }
      }else{
        //结束循环
        arr[j+1]=value
        break;
      }
    }

  }
}
arr=[9,8,15,6,2,8]
insertionSort(arr)
console.log(arr)

选择排序

//从未排序中找到最小的元素放到已排序的末尾
function selectionSort(arr) {
  for(var i=0;i<arr.length-1;i++){
    var value=arr[i];
    for(var j=i;j<arr.length;j++){
      if (arr[j]<value) {
        var temp=value
        value=arr[j];
        arr[j]=temp;
      }
    }
    arr[i]=value;
  }
}
arr=[9,8,15,6,2,8]
selectionSort(arr)
console.log(arr)

归并排序


/*
 分治思想,将数组从中间分开,然后对每一部分接着分开,然后将分开的进行有序合并,需要使用递归
*/
function mergeSort(arr) {
  //对数组进行分离
  if (arr.length<=1) {
    return arr;
  }
  var mid = Math.floor((arr.length)/2);
  var arr1,arr2;
  arr1 = mergeSort(arr.slice(0,mid))
  arr2 = mergeSort(arr.slice(mid,arr.length))

  //对数组合并
  var result = merge(arr1,arr2)

  return result;
}

function merge(arr1,arr2) {
  var arr=[];
  while (true) {    
    var a = null;
    if(arr1.length!=0){
      a = arr1[0]
    }
    var b = null;
    if(arr2.length!=0){
      b = arr2[0]
    }
    if((b==null&&a!=null)||(a!=null&&a<=b)){
      arr.push(arr1.shift());
    }else if ((a==null&&b!=null)||(b!=null&&a>b)) {
      arr.push(arr2.shift());
    }else {//当a,b都为null
      break;
    }
  }
  return arr;
}

arr=[9,8,15,6,2,8]
var result = mergeSort(arr)
console.log(result)

快速排序

应该是错了,因为是原地排序

/*
  快速排序:从中间取一个点,将小于此点的元素放到左边,大于的放到右边,再分别对左右的进行同样的操作
*/
function quickSort(arr) {
  // 选中间的点
  if (arr.length<=1) {
    return arr;
  }
  var mid = Math.floor(arr.length/2);
  var arr1=[],arr2=[]
  //得到大于选中点的元素数组,和小于选中点的元素素组
  for(var i=0;i<arr.length;i++){
    if(i==mid) continue;
    if(arr[i]<=arr[mid]){
      arr1.push(arr[i])
    }else{
      arr2.push(arr[i])
    }
  }
  // 进行递归
  arr1=quickSort(arr1)
  arr2=quickSort(arr2)

  arr1.push(arr[mid])
  return arr1.concat(arr2)
}

arr=[9,8,15,6,2,8]
var result = quickSort(arr)
console.log(result)