【数据结构与算法】冒泡排序算法(BubbleSort)

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】冒泡排序算法(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,数据结构与算法,排序算法 

7、总结

        这篇文章写了 BubbleSort 算法的文字描述、图示描述和代码描述。在这里为了方便实现此算法只输入了 5 个正整数。算法一般情况下具有通用性,所以这个 BubbleSort 算法可以对 n 个整数进行排序。

        各位小伙伴,也可以拷贝代码清单试试输入更多的整数(正整数,0和负整数),看看这个算法能不能对数字列表正确排序。本期的分享总结就到这里了,如果有疑问的小伙伴,我们在评论区交流嗷,笔者必回,我们下期再见啦 !

        文章来源地址https://www.toymoban.com/news/detail-775055.html

到了这里,关于【数据结构与算法】冒泡排序算法(BubbleSort)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包