八大排序算法之冒泡排序

基本思想

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

算法的实现

package com.zyg.sort;

public class BubbleSortAlgorithm
{
    // 冒泡排序
    public static void bubbleSort(int a[], int len)
    {
        for (int i = 0; i < len; i++)
        {
            boolean flag = false;
            <!--more-->
            for (int j = len - 1; j > i; j--)
            {
                // 如果后面元素比元素值小，则交换，每趟排序能找出一个较小元素
                if (a[j] < a[j - 1])
                {
                    // 交换
                    swap(a, j, j - 1);
                    flag = true;
                }
            }
            // 如果一趟排序没有进行交换，表示数组已经有序，提前结束排序过程
            if (!flag)
                break;
        }
    }
    
    // 交换数组元素
    public static void swap(int a[], int i, int j)
    {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    // 打印数组
    public static void printArray(int a[])
    {
        for (int i = 0; i < a.length; i++)
        {
            System.out.println(a[i]);
        }
    }
    
    public static void main(String[] args)
    {
        // 定义初始数组
        int a[] =
        { 4, 3, 6, 7, 33, 15, 90, 65, 777, 5550 };
        // 进行冒泡排序
        bubbleSort(a, a.length);
        // 打印
        printArray(a);
    }
}

效率

时间复杂度

平均情况：O(n²)
最好情况：O(n)
最坏情况：O(n²)

空间复杂度

O(1)

稳定性

稳定