2020-06-07排序笔记

一、冒泡排序^[1]

时间复杂度
- 最好情况 $O(n)$ ，一般情况 $O（n^2）$ ，最差情况 $O(n^2)$
code

let {ArrayList}=require('../ArrayList.js')
class BubbleSort extends ArrayList{
  constructor(){
    super()
  }
  sort(){
    let len=this.array.length
    for(let i=0;i<len;i++){
      for(let j=0;j<len-1-i;j++){//减去i避免做重复比较，已经比较的就不再比较了
        if(this.array[j]>this.array[j+1]){
          this.swap(j,j+1)
        }
      }
    }
  }
}
function test(size){
  let bubble=new BubbleSort()
  for(let i=size;i>0;i--){
    bubble.insert(i)
  }
  console.log(bubble.toString())
  bubble.sort()
  console.log(bubble.toString())

}
test(10)

二、插入排序^[2]

时间复杂度
- 最好情况 $O(n)$ ，一般情况 $O（n^2）$ ，最差情况 $O(n^2)$
code

let {ArrayList}=require('../ArrayList.js')
class InsertSort extends ArrayList{
  constructor(){
    super()
  }
  sort(){
    let len=this.array.length
    let j
    let temp
    for(let i=1;i<len;i++){
      j=i
      temp=this.array[i]
      while(j>0&&this.array[j-1]>temp){
        this.array[j]=this.array[j-1]
        j--
      }
      this.array[j]=temp
    }
  }
}
function test(size){
  let insert=new InsertSort()
  for(let i=size;i>0;i--){
    insert.insert(i)
  }
  console.log(insert.toString())
  insert.sort()
  console.log(insert.toString())

}
test(10)

三、选择排序^[3]

时间复杂度
- 最好情况 $O(n^2)$ ，一般情况 $O（n^2）$ ，最差情况 $O(n^2)$
code

let {ArrayList}=require('../ArrayList.js')
class SelectSort extends ArrayList{
  constructor(){
    super()
  }
  sort(){
    let len=this.array.length
    let minIndex=0
    
    for(let i=0;i<len;i++){
      minIndex=i
      for(let j=i;j<len;j++){
        if(this.array[minIndex]>this.array[j]){
          minIndex=j
        }
      }
      if(i!==minIndex){
        this.swap(i,minIndex)
      }
    }
  }
}
function test(size){
  let slelect=new SelectSort()
  for(let i=size;i>0;i--){
    slelect.insert(i)
  }
  console.log(slelect.toString())
  slelect.sort()
  console.log(slelect.toString())

}
test(10)

四、归并排序^[4]

时间复杂度
- 最好情况 $O(nlog(n))$ ，一般情况 $O(nlog(n))$ ，最差情况 $O(nlog(n))$
code

let {ArrayList}=require('../ArrayList.js')
class MergeSort extends ArrayList{
  constructor(){
    super()
  }
  sort(){
    this.array=this.mergeRect(this.array)
  }
  mergeRect(arr){//将数组拆分成小数组
    let len=arr.length
    if(len===1){
      return arr
    }

    let mid=Math.floor(len/2)
    let left=arr.slice(0,mid)
    let right=arr.slice(mid,len)
    return this.merge (this.mergeRect(left),this.mergeRect(right))
  }
  merge(left,right){
    let res=[]
    let il=0
    let ir=0
    while(il<left.length&&ir<right.length){
      if(left[il]<right[ir]){
        res.push(left[il++])
      }else{
        res.push(right[ir++])
      }
    }
    while(il<left.length){
      res.push(left[il++])
    }
    while(ir<right.length){
      res.push(right[ir++])
    }
    return res
  }
}
function test(size){
  let merge=new MergeSort()
  for(let i=size;i>0;i--){
    merge.insert(i)
  }
  console.log(merge.toString())
  merge.sort()
  console.log(merge.toString())

}
test(5)

五、快速排序^[5]

时间复杂度
- 最好情况 $O(nlog(n))$ ，一般情况 $O(nlog(n))$ ，最差情况 $O(n^2)$
code

let {ArrayList}=require('../ArrayList.js')
class QuickSort extends ArrayList{
  constructor(){
    super()
  }
  sort(){
    this.quick(this.array,0,this.array.length-1)
  }
  quick(arr,left,right){
    let index
    if(arr.length>1){
      index=this.partition(arr,left,right)
      if(left<index-1){
        this.quick(arr,left,index-1)
      }
      if(index<right){
        this.quick(arr,index,right)
      }
    }
  }
  partition(arr,left,right){
    let pivot=arr[Math.floor((right+left)/2)]
    let i=left
    let j=right
    while(i<=j){
      while(arr[i]<pivot){
        i++
      }
      while(arr[j]>pivot){
        j--
      }
      if(i<=j){
        this.quickSwap(arr,i,j)
        i++
        j--
      }
    }
    return i
  }
  quickSwap(arr,index1,index2){
    let axur=arr[index1]
    arr[index1]=arr[index2]
    arr[index2]=axur
  }
}
function test(size){
  let quick=new QuickSort()
  for(let i=size;i>0;i--){
    quick.insert(i)
  }
  console.log(quick.toString())
  quick.sort()
  console.log(quick.toString())

}
test(10)

1.冒泡排序 ↩
插入排序 ↩
3.选择排序 ↩
4.归并排序 ↩
5.快速排序 ↩

最后编辑于：2020.06.07 19:00:00

2020-06-07排序笔记

一、冒泡排序[1]

二、插入排序[2]

三、选择排序[3]

四、归并排序[4]

五、快速排序[5]

一、冒泡排序^[1]

二、插入排序^[2]

三、选择排序^[3]

四、归并排序^[4]

五、快速排序^[5]