JS实现数据结构及算法之排序算法

var CArray = function () {
  this.dataStore = [9,5,6,8,2,7,3,4,1]   //定义数组
  this.swap = swap;      //数值交换位置
  this.bubbleSort = bubbleSort  //冒泡排序
}
function swap(arr, index1, index2) {
  var temp = arr[index1]
  arr[index1] = arr[index2]
  arr[index2] = temp
}
function bubbleSort() {
  var data = this.dataStore
  var numlength = data.length
  for(var outer = numlength; outer>=2; --outer) {
    for(var inner = 0; inner<=outer -1;inner ++) {
      if(data[inner] > data[inner + 1]){
        this.swap(this.dataStore, inner, inner+1)
      }
    }
  }
}
var aa= new CArray()
aa.bubbleSort()
console.log(aa.dataStore)

var CArray = function () {
  this.dataStore = [9,5,6,8,2,7,3,4,1]   //定义数组
  this.swap = swap;      //数值交换位置
  this.selectSort = selectSort  //选择排序
}
function swap(arr, index1, index2) {
  var temp = arr[index1]
  arr[index1] = arr[index2]
  arr[index2] = temp
}
function selectSort() {
  var min
  for(var outer = 0; outer < this.dataStore.length -2; ++outer) {
    min = outer
    for(var inner = outer +1; inner <= this.dataStore.length -1;  ++inner) {
      if(this.dataStore[inner] < this.dataStore[min]){
        min = inner
      }
    }
    this.swap(this.dataStore, outer,  min)
  }
}
var aa= new CArray()
aa.selectSort()
console.log(aa.dataStore)

var CArray = function () {
  this.dataStore = [9,5,6,8,2,7,3,4,1]   //定义数组
  this.insertSort = insertSort  //插入排序
}
function insertSort() {
  var temp, inner
  for(var outer = 1; outer < this.dataStore.length; ++outer) {
    temp = this.dataStore[outer]
    inner = outer
    while(inner>0 && (this.dataStore[inner -1]) >= temp){
      this.dataStore[inner] = this.dataStore[inner -1]
      // console.log('inner->',this.dataStore)
      inner --
    }
    this.dataStore[inner] = temp
    // console.log('outer->',this.dataStore)
  }
}
var aa= new CArray()
aa.insertSort()
console.log(aa.dataStore)

var CArray = function () {
  this.dataStore = [99,5,6,8,2,7,3,4,1,23,12,67,43,89]   //定义数组
  this.shellSort = shellSort  //希尔排序
  this.gaps = [5,3,1]  //希尔间隔
  this.dynamiSort = dynamiSort //动态的希尔排序
  this.swap = swap;      //数值交换位置
}
function shellSort() {
  for(var g = 0; g < this.gaps.length; ++g) {
    for(var i = this.gaps[g]; i < this.dataStore.length; ++i) {
      var temp = this.dataStore[i]
      for(var j = i; j>=this.gaps[g] && this.dataStore[j - this.gaps[g]] > temp; j-=this.gaps[g]) {
        this.dataStore[j] = this.dataStore[j - this.gaps[g]]
      }
      this.dataStore[j] = temp
    }
    console.log('调换后-》', this.dataStore)
  }
}
//动态的希尔排序
function dynamiSort() {
  var N = this.dataStore.length
  var h = 1
  while(h < N/3) {
    h = h*3+1
  }
  while(h>=1) {
    for(var i = h; i < N; ++i) {
      for(var j = i; j>=h && this.dataStore[j] < this.dataStore[j - h] ; j-=h) {
        console.log(j)
        this.swap(this.dataStore, j,  j-h)
      }
    }
    console.log('调整后-》',this.dataStore)
    h = (h-1) / 3
  }
}
function swap(arr, index1, index2) {
  var temp = arr[index1]
  arr[index1] = arr[index2]
  arr[index2] = temp
}
var aa= new CArray()
// aa.shellSort()
 aa.dynamiSort()
console.log(aa.dataStore)

// 归并排序
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 mergeArray(mergeSort(left), mergeSort(right));
}
//融合两个有序数组
function mergeArray(left, right) {
  var arr = []
  while(left.length && right.length) {
    if(left[0] > right[0]) {
      arr.push(right.shift())
    } else {
      arr.push(left.shift())
    }
  }
  return arr.concat(left, right)
}

var arr = [2,3,4,12,324,34,5,89,7654,8,9]

console.log(mergeSort(arr))

// 快速排序
function qSort(list) {
  if( list.length === 0) return []
  var pivot = list[0]
  var lesser = []
  var greater = []
  for(var i = 1; i < list.length; i++) {
    if(list[i] < pivot) {
      lesser.push(list[i])
    } else {
      greater.push(list[i])
    }
  }
  return qSort(lesser).concat(pivot, qSort(greater))
}

var arr = [4,3,5,2]
console.log(qSort(arr))