数据结构与算法.md · NinJa427/前端知识积累

# 数据结构与算法

## 排序算法

### 交换函数

```js
function swap(array,a,b){
  [array[a],array[b]] = [array[b],array[a]]
}
```

### 冒泡排序

```js
function bubbleSort(array){
  var length = array.length,i = length -1;
  if(length <= 1) return array
  while(i>=0){
    for(var j = 0; j<=length;j++){
      if(array[j]>array[j+1]){
        swap(array,j,j+1)
      }
    }
    i--;
  }
  return array
}
```

### 选择排序

```js
function selectionSort(array){
  let length = array.length;
  if(length <= 1) return array
  for(let i = 0;i<length;i++){
    let minIndex = i;
    for(let j = minIndex+1;j<length;j++){
      if(array[minIndex] < array[j]){
        minIndex = j
      }
      swap(array,minIndex,j)
    }
  }
  return array
}
```

### 插入排序

```js
function insertionSort(array){
  let length = array.length;
  if(length <= 1) return array
  for(let i=1;i<length;i++){
    for(let j = i;j>0;j--){
      if(array[j]< array[j-1]){
        swap(array,j,j-1)
      }
    }
  }
  return array
}
```

### 快速排序

```js
function quickSort(array){
  let length = array.length;
  if(length <= 1) return array
  let left = [],right = [],
      pivotIndex = Math.floor(length/2),
      pivot = array.splice(pivotIndex,1)[0];
  for(let i = 0;i<length;i++){
    if(array[i]>pivot){
      right.push(array[i])
    }else if(array[i]<pivot){
      left.push(array[i])
    }
  }
  return quickSort(left).concat(pivot,quickSort(right))
}
```

### 合并排序

## 二分查找

```js
let arr = [4, 23, 31, 45, 52, 61, 77, 89, 110]
function serach(array,x){
  let left = 0,right = array.length -1,guess = 0;
  while(left <= right){
    guess = Math.floor((left + right) / 2);
    if(array[guess] === x) return guess
    else if(array[guess] > x){
      right -= 1;
    }else {
      left += 1;
    }
  }
  return guess
}
console.log(serach(arr,77)) // 6
```

NinJa427/前端知识积累

简介

发行版

贡献者

近期动态

NinJa427/前端知识积累 .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

NinJa427/前端知识积累