javascript冒泡排序基础及优化版

in 算法 with 0 comment

冒泡排序

排序：即把数组中每个元素找到合适自己放的位置，数组长度 - 1 个元素都找到位置了，则整个数组就有序了

冒泡排序是最基本排序之一，是一种稳定排序，其时间复杂度为 O(n²)，优化版的冒泡排序一般都是在当前元素已经比较有序的情况下，通过减少外层循环，内层循环次数提高效率，大招鸡尾酒排序（双向冒泡）一般用在比较极端情况比如元素只有一些顺序不对，其它顺序都正确的情况，本文按从小到大排序

基础版

   //**primary**
    //  for(let i = 0; i < arr.length - 1; i++) {
    //     console.log(i)
    //      for(let j = 0; j < arr.length - i - 1; j++){
    //          if(arr[j] > arr[j + 1]){
    //              let temp = arr[j + 1]
    //              arr[j + 1] = arr[j]
    //              arr[j] = temp
    //          }
    //      }
    //  }

优化外层循环版

有时元素已经有序了，但外层循环还会继续执行，这样效率就低了，通过引入isSorted变量来标识当前数组是否已经有序，从而提高效率，不过在当前数组已经有序的情况下，还是会多运行一轮

//**pro**
    for (let i = 0; i < arr.length - 1; i++) {
      //console.log(i);
      //每一轮遍历之前先check isStore状态,其实这样依然会多执行一次,因为只有执行完当前轮，才能在下一轮判断
      //那能不能在当前轮结束就进行判断，比如调用isOrder()函数进行判断
      //但这种方法要构造一个数组，并且还要调用这个函数，这些开销比多循环一次开销大多了
      let isSorted  = true; //i = 2 , 3
      for (let j = 0; j < arr.length - i - 1; j++) {
        let temp = 0;
        if (arr[j] > arr[j + 1]) {
          temp = arr[j + 1];
          arr[j + 1] = arr[j];
          arr[j] = temp;
          isSorted = false;
        }
      }
      if (isSorted) {
        break;
      }
    }

优化内层循环版

冒泡排序一般是排完一轮就确定一个有序数，即第一轮排完确定一个数的位置，第二轮排完确定二个数的位置，不过实际排序会出现有些元素已经有序了，即有序区大于排序轮数，这时可以通过确定每轮内层循环结束的索引来提高效率，即引入数组有序区域的概念，每轮循环结束，标记一下有序区的位置，下次内层循环直接比较到有序区位置即可，而不必比较到数组的长度 arr.length - i -1 这样就达到减少内层循环的目的

// **max**
     function bubbleSortMax(arr) {
       let sortedBorder = arr.length - 1
       //把lastChangeIndex放外层，不然内层每次循环都定义一个变量，浪费内存
       let lastChangeIndex = 0
       for(let i = 0; i < arr.length - 1; i++){
         let isSorted = true
         for(let j = 0; j < sortedBorder; j++){
           if(arr[j] > arr[j+1]) {
             //把temp声明放这里，只有满足条件才let temp,如果放到if外边，则每次循环都要定义一个变量，浪费内存
             let temp = arr[j]
             arr[j] = arr[j+1]
             arr[j+1] = temp
             lastChangeIndex = j
             isSorted = false
           }
         }
         //内层循环完的时候lastChangeIndex才是真正的lastChangeIndex
         sortedBorder = lastChangeIndex
         console.log('lastChangeIndex ' + lastChangeIndex)
         if(isSorted){
           break;
         }
       }
     }

鸡尾酒排序（双向排序）

试想如果一个数组只有一个元素无序，其它元素都有序 [2,3,4,5,6,7,8,1]，这时如果按照冒泡的规则两两比较，时间复杂度是o(n²), 但这种情况如果使用双向冒泡，时间复杂度可降到 O(n)

// **pro max**
function bubbleSortProMax(arr) {
       let temp = 0
       //每一轮进行左，右两次比较，因此一轮就能确定两个数的位置
       //共比较 arr.length / 2 轮就可以实现所有数排序完毕
       //每次从左到右比较j从i开始
       for(let i = 0; i < arr.length / 2; i++){
         let isSorted = true
         for(let j = i; j < arr.length - i - 1; j++){
           if(arr[j] > arr[j+1]){
             temp = arr[j]
             arr[j] = arr[j+1]
             arr[j+1] = temp
             isSorted = false
           }
         }
         if(isSorted){
           break
         }
         isSorted = true
         //每次从右往左比较 结束条件为 j > i
         for(let j = arr.length - i - 1; j > i; j--) {
           if(arr[j] < arr[j - 1]){
             temp = arr[j]
             arr[j] = arr[j - 1]
             arr[j - 1] = temp
             isSorted = false
           }
         }
         if(isSorted){
           break
         }
       }
     }

冒泡排序应用：判断数组是否有序

//判断数组是否有序 递归
    function isSorted(arr, index) {
      if(index === 1) {
        return true
      }
      return arr[index - 1] <= arr[index - 2] ? false : isSorted(arr, index - 1)
    }
    console.log(isSorted([1,2,3], 3))

 
//迭代,判断无序挺好判断
    //但判断有序就要数组中每个元素都要相邻进行比较
    //这时可想到用冒泡法外层循环判断, 有序即不会发生元素交换
    function isSorted2(arr) {
        let isSorted = true
        for(let j = 0; j < arr.length - 1; j++){
          if(arr[j] > arr[j+1]) {
            isSorted = false
          }
        }
        if(isSorted){
          return true
        }else{
          return false
        }
    }
    console.log(isSorted2([1,1,2,3,14,15,23]))

本文由 dealdot ＜dealdot＃163.com＞ 创作, Full Stack Developer @ DeepBlue
本文最后编辑时间为: Jun 10, 2021 at 17:43 pm
转载请注明来源

评论已关闭.