【数据结构与算法】冒泡排序算法（BubbleSort）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】冒泡排序算法（BubbleSort）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、缘起

2、BubbleSort 算法描述

3、用图示描述 BubbleSort 算法

4、C 语言描述

5、Python 语言描述

6、Java 语言描述

7、总结

1、缘起

冒泡排序算法 是一个非常经典的算法，它是各大网络编程平台上的座上宾，面试官口中的最爱。这个算法就是因其中数字从列表的开始向顶部移动的方式 就像水泡从水中冒出的样子 而得名，将较大的元素逐步"冒泡"到数组的顶部，从而实现排序。

虽然效率不如其他高级排序算法，但冒泡排序算法的思想易于理解和实现，是学习排序算法的入门良品。通过这篇博客让我们来翔实的了解一下冒泡排序算法吧！本篇博客所讲解的冒泡排序算法的排序为升序。

2、BubbleSort 算法描述

假设将需要排序的数字列表分成两个子列表: 已排序的 和 未排序的。在未排序子列表中，最小的元素通过冒泡的方法选出来并移到已排序子列表中。

未排序子列表 中的元素从前往后两两比较大小，如果一个元素比另外一个元素小，那么将这两个元素交换位置；否则，不进行任何处理，则进行下一次的元素两两比较；直到最大的元素排到合适的位置。最大元素排到合适的位置称之为一轮排序，一个含有N个元素的数字列表则需要 N-1轮来完成数据排序。

bubble sort,数据结构与算法,排序算法

为什么是 N-1 轮排序？当未排序子列表剩下两个元素时，只需要交换一次数据，就完成了整个原始列表的数据排序。所以排序轮数比元素的个数少1。

3、用图示描述 BubbleSort 算法

bubble sort,数据结构与算法,排序算法

注：红色方块左边为未排序元素，右边为已排序元素

第一轮，从 9 开始并把它与 5 比较，9 大于 5 则这两个元素进行位置交换。9 大于 7 则这两个元素进行位置交换。9 大于 1 则这两个元素进行位置交换。9 大于 3 则这两个元素进行位置交换，9 到达合适的位置。图中只给出了每一轮排序后的数字列表，每一轮排序的数据交换细节并没给出，我将其留给各位小伙伴作为练习。这里只详细的写了第一轮冒泡排序算法的具体过程，剩余轮数也留给各位小伙伴作为练习。

上图中，在第 3 轮后数字列表已经排好顺序了，在 4 轮不会有数据交换。如果在元素更多的情况下，在排序轮数还没达到 N-1 轮，可能整个数字列表就已经排好顺序了。如果在排序过程中，数字列表已经提前排好顺序，但是算法中没有提前结束排序的功能，那么这个算法就会跑完 N-1 轮排序才会停止。这时，冒泡排序算法的性能并不是很好。

这时，我们可以在算法中包含一个 指示器（标志位），如果在一轮排序中没有数据交换，说明整个数字列表已经排好顺序了，那就停止排序，这样可以减少冒泡排序算法的排序轮数，改善冒泡排序算法的性能。

4、C 语言描述

#include<stdio.h>

//函数声明
void BubbleSort(int* arr, int sz);

//冒泡排序法(BubbleSort)
int main()
{
	//将需要排序的数字存入数组
	int arr[] = { 5,4,3,2,1};

	//求数组中元素的个数
	int sz = (sizeof(arr) / sizeof(arr[0]));

	//将数组传入函数
	BubbleSort(arr, sz);

	//打印已排序的数组
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	
	return 0;
}	

void BubbleSort(int* arr, int sz)
{
	//确定冒泡排序的轮数
	for (int i = 0; i < sz - 1; i++)
	{
		//标志位,假设在排序过程中剩余的元素已经排好顺序了
		int flag = 1;

		//每一次冒泡排序
		for (int j = 0; j < sz - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				flag = 0;
			}
		}

		//在排序过程中已排好序了,就不会有数据交换
		//即标志位就不会重新被赋值
		if (flag == 1)
		{
			break;  //跳出排序轮数循环
		}
	}
}

bubble sort,数据结构与算法,排序算法

关键代码解释：

第二层循环判断条件：j < sz - 1 - i

表达式分两步解释

① sz - 1: 在一轮排序中，元素两两比较的次数比元素个数少1。

② -i : 减去的是已排序的元素个数，即已排序的元素不参与排序，只排未排序的元素。每一轮排序就会排好一个元素，即排序轮数和已排序元素的个数相同，所以是 -i。

5、Python 语言描述

def BubbleSort(arr):
    '''冒泡排序算法'''

    # 求数字列表中元素的个数
    sz = len(arr)

    for i in range(sz - 1):

        # 标志位，假设在排序过程中剩余的元素已经排好顺序了
        flag = 1

        for j in range(sz - i -1):
            if arr[j] > arr[j + 1]:
                arr[j],arr[j + 1] = arr[j + 1],arr[j]
                flag = 0
    
    # 在排序过程中已经排好顺序了，就不会有数据交换
    # 即标志位就不会重新被赋值
        if flag == 1:
            break


if __name__ == '__main__':
    arr = [5,4,3,2,1]
    BubbleSort(arr)
    print("排序后的数字列表")
    for i in range(len(arr)):
        print(arr[i],end = " ")

bubble sort,数据结构与算法,排序算法

6、Java 语言描述

public class BubbleSort 
{
    public static void bubbleSort(int[] arr) 
    {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) 
        {
            # 标志位，假设在排序过程中剩余的元素已经排好顺序了
            flag = 1

            for (int j = 0; j < n - i - 1; j++) 
            {
                if (arr[j] > arr[j + 1]) 
                {
                    // 数据交换
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }

        //在排序过程中已排好序了,就不会有数据交换
		//即标志位就不会重新被赋值
		if (flag == 1)
		{
			break;  //跳出排序轮数循环
		}

        }
     }

    public static void main(String[] args) 
    {
        int[] arr = {5,4,3,2,1};
        bubbleSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) 
        {
            System.out.print(arr[i] + " ");
        }
    }
}

bubble sort,数据结构与算法,排序算法