js 常用排序总结(图解)

- 日理万妓 2022-11-27 06:54 10阅读 0赞

在这里插入图片描述

冒泡排序
原理:从第一个元素开始,把当前元素和下一个索引元素进行比较。如果当前元素大,那么就交换位置,重复操作直到比较到最后一个元素
在这里插入图片描述

  1. function bubbleSort(arr) {
  2. if (Array.isArray(arr)) {
  3. for (var i = arr.length - 1; i > 0; i--) {
  4. for (var j = 0; j < i; j++) {
  5. if (arr[j] > arr[j + 1]) {
  6. [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
  7. }
  8. }
  9. }
  10. return arr;
  11. }
  12. }

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

  1. function insertSort(arr) {
  2. if (Array.isArray(arr)) {
  3. for (var i = 1; i < arr.length; i++) {
  4. var preIndex = i - 1;
  5. var current = arr[i]
  6. while (preIndex >= 0 && arr[preIndex] > c) {
  7. arr[preIndex + 1] = arr[preIndex];
  8. preIndex--;
  9. }
  10. arr[preIndex + 1] = current;
  11. }
  12. return arr;
  13. }
  14. }

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

  1. function selectSort(arr) {
  2. if (Array.isArray(arr)) {
  3. for (var i = 0; i < arr.length - 1; i++) {
  4. var minIdex = i;
  5. for (var j = i + 1; j < arr.length; j++) {
  6. minIdex = arr[j] < arr[minIdex] ? j : minIdex;
  7. }
  8. [arr[i], arr[minIdex]] = [arr[minIdex], arr[i]];
  9. }
  10. return arr;
  11. }
  12. }

快速排序
原理:在数据集之中,找一个基准点,建立两个数组,分别存储左边和右边的数组,利用递归进行下次比较。
在这里插入图片描述

  1. function quickSort(arr) {
  2. if (!Array.isArray(arr)) return;
  3. if (arr.length <= 1) return arr;
  4. var left = [], right = [];
  5. var num = Math.floor(arr.length / 2);
  6. var numValue = arr.splice(num, 1)[0];
  7. for (var i = 0; i < arr.length; i++) {
  8. if (arr[i] > numValue) {
  9. right.push(arr[i]);
  10. } else {
  11. left.push(arr[i]);
  12. }
  13. }
  14. return [...quickSort(left), numValue, ...quickSort(right)]
  15. }

归并排序
原理:
(1) 把长度为n的输入序列分成两个长度为n/2的子序列;
(2)对这两个子序列分别采用归并排序;
(3) 将两个排序好的子序列合并成一个最终的排序序列。
在这里插入图片描述

  1. function mergeSort(arr) { //采用自上而下的递归方法
  2. var len = arr.length;
  3. if (len < 2) {
  4. return arr;
  5. }
  6. var middle = Math.floor(len / 2),
  7. left = arr.slice(0, middle),
  8. right = arr.slice(middle);
  9. return merge(mergeSort(left), mergeSort(right));
  10. }
  11. function merge(left, right) {
  12. var result = [];
  13. while (left.length && right.length) {
  14. // 不断比较left和right数组的第一项,小的取出存入res
  15. left[0] < right[0] ? result.push(left.shift()) : result.push(right.shift());
  16. }
  17. return result.concat(left, right);
  18. }

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

  1. //定义一个对象数组
  2. var data = [{ name: "jiang", age: 22 }, { name: "AAAAAAAAAAAAAA", age: 21 }, { name: "CCCCCCCCc", age: 25}];
  3. //定义一个比较器
  4. function compare(propertyName) {
  5. return function (object1, object2) {
  6. var value1 = object1[propertyName];
  7. var value2 = object2[propertyName];
  8. if (value2 < value1) {
  9. return -1;
  10. }
  11. else if (value2 > value1) {
  12. return 1;
  13. }
  14. else {
  15. return 0;
  16. }
  17. }
  18. }
  19. //使用方法
  20.   data.sort(compare("name"));
  21.   alert(data[0].name);//jiang
  22. //使用方法
  23.   data.sort(compare("age"));
  24.   alert(data[0].age);//25s

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

  1. function sortObj(obj) {
  2. var arr = [];
  3. for (var i in obj) {
  4. arr.push([obj[i],i]);
  5. };
  6. arr.reverse();
  7. var len = arr.length;
  8. var obj = { };
  9. for (var i = 0; i < len; i++) {
  10. obj[arr[i][1]] = arr[i][0];
  11. }
  12. return obj;
  13. }

数组排序
从小到大排序

  1. const minSort = (arr) => {
  2. let newArr = arr.sort((a,b)=>{
  3. return a - b
  4. })
  5. return newArr
  6. }

从大到小排序

  1. const maxSort = (arr) => {
  2. let newArr = arr.sort((a,b)=>{
  3. return b - a
  4. })
  5. return newArr
  6. }

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

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

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

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

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

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

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

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

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

在这里插入图片描述

发表评论

表情:
评论列表 (有 0 条评论,10人围观)

还没有评论,来说两句吧...

相关阅读