js 常用排序总结（图解）

冒泡排序
原理：从第一个元素开始，把当前元素和下一个索引元素进行比较。如果当前元素大，那么就交换位置，重复操作直到比较到最后一个元素

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

插入排序
原理：第一个元素默认为排序元素，取出下一个元素和当前元素比较，如果当前元素大就交换位置。此时第一个元素就是当前的最小数，所以下次取出操作从第三个元素开始，向前对比，重复之前的操作。

function insertSort(arr) {      if (Array.isArray(arr)) { for (var i = 1; i < arr.length; i++) {   var preIndex = i - 1;   var current = arr[i]   while (preIndex >= 0 && arr[preIndex] > c) {     arr[preIndex + 1] = arr[preIndex];     preIndex--;   }   arr[preIndex + 1] = current; } return arr;      }    }

选择排序
原理：遍历数组，设置最小值的索引为 0，如果取出的值比当前最小值小，就替换最小值索引，遍历完成后，将第一个元素和最小值索引上的值交换。如上操作后，第一个元素就是数组中的最小值，下次遍历就可以从索引 1 开始重复上述操作。

 function selectSort(arr) {      if (Array.isArray(arr)) { for (var i = 0; i < arr.length - 1; i++) {   var minIdex = i;   for (var j = i + 1; j < arr.length; j++) {     minIdex = arr[j] < arr[minIdex] ? j : minIdex;   }   [arr[i], arr[minIdex]] = [arr[minIdex], arr[i]]; } return arr;      }    }

快速排序
原理：在数据集之中，找一个基准点，建立两个数组，分别存储左边和右边的数组，利用递归进行下次比较。

function quickSort(arr) {      if (!Array.isArray(arr)) return;      if (arr.length <= 1) return arr;      var left = [], right = [];      var num = Math.floor(arr.length / 2);      var numValue = arr.splice(num, 1)[0];      for (var i = 0; i < arr.length; i++) { if (arr[i] > numValue) {   right.push(arr[i]); } else {   left.push(arr[i]); }      }      return [...quickSort(left), numValue, ...quickSort(right)]    }

归并排序
原理：
（1） 把长度为n的输入序列分成两个长度为n/2的子序列；
（2）对这两个子序列分别采用归并排序；
（3） 将两个排序好的子序列合并成一个最终的排序序列。

function mergeSort(arr) {  //采用自上而下的递归方法      var len = arr.length;      if (len < 2) { return arr;      }      var middle = Math.floor(len / 2), left = arr.slice(0, middle), right = arr.slice(middle);      return merge(mergeSort(left), mergeSort(right));    }    function merge(left, right) {      var result = [];      while (left.length && right.length) { // 不断比较left和right数组的第一项，小的取出存入res left[0] < right[0] ? result.push(left.shift()) : result.push(right.shift());      }      return result.concat(left, right);    }

按值排序对象
原理:
根据对象的某一属性进行排序,如name、age等，实例为按降序排列，若想改为升序只需把比较器中的value2-value1改为value1-value2就可以了

//定义一个对象数组var data = [{ name: "jiang", age: 22 }, { name: "AAAAAAAAAAAAAA", age: 21 }, { name: "CCCCCCCCc", age: 25}];//定义一个比较器function compare(propertyName) {return function (object1, object2) {var value1 = object1[propertyName];var value2 = object2[propertyName];  if (value2 < value1) { return -1;  }  else if (value2 > value1) {  return 1;  }  else {return 0;  } }}//使用方法　　data.sort(compare("name"));　　alert(data[0].name);//jiang//使用方法　　data.sort(compare("age"));　　alert(data[0].age);//25s

倒序排列对象
原理：
获取对象，创建临时数组存储对象数据，吧数组进行倒序排序，再创建应该obj对象来存储排序活的数据，遍历活返回。

function sortObj(obj) { var arr = []; for (var i in obj) {     arr.push([obj[i],i]); }; arr.reverse(); var len = arr.length; var obj = {}; for (var i = 0; i < len; i++) {     obj[arr[i][1]] = arr[i][0]; } return obj;    }

数组排序
从小到大排序

const minSort = (arr)  => {      let newArr =  arr.sort((a,b)=>{    return a - b})return newArr   }

从大到小排序

const maxSort = (arr)  => {      let newArr =  arr.sort((a,b)=>{    return b - a})return newArr   }

随机排序四种方法
方法一：sort
原理：
因为sort排序方法是通过回调函数的返回值来进行排序的，1是升序，-1是降序，而随机数的取值范围是0-1，所以我们将随机数-0.5，就可以得到随机的正负数。但是由于此方法是两个相邻的数进行比较，所以到后面比较的数越小，出现到概率就越大，所以概率不相同。

var arr=[1,3,4,6,8,9,7];function foo(arr){var cloneArr=arr.concat();//拷贝数组cloneArr.sort(()=>{return Math.random()-0.5;//获取-0.5 - 0.5的随机数})return cloneArr; //返回排序后的值}for(var i=0;i<10;i++){console.log(foo(arr))}

注：由于此方法实现之后的概率不相同，所以不推荐使用

方法二：递归
原理：
通过随机数随机产生数组的下标，然后通过splice截取当前随机的数放入新数组中，只要克隆的数组没有被截取完，使用arguments.callee()进行自调。

var arr=[1,3,5,6,7,9,8];function foo(arr){var cloneArr=arr.concat();//拷贝数组var result=[];(function(){if(!cloneArr.length){return;}var index=Math.floor(Math.random()*cloneArr.length)//得到从0到cloneArr.length的随机数result.push(...cloneArr.splice(index,1));arguments.callee();})()return result;}for(var i=0;i<10;i++){console.log(foo(arr))}

方法三：迭代
原理：
循环生成随机数，每生成一次随机数就作为下标，将原数拼接到新数组中去。直到原数组为空。

var arr=[1,3,5,6,7,9,8];function foo(arr){var cloneArr=arr.concat();//拷贝数组var result=[];varlen=cloneArr.length;for(var i=0;i<len;i++){var index=Math.floor(Math.random()*cloneArr.length);result=result.concat(cloneArr[index]);}return result;}for(var i=0;i<10;i++){console.log(foo(arr))}

方法四：洗牌算法
原理：
洗牌算法就是将循环的数保存下来，保存下来后就随机产生一个数，将随机产生的数赋值给前面保存的数，然后再讲前面保存的数给当前随机产生的数，最后直到将数组的长度循环完。

var arr=[1,3,5,6,7,9,8];function foo(arr){var cloneArr=arr.concat();//拷贝数组var result=[];varlen=cloneArr.length;for(var i=0;i<len;i++){var index=Math.floor(Math.random()*cloneArr.length);var temp=cloneArr[i];cloneArr[i]=cloneArr[index];cloneArr[index]=temp;}return cloneArr;}for(var i=0;i<10;i++){console.log(foo(arr))}