冒泡排序(Bubble_Sort)

基本思想

从数组中第一个数开始，依次遍历数组中的每一个数，通过相邻比较交换，每一轮循环下来找出剩余未排序数的中的最大数并”冒泡”至数列的顶端。

特点

数据结构：数组

稳定性：稳定

过程

初始关键字：『 6，5，3，1，8，7，2，4 』

第一趟排序：『6，5，3，1，8，7，2，4 』

5，『 6，3，1，8，7，2，4 』

5，3，『 6，1，8，7，2，4 』

5，3，1，『 6，8，7，2，4 』

5，3，1，6，『 8，7，2，4 』

5，3，1，6，7，『 8，2，4 』

5，3，1，6，7，2，『 8，4 』

5，3，1，6，7，2，4，『 8 』

第二趟排序：『 5，3，1，6，7，2，4 』，8

3，『5，1，6，7，2，4』，8

3，1，『5，6，7，2，4』，8

3，1，5，『6，7，2，4』，8

3，1，5，6，『7，2，4』，8

3，1，5，6，2，『7，4』，8

3，1，5，6，2，4，『7』，8

第三趟排序：『 3，1，5，6，2，4 』，7，8

1，『3，5，6，2，4』，7，8

1，3，『5，6，2，4』，7，8

1，3，5，『6，2，4』，7，8

1，3，5，2，『6，4』，7，8

1，3，5，2，4，『6』，7，8

第四趟排序：『 1，3，5，2，4 』，6，7，8

1，『3，5，2，4』，6，7，8

1，3，『5，2，4』，6，7，8

1，3，2，『5，4』，6，7，8

1，3，2，4，『5』，6，7，8

第五趟排序：『 1，3，2，4 』，5，6，7，8

1，『3，2，4』，5，6，7，8

1，2，『3，4』，5，6，7，8

1，2，3，『4』，5，6，7，8

第六趟排序：『 1，2，3 』，4，5，6，7，8

1，『2，3』，4，5，6，7，8

1，2，『3』，4，5，6，7，8

第七趟排序：『 1，2 』，3，4，5，6，7，8

『 1 』，2，3，4，5，6，7，8

结果：『 1，2，3，4，5，6，7，8 』

排序过程宏观过程

【复杂度与辅助空间】

最差时间复杂度：O(n^2)

最优时间复杂度：O(n)

平均时间复杂度：O(n^2)

所需辅助空间：O(1)

实现方法

双重循环，外层i控制每轮进行多少次比较，内层循环j控制每轮i次比较相邻两元素是否逆序，若逆序，则进行交换。

注：设有n个元素，则共进行n-1趟交换，设每趟趟数为i，则每趟比较n-i次。

源程序

void bubble_sort(int a[],int n){
    for (int i = 0; i < n - 1; i++){//循环的次数为数组长度减一
        for (int j = 0; j < n – 1 - i; j++){//循环次数为待排序数第一位数冒泡至最高位的比较次数
            if (a[j] > a[j + 1]){//找出未排序序列中的最小值
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
}

优化


void bubble_sort(int a[],int n)
{
    bool flag;
    for (int i = 0; i < n - 1; i++)//循环的次数为数组长度减一
    {
        flag = true;//判断是否有交换
        for (int j = 0; j < n – 1 - i; j++)//循环次数为待排序数第一位数冒泡至最高位的比较次数
            if (a[j] > a[j + 1])//找出未排序序列中的最小值
            {
                swap(a[j],a[j + 1]);
                flag = false;//有交换说明仍需排序
            }
        if (flag)    break;//若无交换，终止循环
    }
}

JAVA版本


import java.util.Arrays;

public class BubbleSort1 {
    public static void BubbleSort(int[] arr) {
        boolean flag = true;
        while(flag){
            int temp;//定义一个临时变量
            for(int i=0;i<arr.length-1;i++){//冒泡趟数，n-1趟
                for(int j=0;j<arr.length-i-1;j++){
                    if(arr[j+1]<arr[j]){
                        temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                        flag = true;
                    }
                }
                if(!flag){
                    break;//若果没有发生交换，则退出循环
                }
            }
        }
    }
    public static void main(String[] args) {
        int arr[] = new int[]{1,6,2,2,5};
        BubbleSort.BubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}