基本排序算法

- 直接插入排序方法：从当前记录开始，逐个与前面的记录比较，若当前记录小，则把前面的记录后移一位，否则插入当前记录运行时间与待排序的记录的顺序有关时间复杂度O(n²) 稳定性：稳定代码

var arr=[8,4,5,7,1,3,6,2]
function insertionSort(arr){
  for(var i=1;i<arr.length;i++){
    var tmp=arr[i]
    for(var j=i-1;j>=0;j--){
      if(tmp>=arr[j]){break}
      arr[j+1]=arr[j]
   }
   j==-1?arr[0]=tmp:arr[j+1]=tmp
 }
}
insertionSort(arr)
console.log(arr)

- 直接选择排序
做法：一次从未排序的序列中选择最小的值，与当前元素进行交换
时间复杂度：
稳定性：不稳定 2 2 1，经过选择排序后，两个2的位置会交换
最坏情况下比较次数和交换次数：n(n-1)和2(n-1)
最坏情况的移动次数：3(n-1)代码：

var arr=[8,4,5,7,1,3,6,2]
function swap(a,i,j){
  var tmp=a[i]
  a[i]=a[j]
  a[j]=tmp
}
function selectSort(arr){
  for(var i=0;i<arr.length-1;i++){
    var min=arr[i]
    var minindex=i
    for(var j=i;j<arr.length;j++){
      if(arr[j]<min){
        min=arr[j]
        minindex=[j]
      }
   }
    // 找到最小元素后，与当前元素交换
  swap(arr,i,minindex)
}
}
selectSort(arr)
console.log(arr)

- 冒泡排序
做法：从前往后依次进行比较，若前者>后者，则交换
时间复杂度：O(n²)
稳定性：稳定
代码

var arr=[8,4,5,7,1,3,6,2]
function swap(a,i,j){
  var tmp=a[i]
  a[i]=a[j]
  a[j]=tmp
}
function bubbleSort(arr){
  
  for(var i=0;i<arr.length-1;i++){
    for(var j=0;j<arr.length;j++){
      if(arr[j]>arr[j+1]){
        swap(arr,j,j+1) //逆序交换
      }
   }
}
}
bubbleSort(arr)
console.log(arr)

- 归并排序时间复杂度：O(nlog₂n)
稳定性：稳定
特点：
运行时间与待排序中记录的顺序有关
需要与序列长度成正比的额外内存空间

var arr=[8,4,5,7,1,3,6,2]
function merge(arr,l,m,r){
  var newx=new Array(arr.length)
  var i
  var j
  // 升序排列
  for(i=m+1;i>l;i--){newx[i-1]=arr[i-1]}
  // 降序排列
  for(j=m;j<r;j++){newx[r+m-j]=arr[j+1]}
  console.log(newx,i,j)
  for(var k=l;k<=r;k++){
    if(newx[j]<newx[i]){
      arr[k]=newx[j--]
    }else{
      arr[k]=newx[i++]
    }
  }
}

function mergeSort(arr,l,r){
  if(l>=r){return}
  var m=Math.floor((l+r)/2)
  
  mergeSort(arr,l,m)
  
  mergeSort(arr,m+1,r)
  
  merge(arr,l,m,r)
}
mergeSort(arr,0,arr.length-1)

常用排序算法

基本排序算法

相关推荐