JavaScript 冒泡排序算法


prtyaa
prtyaa 2023-12-26 17:53:34 67342
分类专栏: 资讯
  • 冒泡排序算法是一种通过比较两个相邻元素来对数组进行排序的算法,如果它们没有按预期的顺序排列,则交换它们。这里的顺序可以是任何顺序,比如递增顺序或递减顺序。

    冒泡排序原理

    我们手上有一个未排序的数组 arr = [1, 4, 2, 5, -2, 3],任务是使用冒泡排序来对数组进行排序。

    冒泡排序从索引 0 开始对比元素,如果第 0 个元素比第 1 个元素大则二者交换,否则什么都不做。

    然后第 1 个索引对比第 2 个,第 2 个对比第 3 个,以此类推……

    让我们看一个例子,每一步都会展示出来

    每次迭代后,数组中最大的值会成为数组中的最后位置的元素。每次迭代中,对比过程会在到达最后未排序的元素时终止。

    迭代和元素对比完成之后,我们就得到了一个排序后的数组。

    句法

    BubbleSort(array){
      for i -> 0 to arrayLength 
         for j -> 0 to (arrayLength - i - 1)
          if arr[j] > arr[j + 1]
            swap(arr[j], arr[j + 1])
    }

    实现

    // Bubble sort Implementation using Javascript
    // Creating the bblSort function
    function bblSort(arr) {
    	
      for(var i = 0; i < arr.length; i++) {
        
        // Last i elements are already in place
        for(var j = 0; j < ( arr.length - i -1 ); j++) {
          
          // Checking if the item at present iteration
          // is greater than the next iteration
          if(arr[j] > arr[j+1]) {          
            // If the condition is true then swap them
            var temp = arr[j]
            arr[j] = arr[j + 1]
            arr[j+1] = temp
          }
        }
      }
      // Print the sorted array
      console.log(arr);
    }
      
      
    // This is our unsorted array
    var arr = [234, 43, 55, 63, 5, 6, 235, 547];
    
    // Now pass this array to the bblSort() function
    bblSort(arr);
    
    //Output 
    //Sorted array :
    //[5, 6, 43, 55, 63, 234, 235, 547]
    

    注意:这种实现方式未经优化。接下来我们看一下优化后的版本。

    优化后的方案

    我们上面讨论的冒泡排序方案是未经优化的。即使数组是排序后的,代码的运行时间仍然是 �(�2) 复杂度。我们看一下如何在 JavaScript 中实现优化后的方案。

    优化后的句法

    BubbleSort(array){
      for i -> 0 to arrayLength 
         isSwapped <- false
         for j -> 0 to (arrayLength - i - 1)
          if arr[j] > arr[j + 1]
            swap(arr[j], arr[j + 1])
            isSwapped -> true
    }

    具体实现

    // Optimized implementation of bubble sort Algorithm
    
    function bubbleSort(arr) {
    	
      var i, j;
      var len = arr.length;
        
      var isSwapped = false;
        
      for(i =0; i < len; i++){
        
        isSwapped = false;
        
        for(j = 0; j < len; j++){
          if(arr[j] > arr[j + 1]){
          var temp = arr[j]
          arr[j] = arr[j+1];
          arr[j+1] = temp;
          isSwapped = true;
          }
        }
        
        // IF no two elements were swapped by inner loop, then break
        
        if(!isSwapped){
        break;
        }
      }
        
      // Print the array
      console.log(arr)
    }
      
      
    var arr = [243, 45, 23, 356, 3, 5346, 35, 5];
    
    // calling the bubbleSort Function
    bubbleSort(arr)
    
    //Output
    //Sorted Array :
    //[3, 5, 23, 35, 45, 243, 356, 5346]
    

     

网站声明:如果转载,请联系本站管理员。否则一切后果自行承担。

本文链接:https://www.xckfsq.com/news/show.html?id=30945
赞同 0
评论 0 条