js排序算法(一)

v1 發(fā)布于2019-08-20 13:55 / 2577人閱讀

摘要：冒泡排序算法即相鄰的兩個元素進行比較，如果前一個元素比后一個元素大，則將這兩個元素換位，即將較大的元素后置。重復(fù)操作，每次都將的值折半比較，直到，唯的時候排序操作結(jié)束。歸并排序通過遞歸的方式不斷的合并兩個有序數(shù)組完成數(shù)組的排序

1. 冒泡排序算法: 即相鄰的兩個元素進行比較，如果前一個元素比后一個元素大，則將這兩個元素換位，即將較大的元素后置。

內(nèi)循環(huán)每走一次都會將前l(fā)ength - i個元素中的最大元素放到length - i 的位置上。

var data = [1, 49, 30, 80, 6, 2, 18, 15, 23, 78, 16, 5, 4, 2, 34, 35, 46, 18]
function bubble(arr) {
  var length = arr.length
  for (var i = 0; i < length; i++) {
    for(var j = 0; j < length - 1 -i; j++) {
      var temp = arr[j]
      if (arr[j] > arr[j+1]) {
        arr[j] = arr[j+1]
        arr[j+1] = temp
      }
    }
  }
  console.log(arr)
}

bubble(data)

2. 選擇排序算法: 每次循環(huán)都選擇最小值，然后將其與當前位置的值進行互換操作即可

function select(arr) {
  var minIndex
  var temp
  for (var i = 0; i < arr.length-1; i++) {
    minIndex = i
    for(var j = i + 1; j < arr.lenght - i - 1; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    temp = arr[i]
    arr[i] =  arr[minIndex]
    arr[minIndex] = temp
  }
  console.log(arr)
}
select(data)

3. 插入排序：如果前一個的值比當前值小則二者換位, 直到將這個碰見比前一個值小的數(shù)為止

function insert(arr) {
  for (var i=1; i= 0 && arr[preIndex] > current) {
      arr[preIndex+1] = arr[preIndex]
      preIndex--
    }
    arr[preIndex+1] = current
  }
  console.log(arr)
}
insert(data)

4. 希爾排序: 先將arr分成arr.length/2組,其中index=1和index=length/2 + 1為一組，

如果length/2的值比較小則互換位置。重復(fù)操作，每次都將gap的值折半比較，
直到，gap唯1的時候排序操作結(jié)束。

function shell(arr) {
  function swap(array, i, k) {
    var temp = array[i]
    array[i] = array[k]
    array[k] = temp
  }
  var gap = Math.floor(arr.length / 2)
  while(gap > 0) {
    for(var i=gap; i0; j-=gap) {
        if (arr[j-gap] > arr[j]) {
          swip(arr, j-gap, j)
        }
      }
    }
     gap = Math.floor(gap / 2)
  }
  console.log(arr)
}
shell(data)

5. 歸并排序: 通過遞歸的方式不斷的合并兩個有序數(shù)組完成數(shù)組的排序

function mergeSort(arr) {
  var len = arr.length;
  if (len < 2) {
    return arr
  }
  var middle = Math.floor(len / 2)
  var left = arr.slice(0, middle)
  var right = arr.slice(middle)
  return merge(mergeSort(left), mergeSort(right))
}

function merge(left, right) {
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());
    return result;
}
console.log(mergeSort(data))