JS实现排序算法

常用的排序算法一般分为五类，分别是冒泡排序、选择排序、插入排序、归并排序以及快速排序。

冒泡排序

var test=[4,43,30,431,98,0];
function bubbleSort(arr) {
	var length=arr.length;
  for (var i = 0; i < length; i++) {
		for(var j=0;j<length-1;j++){
    		if(arr[j]>arr[j+1]){
        	temp=arr[j];
          arr[j]=arr[j+1];
          arr[j+1]=temp;
        }
    }
  }
}
bubbleSort(test);
console.log(test); // [0, 4, 30, 43, 98, 431]

选择排序

var test = [4, 43, 30, 431, 98, 0];
function selectionSort(arr) {
  var length = arr.length,
    indexMin;
  for (var i = 0; i < length - 1; i++) {
    indexMin = i;
    for (var j = i; j < length; j++) {
      if (arr[indexMin] > arr[j]) {
        indexMin = j;
      }
      temp = arr[i];
      arr[i] = arr[indexMin];
      arr[indexMin] = temp;
    }
  }
}
selectionSort(test);
console.log(test); // [0, 4, 30, 43, 98, 431]

插入排序

var test = [4, 43, 30, 431, 98, 0];
function insertionSort(arr) {
  var length = arr.length,
    temp;
  for (var i = 1; i < length; i++) {
    var j = i;
    temp = arr[i];
    while (j > 0 && arr[j - 1] > temp) {
      arr[j] = arr[j - 1];
      j--
    }
    arr[j] = temp;
  }
}
insertionSort(test);
console.log(test); // [0, 4, 30, 43, 98, 431]

归并排序

var test = [4, 43, 30, 431, 98, 0];

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

  while (left.length && right.length) {
    if (left[0] < right[0])
      tmp.push(left.shift());
    else
      tmp.push(right.shift());
  }
  console.log(tmp.concat(left, right));
  return tmp.concat(left, right);
}

function mergeSort(a) {
  if (a.length === 1) return a;
  var mid = Math.floor(a.length / 2),
    left = a.slice(0, mid),
    right = a.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}
test = mergeSort(test);
console.log(test); // [0, 4, 30, 43, 98, 431]

快速排序

var test = [4, 43, 30, 431, 98, 0];
function quickSort(arr){
    function swap(arr,right,left){
        var tmp = arr[right];
        arr[right]=arr[left];
        arr[left]=tmp;
    }
    function partition(arr,left,right){//分区操作，
        var pivotValue=arr[right]//最右面设为标准
        var storeIndex=left;
        for(var i=left;i<right;i++){
            if(arr[i]<=pivotValue){
                swap(arr,storeIndex,i);
                storeIndex++;
            }
        }
        swap(arr,right,storeIndex) ;
        return storeIndex//返回标杆元素的索引值
    }
    function sort(arr,left,right){
        if(left>right) return;
        var storeIndex=partition(arr,left,right);
        sort(arr,left,storeIndex-1);
        sort(arr,storeIndex+1,right);
    }
    sort(arr,0,arr.length-1);
    return arr;
}
quickSort(test);
console.log(test); // [0, 4, 30, 43, 98, 431]