综述

冒泡排序是一种简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来.
走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端.

算法描述

1.比较相邻的元素.如果前一个比后二个大,就交换它们两个;
2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
3.针对所有的元素重复以上的步骤,除了最后一个;
4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较.

示意图

动态示意图

静态示意图

性质

排序类别:交换排序
是否是稳定排序:稳定
是否是原地排序:是
时间复杂度:O(N^2)
空间复杂度:O(1)

要点

冒泡排序是一种交换排序.
交换排序:两两比较待排序的关键字,并交换不满足次序要求的那对数,直到整个表都满足次序要求为止.

算法思想

它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端,故名冒泡排序.

假设有一个大小为 N 的无序序列.冒泡排序就是要每趟排序过程中通过两两比较,找到第 i 个小(大)的元素,将其往上排.
要将以上流程转化为代码,我们需要像机器一样去思考,不然编译器可看不懂.
假设要对一个大小为 N 的无序序列进行升序排序(即从小到大).
(1)每趟排序过程中需要通过比较找到第 i 个小的元素.
所以,我们需要一个外部循环,从数组首端(下标 0)开始,一直扫描到倒数第二个元素(即下标 N - 2),剩下最后一个元素,必然为最大.
(2)假设是第 i 趟排序,可知,前 i-1 个元素已经有序.现在要找第 i 个元素,只需从数组末端开始,扫描到第 i 个元素,将它们两两比较即可.
所以,需要一个内部循环,从数组末端开始(下标 N - 1),扫描到(下标 i + 1).

时间复杂度分析

1.若文件的初始状态是正序的,一趟扫描即可完成排序.所需的关键字比较次数C和记录移动次数M均达到最小值:Cmin=N-1, Mmin=0.所以,冒泡排序最好时间复杂度为O(N).
2.若初始文件是反序的,需要进行 N -1 趟排序.每趟排序要进行(N-i)次关键字的比较(1 ≤ i ≤ N - 1),且每次比较都必须移动记录三次来达到交换记录位置.
在这种情况下,比较和移动次数均达到最大值:
Cmax = N(N-1)/2 = O(N^2)
Mmax = 3N(N-1)/2 = O(N^2)
冒泡排序的最坏时间复杂度为O(N^2).

因此,冒泡排序的平均时间复杂度为O(N^2).

总结起来,其实就是一句话:当数据越接近正序时,冒泡排序性能越好.

稳定性分析

冒泡排序就是把小的元素往前调或者把大的元素往后调.比较是相邻的两个元素比较,交换也发生在这两个元素之间.
所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法.

优化方式

优化一

假设我们现在排序ar[]={1,2,3,4,5,6,7,8,10,9}这组数据,按照上面的排序方式,第一趟排序后将10和9交换已经有序,接下来的8趟排序就是多余的,什么也没做.所以我们可以在交换的地方加一个标记,如果那一趟排序没有交换元素,说明这组数据已经有序,不用再继续下去.

优化二

优化一仅仅适用于连片有序而整体无序的数据(例如:1, 2,3,4,7,6,5).但是对于前面大部分是无序而后边小半部分有序的数据(1,2,5,7,4,3,6,8,9,10)排序效率也不可观,对于种类型数据,我们可以继续优化:即我们可以记下最后一次交换的位置,后边没有交换,必然是有序的,然后下一次排序从第一个比较到上次记录的位置结束即可.

优化三

优化二的效率有很大的提升,还有一种优化方法可以继续提高效率.大致思想就是一次排序可以确定两个值,正向扫描找到最大值交换到最后,反向扫描找到最小值交换到最前面.
例如:排序数据1,2,3,4,5,6,0

Python实现及优化

def bubblesort1(dest_list=[]):
    if len(dest_list) <= 1:
        return dest_list

    for i in range(len(dest_list) - 1):
        print('第{}趟排序为:'.format(str(i + 1)))
        for j in range(len(dest_list) - 1 - i):
            print('第{}次排序为:'.format(str(j + 1)), dest_list)
            if dest_list[j] > dest_list[j + 1]:
                dest_list[j], dest_list[j + 1] = dest_list[j + 1], dest_list[j]
    return dest_list

dest = [5, 3, 4, 6, 2, 1, 7]
result = bubblesort1(dest)
print('最后的结果是:', result)

'''
第1趟排序为:
第1次排序为: [5, 3, 4, 6, 2, 1, 7]
第2次排序为: [3, 5, 4, 6, 2, 1, 7]
第3次排序为: [3, 4, 5, 6, 2, 1, 7]
第4次排序为: [3, 4, 5, 6, 2, 1, 7]
第5次排序为: [3, 4, 5, 2, 6, 1, 7]
第6次排序为: [3, 4, 5, 2, 1, 6, 7]
第2趟排序为:
第1次排序为: [3, 4, 5, 2, 1, 6, 7]
第2次排序为: [3, 4, 5, 2, 1, 6, 7]
第3次排序为: [3, 4, 5, 2, 1, 6, 7]
第4次排序为: [3, 4, 2, 5, 1, 6, 7]
第5次排序为: [3, 4, 2, 1, 5, 6, 7]
第3趟排序为:
第1次排序为: [3, 4, 2, 1, 5, 6, 7]
第2次排序为: [3, 4, 2, 1, 5, 6, 7]
第3次排序为: [3, 2, 4, 1, 5, 6, 7]
第4次排序为: [3, 2, 1, 4, 5, 6, 7]
第4趟排序为:
第1次排序为: [3, 2, 1, 4, 5, 6, 7]
第2次排序为: [2, 3, 1, 4, 5, 6, 7]
第3次排序为: [2, 1, 3, 4, 5, 6, 7]
第5趟排序为:
第1次排序为: [2, 1, 3, 4, 5, 6, 7]
第2次排序为: [1, 2, 3, 4, 5, 6, 7]
第6趟排序为:
第1次排序为: [1, 2, 3, 4, 5, 6, 7]
最后的结果是: [1, 2, 3, 4, 5, 6, 7]
'''

"""
优化方式一
对冒泡排序常见的改进方法是加入标志性变量exchange,用于标志某一趟排序过程中是否有数据交换。
如果进行某一趟排序时并没有进行数据交换,则说明所有数据已经有序,可立即结束排序,避免不必要的比较过程。
"""


def bubblesort2(dest_list=[]):
    if len(dest_list) <= 1:
        return dest_list

    for i in range(len(dest_list)):
        exchange = False
        print('第{}趟排序:'.format(str(i + 1)))
        for j in range(len(dest_list) - 1 - i):
            print('第{}次排序为:'.format(str(j + 1)), dest_list)
            if dest_list[j] > dest_list[j + 1]:
                dest_list[j], dest_list[j + 1] = dest_list[j + 1], dest_list[j]
                exchange = True
        if not exchange:
            break

    return dest_list

dest = [2, 1, 4, 3, 5, 6, 7]
result = bubblesort2(dest)
print('最后的结果是:', result)

'''
第1趟排序:
第1次排序为: [2, 1, 4, 3, 5, 6, 7]
第2次排序为: [1, 2, 4, 3, 5, 6, 7]
第3次排序为: [1, 2, 4, 3, 5, 6, 7]
第4次排序为: [1, 2, 3, 4, 5, 6, 7]
第5次排序为: [1, 2, 3, 4, 5, 6, 7]
第6次排序为: [1, 2, 3, 4, 5, 6, 7]
第2趟排序:
第1次排序为: [1, 2, 3, 4, 5, 6, 7]
第2次排序为: [1, 2, 3, 4, 5, 6, 7]
第3次排序为: [1, 2, 3, 4, 5, 6, 7]
第4次排序为: [1, 2, 3, 4, 5, 6, 7]
第5次排序为: [1, 2, 3, 4, 5, 6, 7]
最后的结果是: [1, 2, 3, 4, 5, 6, 7]
'''

"""
优化方式二
优化一仅仅适用于连片有序而整体无序的数据(例如：1, 2,3 ,4 ,7,6,5)。
但是对于前面大部分是无序而后边小半部分有序的数据(1,2,5,7,4,3,6,8,9,10)排序效率也不可观,对于这种类型数据,我们可以继续优化。
我们可以记下最后一次交换的位置,后边没有交换,必然是有序的,然后下一次排序从第一个比较到上次记录的位置结束即可。
"""


def bubblesort3(dest_list=[]):
    if len(dest_list) <= 1:
        return dest_list

    k = len(dest_list) - 1  # 确定比较次数
    for i in range(len(dest_list)):
        exchange = False
        pos = 0  # 用来记录最后一次交换的位置
        print('第{}趟排序:'.format(str(i + 1)))
        for j in range(k):
            print('第{}次排序为:'.format(str(j + 1)), dest_list)
            if dest_list[j] > dest_list[j + 1]:
                dest_list[j], dest_list[j + 1] = dest_list[j + 1], dest_list[j]
                exchange = True
                pos = j  # 交换元素,记录最后一次交换的位置
        if not exchange:  # 如果没有交换过元素,则已经有序
            break
        k = pos  # 下一次比较到记录位置即可

    return dest_list

dest = [2, 1, 4, 3, 5, 6, 7]
result = bubblesort3(dest)
print('最后的结果是:', result)

'''
第1趟排序:
第1次排序为: [2, 1, 4, 3, 5, 6, 7]
第2次排序为: [1, 2, 4, 3, 5, 6, 7]
第3次排序为: [1, 2, 4, 3, 5, 6, 7]
第4次排序为: [1, 2, 3, 4, 5, 6, 7]
第5次排序为: [1, 2, 3, 4, 5, 6, 7]
第6次排序为: [1, 2, 3, 4, 5, 6, 7]
第2趟排序:
第1次排序为: [1, 2, 3, 4, 5, 6, 7]
第2次排序为: [1, 2, 3, 4, 5, 6, 7]
最后的结果是: [1, 2, 3, 4, 5, 6, 7]
'''

"""
优化方式三
大致思想就是一次排序可以确定两个值,正向扫描找到最大值交换到最后,反向扫描找到最小值交换到最前面。
"""


def bubblesort4(dest_list=[]):
    if len(dest_list) <= 1:
        return dest_list

    k = len(dest_list) - 1  # 确定比较次数
    n = 0  # 同时找最大值的最小需要两个下标遍历
    for i in range(len(dest_list)):
        exchange = False
        pos = 0  # 用来记录最后一次交换的位置
        print('第{}趟排序:'.format(str(i + 1)))
        for j in range(n, k):
            if dest_list[j] > dest_list[j + 1]:
                dest_list[j], dest_list[j + 1] = dest_list[j + 1], dest_list[j]
                exchange = True
                pos = j  # 交换元素,记录最后一次交换的位置
            print('第{}次排序为:'.format(str(j + 1)), dest_list)
        if not exchange:  # 如果没有交换过元素,则已经有序
            break
        k = pos  # 下一次比较到记录位置即可

        # print('进行倒序寻找...')

        for m in range(k, n, -1):
            if dest_list[m] < dest_list[m - 1]:
                dest_list[m], dest_list[m - 1] = dest_list[m - 1], dest_list[m]
                exchange = True
            # print('第{}次排序为:'.format(str(k - n - m + 1)), dest_list)
        n += 1
        if not exchange:  # 如果没有交换过元素,则已经有序
            break

    return dest_list

dest = [1, 2, 3, 4, 5, 6, 0]
result = bubblesort4(dest)
print('最后的结果是:', result)


'''
第1趟排序:
第1次排序为: [1, 2, 3, 4, 5, 6, 0]
第2次排序为: [1, 2, 3, 4, 5, 6, 0]
第3次排序为: [1, 2, 3, 4, 5, 6, 0]
第4次排序为: [1, 2, 3, 4, 5, 6, 0]
第5次排序为: [1, 2, 3, 4, 5, 6, 0]
第6次排序为: [1, 2, 3, 4, 5, 0, 6]
第2趟排序:
第2次排序为: [0, 1, 2, 3, 4, 5, 6]
第3次排序为: [0, 1, 2, 3, 4, 5, 6]
第4次排序为: [0, 1, 2, 3, 4, 5, 6]
第5次排序为: [0, 1, 2, 3, 4, 5, 6]
最后的结果是: [0, 1, 2, 3, 4, 5, 6]
'''

C语言实现及优化

#include <stdio.h>


/* 1.从当前元素起,向后依次比较每一对相邻元素,若逆序则交换 */
/* 2.对所有元素均重复以上步骤,直至最后一个元素 */
void bubbleSort(int arr[],int len)
{
    int i = 0;
    int count = 0;
    int tmp = 0;
    for(i = 0; i < len - 1; i++)//确定排序趟数
    {
        int j = 0;
        for(j = 0; j < len - 1 - i; j++)//确定比较次数
        {
            if(arr[j]>arr[j + 1])
            {
                //交换
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                count ++;
            }
        }
    }
    printf("最后交换的次数是:%d\n", count);
}

/*
优化一
假设我们现在排序ar[]={1,2,3,4,5,6,7,8,10,9}这组数据,按照上面的排序方式,第一趟排序后将10和9交换已经有序,接下来的8趟排序就是多余的,什么也没做.
所以我们可以在交换的地方加一个标记,如果那一趟排序没有交换元素,说明这组数据已经有序,不用再继续下去.
*/

void bubbleSort2(int arr[], int len)
{
    int i=0, j=0, count=0;
    for(i=0;i<len;i++)             /* 外循环为排序趟数,len个数进行len-1趟 */
    {
        int flag = 0;
        for(j=0;j<len-i-1;j++)     /* 内循环为每趟比较的次数,第i趟比较len-i次 */
        {
            if(arr[j]>arr[j+1])    /* 相邻元素比较,若逆序则交换(升序为左大于右,降序反之)*/
            {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                flag = 1;
                count ++;
            }
        }

        if(flag)
            printf("最后交换的次数是:%d\n", count);
            return;
    }
    printf("最后交换的次数是:%d\n", count);
}

/*
优化二
优化一仅仅适用于连片有序而整体无序的数据(例如:1, 2,3,4,7,6,5).
但是对于前面大部分是无序而后边小半部分有序的数据(1,2,5,7,4,3,6,8,9,10)排序效率也不可观,对于种类型数据,我们可以继续优化.
既我们可以记下最后一次交换的位置,后边没有交换,必然是有序的,然后下一次排序从第一个比较到上次记录的位置结束即可.
*/
void bubbleSort3(int arr[], int len)
{
    int i = 0;
    int count = 0;
    int tmp = 0;
    int flag = 0;
    int pos = 0;//用来记录最后一次交换的位置
    int k = len - 1;
    for(i = 0; i < len - 1; i++)//确定排序趟数
    {
        pos = 0;
        int j = 0;
        flag = 0;
        for(j = 0; j < k; j++)//确定比较次数
        {
            if(arr[j]>arr[j + 1])
            {
                //交换
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                flag = 1;//加入标记
                pos = j;//交换元素,记录最后一次交换的位置
                count ++;
            }
        }

        if(flag == 0)//如果没有交换过元素,则已经有序
        {
            printf("最后交换的次数是:%d\n", count);
            return;
        }
        k = pos;//下一次比较到记录位置即可
    }
    printf("最后交换的次数是:%d\n", count);
    return;
}


/*
优化三
优化二的效率有很大的提升,还有一种优化方法可以继续提高效率.
大致思想就是一次排序可以确定两个值,正向扫描找到最大值交换到最后,反向扫描找到最小值交换到最前面.例如:排序数据1,2,3,4,5,6,0
*/

void bubbleSort4(int arr[], int len)
{
    int i = 0;
    int j = 0;
    int n = 0;//同时找最大值的最小需要两个下标遍历
    int flag = 0;
    int pos = 0;//用来记录最后一次交换的位置
    int k = len - 1;
    for(i = 0; i < len - 1; i++)//确定排序趟数
    {
        pos = 0;
        flag = 0;
        //正向寻找最大值
        for(j = n; j < k; j++)//确定比较次数
        {
            if(arr[j]>arr[j + 1])
            {
                //交换
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                flag = 1;//加入标记
                pos = j;//交换元素,记录最后一次交换的位置
            }
        }
        if(flag == 0)//如果没有交换过元素,则已经有序,直接结束
        {
            return;
        }
        k = pos;//下一次比较到记录位置即可
        //反向寻找最小值
        for(j = k; j > n; j--)
        {
            int tmp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = tmp;
            flag = 1;
        }
        n++;
        if(flag == 0)//如果没有交换过元素,则已经有序,直接结束
        {
            return;
        }
    }
}




int main()
{
    int i=0;

    int dest[] = { 1, 2, 5, 7, 4, 3, 6, 8, 9, 10 };
    bubbleSort(dest, 7);
    for(i=0;i<7;i++)
        printf("%d ", dest[i]);
    printf("\n");

    int dest1[] = { 1, 2, 5, 7, 4, 3, 6, 8, 9, 10 };
    bubbleSort2(dest1, 7);
    for(i=0;i<7;i++)
        printf("%d ", dest1[i]);
    printf("\n");

    int dest2[] = { 1, 2, 5, 7, 4, 3, 6, 8, 9, 10 };
    bubbleSort3(dest2, 10);
    for(i=0;i<10;i++)
        printf("%d ", dest2[i]);
    printf("\n");

    int dest3[] = { 1, 2, 5, 7, 4, 3, 6, 8, 9, 10 };
    bubbleSort4(dest2, 10);
    for(i=0;i<10;i++)
        printf("%d ", dest3[i]);
    printf("\n");

    return 0;
}