JavaScript 使用的冒泡排序算法

冒泡排序算法 是一种通过比较两个相邻元素并在它们未按照预期顺序排列时交换它们的算法。这里的顺序可以是任何增序或减序。

冒泡排序如何工作

我们有一个未排序的数组 arr = [1, 4, 2, 5, -2, 3] ，任务是使用冒泡排序将数组按升序排序。

冒泡排序比较索引为0的元素，如果0号索引值大于1号索引值，则交换这两个值；如果0号索引值小于1号索引值，则不进行任何操作。

接下来，1号索引值与2号索引值进行比较，然后2号索引值与3号索引值进行比较，依此类推…

让我们看一个示例。这里每个步骤都有简要说明：

JavaScript 使用的冒泡排序算法

在每次迭代之后，数组的最大值变为数组的最后一个索引值。在每次迭代中，比较会持续到最后一个未排序的元素。

JavaScript 使用的冒泡排序算法

语法

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);

输出：已排序的数组

[5, 6, 43, 55, 63, 234, 235, 547]

注意： 这个实现并没有进行优化。接下来我们会看到优化的解决方案。

优化的解决方案

正如我们之前讨论的冒泡排序的实现并没有进行优化一样。即使在数组已经排序的情况下，代码的复杂度仍然为O(n^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)

输出：排序后的数组