冒泡排序和递归

迈不过友情╰ 2023-01-05 05:02 142阅读 0赞

# 冒泡排序 #

1、比较相邻的两个元素，如果前一个比后一个大，则交换位置。  
2、比较完第一轮的时候，最后一个元素是最大的元素。  
3、这时候最后一个元素是最大的，所以最后一个元素就不需要参与比较大小。

### 实现原理 ###

> 数组中有`n`个数，比较每相邻两个数，如果前者大于后者，就把两个数交换位置；这样一来，第一轮就可以选出一个最大的数放在最后面；那么经过`n-1`（数组的 length - 1） 轮，就完成了所有数的排序。

##### 好的，我们先来实现找数组中的最大数，并把他放到数组最后。 #####

var arr = [3,4,1,2];
    // 遍历数组，次数就是arr.length - 1
    for (var i = 0; i < arr.length - 1; i++) { 
    	// 如果前一个数 大于 后一个数 就交换两数位置
    	if (arr[i] > arr[i + 1]) { 
    		var temp = arr[i];
    		arr[i] = arr[i + 1];
    		arr[i + 1] = temp;
    	}
    }
    console.log(arr)  // [3, 1, 2, 4]

##### 我们能找到数组中最大的数，放到最后，这样重复 arr.length - 1 次，便可以实现数组按从小到大的顺序排好了。 #####

##### 虽然上面的代码已经实现冒泡排序了，但就像注释中提到的，内层 for 循环的次数写成，i < arr.length - 1 ，是不是合适呢？ #####

##### 我们想一下，当第一次，找到最大数，放到最后，那么下一次，遍历的时候，是不是就不能把最后一个数算上了呢？因为他就是最大的了，不会出现，前一个数比后一个数大，要交换位置的情况，所以内层 for 循环的次数，改成 i < arr.length - 1 -j ，才合适，看下面的代码。 #####

##### 我们想下这个情况，当原数组是， #####

##### `arr = [1,2,4,3];` #####

##### 在经过第一轮冒泡排序之后，数组就变成了 #####

##### `arr = [1,2,3,4];` #####

##### 此时，数组已经排序完成了，但是按上面的代码来看，数组还会继续排序，所以我们加一个标志位，如果某次循环完后，没有任何两数进行交换，就将标志位 设置为 true，表示排序完成，这样我们就可以减少不必要的排序，提高性能。 #####

### 插入排序法（插队排序） ###

将要排序的数组分成两部分，每次从后面的部分取出索引最小的元素插入到前一部分的适当位置

>  *  从第一个元素开始，该元素可以认为已经被排序；
>  *  取出下一个元素，在已经排序的元素序列中从后向前扫描；
>  *  如果该元素（已排序）大于新元素，将该元素移到下一位置；
>  *  重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
>  *  将新元素插入到该位置后；
>  *  重复步骤2~5。

### 快速排序 ###

在看完上面的东西之后，不知道大家有没有发现在实际的工作中如果数据量过大，数组比较复杂，通过两次遍历，同时会带来性能上的问题，不用慌，我们还可以用快速排序的方法进行解决，`快速排序对冒泡排序的一种改进`

> 实现思路是，将一个数组的排序问题看成是两个小数组的排序问题，以一个数为基准(中间的数)，比基准小的放到左边，比基准大的放到右边，而每个小的数组又可以继续看成更小的两个数组，一直递归下去，直到数组长度大小最大为2。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dMSVVMSUFOQk8_size_16_color_FFFFFF_t_70]

### 完整代码 ###

### 性能 ###

时间复杂度： 平均时间复杂度O(n*n) 、最好情况O(n)、最差情况O(n*n)  
空间复杂度： O(1)  
稳定性： 稳定

时间复杂度指的是一个算法执行所耗费的时间  
空间复杂度指运行完一个程序所需内存的大小  
稳定指，如果a=b,a在b的前面，排序后a仍然在b的前面  
不稳定指，如果a=b，a在b的前面，排序后可能会交换位置

### 总结 ###

1、外层 for 循环控制循环次数  
2、内层 for 循环进行两数交换，找每次的最大数，排到最后  
3、设置一个标志位，减少不必要的循环

# 递归 #

js递归实现方式  
定义：  
递归函数就是在函数体内调用本函数；

递归函数的使用要注意函数终止条件避免死循环；

递归实现形式：  
1.声明一个具名函数，通过函数名调用

function f(a){ 
        if(a<=1){ 
            return 1
        }else{ 
            return a*f(a-1)
        }
    }

但是这样使用会因为 函数名 f 的变化而报错，

f = null
    f ()  // Uncaught TypeError: f is not a function

1.  使用arguments.callee代替函数名

在严格模式下不支持使用arguments.callee

3.使用函数表达式

var fun = (function f(a){ 
        if(a<=1){ 
            return 1
        }else{ 
            return a*f(a-1)
        }
    })
    
    // 或：
    
    var f = function (a){ 
        if(a<=1){ 
            return 1
        }else{ 
            return a*f(a-1)
        }
    }
    
    var fun = f;

## 递归返回值 ##

1.递归函数相当于一种循环调用，需要避免死循环，给定一个条件停止调用

2.递归函数的返回值要返回整个函数

// 返回公约数的数组集合
    let fun = (function f(a,n = 1,b=[]){ 
      if(a%n === 0) { 
         b.push(n)            
        }
       n ++;
       if(n>a){ 
       return b
     }
     return f(a,n,b) // *** 要返回整个函数，不能只是return b
    })
    调用函数
    
    fun(4)
    [1, 2, 4]

在 \*\*\* 处要返回整个函数，

这是因为当执行条件 n>a 不成立时是没有返回值的，例如，第一次执行时 n=1，a=4，1>4 为false因而没有返回值，接着之后的值也都没有返回

// 可以参考这种形式，有return fun
    fun (){ 
    return fun(){ 
     return fun(){ 
       return 4
     }
    }
    }
    
    // 可以参考这种形式，没有return fun
    fun (){ 
    fun(){ 
     fun(){ 
       return 4
     }
    }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dMSVVMSUFOQk8_size_16_color_FFFFFF_t_70]: /images/20221119/450a293beccf4806b1890754328abfdf.png