算法基础（冒泡排序跟快速排序）-一一网

冒泡排序：

冒泡排序的原理：重复的遍历要排序的数组，每次遍历过程中从头至尾比较两个相邻的元素，若顺序错误则交换两个元素。

思路：

1.冒泡排序是比较相邻位置的两个数，而选择排序是按顺序比较，找最大值或者最小值；

2.冒泡排序每一轮比较后，位置不对都需要换位置，选择排序每一轮比较都只需要换一次位置；

3.冒泡排序是通过数去找位置，选择排序是给定位置去找数；

冒泡排序优缺点：

**优点:**比较简单,空间复杂度较低，是稳定的；

**缺点:**时间复杂度太高，效率慢；

冒泡代码实现：

假设数组中有n个数，则需要n轮，而每一轮中比较的次数都要减去已经确定的数值，即第i轮需要比较的次数为：n-i，可以用一个嵌套for循环来实现。

// 冒泡排序  n 轮，n-1 次数；
var arr = [2,90,100,110,290,79,20,40]
   for(var i = 0;i<arr.length-1;i++)  {
       for (var j=0; j<arr.length-i-1; j++) {
          if(arr[j]>arr[j+1]) {  
          temp =   arr[j]    
          arr[j] = arr[j+1]  
          arr[j+1] = temp;   
          } 
   } 
    console.log("第"+ i + "次顺序" +  arr)}
复制代码

快速排序：

快速排序的原理：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按同样的方法对这两部分数据分别进行快速排序。

快速排序的思路（分治策略）

1 先从数列中取出一个数作为基准数

2将比这个属小的全放到它的左边，大于或等于它的数全放到它的右边

3 再对左右区间重复数组，直到各区间只有一个数

4 将有序的区间合并起来，这样整个数列就有序了；

快排代码实现：

let arr =[1,100,10000,200,3900,800377,900,289,989,290,387,188,288,399,400,500,800,900,10000,2999,40008]
function quickSort(arr) { 
 // 1 找基准数，比基数小的  全部放到左边（做数组） 
 //大于等于基准数的全部放到右边（右数组）// 根据基准数，左右数组放好  
let base_num = arr[0] //基准数
let left_arr = [] 
let right_arr = []  
for(let i=1;i<arr.length;i++) {  
  // 比基准数小放左数组；否则放右数组；  
  if (arr[i]<base_num) {    
     left_arr.push(arr[i]) 
   } else { 
     right_arr.push(arr[i])   
  }
  }
// 2 根据左右数组，分别进行快排序，返回排序号左右数组；// （条件：就是驻足中的元素要大于等于2个）
if(left_arr.length>=2)
 left_arr =  quickSort(left_arr)if(right_arr.length>=2) 
 right_arr =  quickSort(right_arr)
// 3  合并排序好的基准数，排序好的右数组，左数组;并且返回；
return left_arr.concat(base_num,right_arr)}
let ans = quickSort(arr)
console.log(ans);
复制代码