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

冒泡排序

冒泡排序是最慢的 排序 算法之一，数据值会像起跑一样从数组的一端漂浮到另一端

动画演示

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)复制代码

选择排序

从数组的开头开始，将第一个元素和其他元素相比，最小的元素放在第一个位置，再从第二个位置开始

动画演示

js实现

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)复制代码

插入排序

类似人们按数字或字母顺序对数据进行排序，后面的要为前面的腾位置

动画演示

js实现

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)复制代码

希尔排序

它会首先比较较远的元素而非相邻的元素，让元素尽快回到正确的位置。

通过定义一个间隔序列来表示在排序过程中进行的元素间隔。

公开的间隔序列是701，301，132，57，23，10，4，1

动画演示

js实现

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)复制代码