排序算法 - 简书

排序算法

冒泡排序

一句话总结：我是体育委员，双手放到两个同学头上，高的排到后面

原理：如名字一般，泡泡越往后越大，循环遍历，每次循环找出一个最大值往最后放

思路：如图，每次循环都能找出一个最大值，每次循环里需要比较所有的剩余元素，需要嵌套循环，需要循环的轮数为 (arr.length-1)，每轮比较的次数为 (arr.length-1-已经比较的轮数)，每次前元素与后元素进行比较，大则交换位置。

1.1.gif

代码：

function bubbleSort(arr){
  let x;
  for(let i=0; i<arr.length-1; i++){
    for(let j=0; j<=arr.length-i-1; j++){
      if(arr[j]>arr[j+1]){
        x = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = x;
      }
    }
  }
  return arr;
}

快速排序

原生JS自身的排序算法sort()，内部同样的是快速排序，通过传入内部函数来实现升序或降序，在实现上肯定是比我们使用的快排复杂的多，主要是做了性能上的优化，所以我们可以放心的使用Array.sort()。

那么，快排是怎么实现的呢？

一句话总结：我是体育委员，我以某某同学为基准，让比他小的去前面，比他大的去后面。

原理：快速排序的思想是使用分治法，把一个序列(list)分成较小的两个子序列，然后递归的排序两个子序列。

思路：挑选一个元素作为基准值，循环遍历整个数组，每个元素与基准值进行比较，分成两个数组，此时递归这两个数组，直到数组中的元素个数小于等于一个，此时返回该数组，组合所有数组和基准值可得到有序数组。

1.2.gif

代码：

function quickSort(arr){
    if(arr.length<=1){ return arr;}
    let leftArr = [];
    let rightArr = [];
    let pivot = arr[0];
    for(let i=1; i<arr.length; i++){
        arr[i]<pivot ? leftArr.push(arr[i]):rightArr.push(arr[i]);
    }
    return [...quickSort(leftArr),pivot,...quickSort(rightArr)];
}

那么，快排就一定快吗？

答案是不一定，有可能得到极端值，这个时候它的时间复杂度是O(n^2)，这是在悲观情况下，那么，怎么避免这种情况呢？

需要用到随机快速排序，在随机的情况下，很难每次都取得极端值。下面，我们来介绍随机快速排序。

随机快速排序

原理：采用的思想还是分治法。

思路：随机选择一个元素作为基准值，其余同快排。

代码：

function randomQuickSort(arr){
    if(arr.length<=1){ return arr;}
    let leftArr = [];
    let rightArr = [];
    let index = parseInt(Math.random()*arr.length);
    let pivot = arr.splice(index,1)[0];
    for(let i=0; i<arr.length; i++){
        arr[i]<pivot ? leftArr.push(arr[i]):rightArr.push(arr[i]);
    }
    return [...randomQuickSort(leftArr),pivot,...randomQuickSort(rightArr)];
}

选择排序

一句话总结：我是体育委员，我会找出最矮的同学，让他排在最前面，然后在剩下的同学中找出最矮的同学，让他排在最前面，以此类推。

代码：

let arr = [21,1,4,2,14,33,18];
let temp;
let index;
function selectedSort(arr){
  for(let i=0; i<arr.length; i++){
    index = i;
    for(let j=i+1; j<arr.length;j++){
      if(arr[index]>arr[j]){
        index = j;
      }
    }
    temp = arr[index];
    arr[index] = arr[i];
    arr[i] = temp;
  }
  return arr;
}
console.log(selectedSort(arr));

归并排序

一句话总结：我是体育委员，让左边一半的同学排好序，右边一半的同学排好序，然后左右merge起来

排序不会？那只有你一个人的时候，我就算你排好序了，然后我是体育委员，我只需要merge左边和右边的同学。

因为左右都是排好序的，假如左一小于右一，那么左一就是最小的，依次类推。

计数排序

一句话总结：打扑克的时候知道怎么整理抽到的牌吧，ok，你就会计数排序了。

计数排序的思路很简单，但是数据结构不同。

1.它使用到了哈希表来统计每个数字(key)出现的次数(value)

2.只遍历一遍数组(不过也要遍历一次哈希表)

3.这叫做用空间换时间