排序算法大总结

Question

排序算法大总结

JesseZhao1990 opened this issue 7 years ago · 0 comments

JesseZhao1990 commented 7 years ago

制作GIF动图的时间成本太高。制作了半张我就放弃了。于是偷懒从网上搜了一些动图。如有侵权，请联系我删除

1. 冒泡排序

时间复杂度O(n^2)，空间复杂度O(1)

冒泡排序，就是从前往后寻找，如果碰到一个更大的。就交换位置往后放。这样一遍下来，就找到了一个最大的值。并且正好这个最大值处于末尾。然后我们第二轮就从开头到倒数第二个值之间进行再次遍历，得到一个次最大值。这样一遍遍的跑。最终整个数组将是从小到大排列

动图如下：

代码如下：

var arr = [1,3,20,5,2,9,6,4,80,9,4];

var arrLength = arr.length;
for(var i=0;i<arrLength;i++){
  for(j=0;j<arrLength-i-1;j++){
    if(arr[j]>arr[j+1]){
      var temp = arr[j];
      arr[j] = arr[j+1];
      arr[j+1] = temp;
    }
  }
}
console.log(arr);

2. 选择排序

时间复杂度O(n^2)，空间复杂度O(1)

在每一遍比较中，在剩余的待比较的数中选择一个最小的数与这个剩余序列的第一个数交换位置。

动图如下：

代码如下：

var arr = [1,3,20,5,2,9,6,4,80,9,4];

var n = arr.length;
for(var i=0;i<n;i++){
  var minIndex = i;
  for(var j=i;j<n;j++){
    if(arr[j]<arr[minIndex]){
      var temp = arr[minIndex];
      arr[minIndex]=arr[j];
      arr[j] = temp;
    }
  }
}

console.log(arr);

3. 插入排序

时间复杂度O(n^2)，空间复杂度O(1)
动画演示：

代码如下：

var arr = [1,3,20,5,2,9,6,4,80,9,4];

var n = arr.length;

for(var i=1;i<n;i++){
  for(var j=i;j>0;j--){
    if(arr[j]<arr[j-1]){
      var temp = arr[j];
      arr[j] = arr[j-1];
      arr[j-1] = temp;
    }
  }
}

console.log(arr);

4.改进型的插入排序

时间复杂度略小于O(n^2)，空间复杂度O(1)

改进型的插入排序，比第三种插入排序要快很多。因为没有数据交换。我们用一个变量记录下当前要插入的值。判断这个值应该插到那个蹲。这种改进型的插入排序的动态图在网上没找到相应的图片。之后抽空我自己做一个补充上。

代码如下：

var arr = [1,3,20,5,2,9,6,4,80,9,4];

var n = arr.length;

for(var i=1;i<n;i++){
  var temp = arr[i];
  var j;
  for(j=i;j>0 && arr[j-1]>temp;j--){
    arr[j] = arr[j-1]
  }
  arr[j] = temp;
}

console.log(arr);

5. 希尔排序（优化的插入排序）

// 修改于 2019-03-06
function shellSort(arr) {
    var len = arr.length;
    for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for (var i = gap; i < len; i++) {
            var j = i;
            var current = arr[i];
            while (j - gap >= 0 && current < arr[j - gap]) {
                 arr[j] = arr[j - gap];
                 j = j - gap;
            }
            arr[j] = current;
        }
    }
    return arr;
}

6.归并排序

利用递归

var arr = [1,3,20,5,2,9,6,4,80,9,4,6];

function mergeSort(arr){
  function _merge(arr,start,middle,end){
    // 开辟临时空间，将start到end的子数组复制到此空间
    const tempArr = arr.slice(start,end+1)
    let index1 = start
    let index2 = middle+1
    for(let k=start;k<=end;k++){
      if(index1>middle){
        arr[k] = tempArr[index2-start]
        index2++
      }else if(index2>end){
        arr[k] = tempArr[index1-start]
        index1++
      }else if(tempArr[index1-start]<tempArr[index2-start]){
        arr[k] = tempArr[index1-start]
        index1++
      }else{
        arr[k] = tempArr[index2-start]
        index2++
      }
    }

  }
  // 前闭后闭
  function _mergeSort(arr,start,end){
    if(start>=end){
      return;
    }
    let middle = Math.floor((start+end)/2)
    _mergeSort(arr,start,middle)
    _mergeSort(arr,middle+1,end)
    _merge(arr,start,middle,end)
  }
   _mergeSort(arr,0,arr.length-1)
}

mergeSort(arr)
console.log(arr)

利用迭代

var arr = [1,3,20,5,2,9,6,4,80,9,4,6];

function mergeSort(arr){
  function _merge(arr,start,middle,end){
    // 开辟临时空间，将start到end的子数组复制到此空间
    const tempArr = arr.slice(start,end+1)
    let index1 = start
    let index2 = middle+1
    for(let k=start;k<=end;k++){
      if(index1>middle){
        arr[k] = tempArr[index2-start]
        index2++
      }else if(index2>end){
        arr[k] = tempArr[index1-start]
        index1++
      }else if(tempArr[index1-start]<tempArr[index2-start]){
        arr[k] = tempArr[index1-start]
        index1++
      }else{
        arr[k] = tempArr[index2-start]
        index2++
      }
    }

  }
  
  function _mergeSort(arr,n){ 
    for(var sz=1;sz<n;sz+=sz){
      for(var i=0;i+sz<n;i=i+2*sz){
        _merge(arr,i,i+sz-1,Math.min(i+sz+sz-1,n-1))
      }
    }
  }
  _mergeSort(arr, arr.length)
}

mergeSort(arr)
console.log(arr)

7.快速排序

非原地排序

var arr = [1,3,20,5,2,9,6,4,80,9,4,6];

function quickSort(arr){
  if(arr.length<=1){
    return arr;
  }
  let mid = Math.floor(arr.length/2)
  let left = [];
  let right = [];
  let middle = arr.splice(mid,1)[0];

  for(var i=0;i<arr.length;i++){
    if(arr[i]<middle){
      left.push(arr[i])
    }else{
      right.push(arr[i])
    }
  }
  return quickSort(left).concat(middle,quickSort(right))
}

console.log(quickSort(arr))

原地排序

var arr = [1,3,20,5,2,9,6,4,80,9,4,6];

function quickSort(arr){
  // 找到位置p，使得l到p-1之间的数小于arr[p],p+1到r之间的数大于arr[p]
  function partition(arr,l,r){
    let v = arr[l];
    let p =l;
    for(let i=l+1;i<=r;i++){
      if(arr[i]<v){
        let temp = arr[p+1]
        arr[p+1] = arr[i]
        arr[i] = temp
        p++
      }
    }
    let temp = arr[p]
    arr[p] = arr[l]
    arr[l] = temp
    return p
  }

  function _quickSort(arr,l,r){
    if(l>=r){
      return;
    }
    let p = partition(arr,l,r);
    _quickSort(arr,l,p-1)
    _quickSort(arr,p+1,r)
  }
  _quickSort(arr,0,arr.length-1)
}

quickSort(arr)
console.log(arr)

三路快排

var arr = [1,3,20,5,2,9,6,4,80,9,4,6];
function quickSort(arr){
  function _quickSort(arr,l,r){
    if(l>=r){
      return;
    }
    // 随机选择一个值v，然后对数组进行整理，整理的目标是
    // 把这个数组整理成三段。l到lt之间的值要小于v，lt到rt之间的值等于v，rt到r之间的值大于v

    // 因此我们分三步走
    // 1. 在l到r之间随机选择一个值v
    let index = l+Math.floor(Math.random()*(r-l))
    let v = arr[index]

    // 2. 先把v放置在l处
    let temp = arr[index];
    arr[index] = arr[l];
    arr[l] = temp;

    // 3. 开始整理
    let i = l+1;
    let lt = l;
    let rt = r;
    while(i<=rt){
      // 当arr[i]等于v的时候，i前移一步。把arr[i]纳入相等区
      if(arr[i]===v){
        i++;
      }
      // 当arr[i]小于v的时候，将arr[lt]和v的位置交换
      if(arr[i]<v){
        temp = arr[lt];
        arr[lt] = arr[i];
        arr[i] = temp;
        i++;
        lt++;
      }
      // 当arr[i]大于v的时候，将arr[i]和arr[rt]的位置交换，rt往左移一步
      if(arr[i]>v){
        temp = arr[rt];
        arr[rt]= arr[i];
        arr[i] = temp;
        rt--
      }
    }
    _quickSort(arr,l,lt-1)
    _quickSort(arr,rt+1,r)
  }
  _quickSort(arr,0,arr.length-1)
}

quickSort(arr)
console.log(arr)

8. 堆排序

方法1：普通的堆排序

const data = Symbol('data');
const count = Symbol('count');
const _shiftUp = Symbol('shiftUp');
const _shiftDown = Symbol('shiftDown');

class MaxHeap {
  constructor(){
    this[data] = [0];
    this[count] = 0;
  }
  // 公共方法：获取堆的大小
  size(){
    return this[count];
  }
  // 公共方法： 判断最大堆是否是空堆
  isEmpty(){
    return this[count] === 0
  }
  // 公共方法： 向堆中添加一个数
  insert(item){
    this[data].push(item);
    this[count]++;
    this._shiftUp(this[count]);
  }
  // 公共方法： 从堆中取出一个最大值
  extractMax(){
    if(this[count]<=0) return;
    let res = this[data][1];
    this[data][1] = this[data][this[count]];
    this[count]--;
    this._shiftDown(1)
    return res;
  }
  // 私有方法： shiftUp过程
  _shiftUp(k){
    while(k>1){
      let index = Math.floor(k/2)
      if(this[data][index]<this[data][k]){
        let temp = this[data][index];
        this[data][index] = this[data][k];
        this[data][k] = temp;
      }else{
        break;
      }
      k = Math.floor(k/2);
    }
  }
  // 私有方法： shiftDown过程
  _shiftDown(k){
    while(k*2<= this[count]){
      let j = k*2
      if(j+1<=this[count] && this[data][j+1] > this[data][j]){
        j++
      }
      if(this[data][k]>=this[data][j]) break;
      let temp = this[data][k];
      this[data][k] = this[data][j];
      this[data][j] = temp;
      k=j;
    }
  }
}

// 堆排序
let arr = [1,3,20,5,2,9,6,4,80,9,4,6];
let heap = new MaxHeap();
for(let i=0;i<arr.length;i++){
  heap.insert(arr[i])
}

for(let j=arr.length-1;j>0;j--){
  arr[j] = heap.extractMax(); 
}

console.log(arr);

方法2：经过优化的堆排序

const data = Symbol('data');
const count = Symbol('count');
const _shiftUp = Symbol('shiftUp');
const _shiftDown = Symbol('shiftDown');

class MaxHeap {
  constructor(arr){
    if(arguments.length>0 && Array.isArray(arguments[0])){
      this[data] = [0].concat(arr);
      this[count] = arr.length;
      for(let i=Math.floor(this[count]/2); i>1 ;i--){
        this._shiftDown(i);
      }
    }else{
      this[data] = [0];
      this[count] = 0;
    }
  }
  // 公共方法：获取堆的大小
  size(){
    return this[count];
  }
  // 公共方法： 判断最大堆是否是空堆
  isEmpty(){
    return this[count] === 0
  }
  // 公共方法： 向堆中添加一个数
  insert(item){
    this[data].push(item);
    this[count]++;
    this._shiftUp(this[count]);
  }
  // 公共方法： 从堆中取出一个最大值
  extractMax(){
    if(this[count]<=0) return;
    let res = this[data][1];
    this[data][1] = this[data][this[count]];
    this[count]--;
    this._shiftDown(1)
    return res;
  }
  // 私有方法： shiftUp过程
  _shiftUp(k){
    while(k>1){
      let index = Math.floor(k/2)
      if(this[data][index]<this[data][k]){
        let temp = this[data][index];
        this[data][index] = this[data][k];
        this[data][k] = temp;
      }else{
        break;
      }
      k = Math.floor(k/2);
    }
  }
  // 私有方法： shiftDown过程
  _shiftDown(k){
    while(k*2<= this[count]){
      let j = k*2
      if(j+1<=this[count] && this[data][j+1] > this[data][j]){
        j++
      }
      if(this[data][k]>=this[data][j]) break;
      let temp = this[data][k];
      this[data][k] = this[data][j];
      this[data][j] = temp;
      k=j;
    }
  }
}

// 经过优化的堆排序
let arr = [1,3,20,5,2,9,6,4,80,9,4,6];
let heap = new MaxHeap(arr);

for(let j=arr.length-1;j>0;j--){
  arr[j] = heap.extractMax(); 
}

console.log(arr);

方法3：原地的堆排序

 

function heapSort(arr){

  function _heapSort(arr,n){
    // heapify
    for(let i=Math.floor((n-1)/2);i>=0;i--){
      _shiftDown(arr,n,i);
    }
    //
    for(let j = n-1;j>0; ){
      var temp = arr[0];
      arr[0] = arr[j];
      arr[j] = temp;
      j--
      _shiftDown(arr,j,0)
    }
  }

  function _shiftDown(arr,n,k){
    while(2*k+1 <n){
      let j = 2*k+1
      if(j+1<n && arr[j]< arr[j+1]){
        j++
      }
      if(arr[k]>arr[j]){
        break;
      }
      let temp = arr[k];
      arr[k] = arr[j];
      arr[j] = temp;
      k=j
    }
  }

  _heapSort(arr,arr.length);

}

let arr = [1,3,20,5,2,9,6,4,80,9,4,6];
heapSort(arr);
console.log(arr);

1. 冒泡排序

2. 选择排序

3. 插入排序

4.改进型的插入排序

5. 希尔排序（优化的插入排序）

6.归并排序

7.快速排序

8. 堆排序

9.利用二分搜索树进行排序