冒泡排序(Bubble Sort)

1.算法描述

  • 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤,除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

2.演示

2.1动图演示

图片描述

2.2具体过程

图片描述

3.代码

3.1常规

// Java program for implementation of Bubble Sort 
class BubbleSort 
{ 
    void bubbleSort(int arr[]) 
    { 
        int n = arr.length; 
        for (int i = 0; i < n-1; i++) 
            for (int j = 0; j < n-i-1; j++) 
                if (arr[j] > arr[j+1]) 
                { 
                    // swap arr[j+1] and arr[i] 
                    int temp = arr[j]; 
                    arr[j] = arr[j+1]; 
                    arr[j+1] = temp; 
                } 
    } 

    /* Prints the array */
    void printArray(int arr[]) 
    { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i] + " "); 
        System.out.println(); 
    } 

    // Driver method to test above 
    public static void main(String args[]) 
    { 
        BubbleSort ob = new BubbleSort(); 
        int arr[] = {64, 34, 25, 12, 22, 11, 90}; 
        ob.bubbleSort(arr); 
        System.out.println("Sorted array"); 
        ob.printArray(arr); 
    } 
} 
/* This code is contributed by Rajat Mishra */

3.2优化

// Optimized java implementation 
// of Bubble sort 
import java.io.*; 

class GFG 
{ 
    // An optimized version of Bubble Sort 
    static void bubbleSort(int arr[], int n) 
    { 
        int i, j, temp; 
        boolean swapped; 
        for (i = 0; i < n - 1; i++) 
        { 
            swapped = false; 
            for (j = 0; j < n - i - 1; j++) 
            { 
                if (arr[j] > arr[j + 1]) 
                { 
                    // swap arr[j] and arr[j+1] 
                    temp = arr[j]; 
                    arr[j] = arr[j + 1]; 
                    arr[j + 1] = temp; 
                    swapped = true; 
                } 
            } 

            // IF no two elements were 
            // swapped by inner loop, then break 
            if (swapped == false) 
                break; 
        } 
    } 

    // Function to print an array 
    static void printArray(int arr[], int size) 
    { 
        int i; 
        for (i = 0; i < size; i++) 
            System.out.print(arr[i] + " "); 
        System.out.println(); 
    } 

    // Driver program 
    public static void main(String args[]) 
    { 
        int arr[] = { 64, 34, 25, 12, 22, 11, 90 }; 
        int n = arr.length; 
        bubbleSort(arr, n); 
        System.out.println("Sorted array: "); 
        printArray(arr, n); 
    } 
} 
// This code is contributed 
// by Nikita Tiwari. 

4.归纳

排序方法 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度 稳定性
冒泡排序 O(n*n) O(n) O(1) 稳定

5.总结

代码简介但低效,仅用于入门。

参考:

十大经典排序算法

Bubble Sort

[冒泡排序](

评论

暂无评论