【数据结构周周练】033 冒泡排序算法原理详解及代码分享

ゝ一世哀愁。 2021-06-11 15:13 334阅读 0赞

## 一、冒泡排序 ##

### 1、冒泡排序简介 ###

从今天开始给大家分享几个经典的交换排序算法，今天是冒泡排序（Bubble Sort），它是一种比较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（从大到小，或从小到大，这个大小不仅仅是数值的大小，还包括位置的先后）倒置，就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

主要有下面三个步骤：

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

这个算法原理是也是比较简单的，同时是一个稳定的算法。这个算法适用于顺序表和链表，本次以数组为例介绍，因为核心是算法本身，而不是采用什么数据结构，如果大家有兴趣，可以尝试一下哦，**该算法的比较次数与排序表的初始状态有关**，**我们设置一个flag，如果在一趟排序过程中，没有交换，说明就无需再进行剩下的比较了，所以，如果排序表是一个已经排好序的表，只需要比较一轮就可以完成**。非常棒的一个算法，希望大家能够掌握。

### 2、算法思想及流程 ###

排序时，从第一个数据开始，与其后一个数据作比较。主要做如下几个步骤：

1.定义一个中间变量和一个flag，中间变量用来交换，flag用来判断在一轮比较中是否交换，交换为0，未交换为1，这样设置主要是为方便后面代码。

2.如果该数据比后面数据大，用中间变量交换两个数据。并将flag置为0。

3.同样方法接着比较下一论，每比较一次，最后一个数据就是最大值，所以每一轮比较次数都要-1。

## 二、全部代码 ##

刚才上面是分析，接下来我将所有的代码分享一下。

#include<iostream>
    using namespace std;
    
    void BubbleSort(int Arr[], int length) {
    	int temp;
    	int flag;
    	for (int i = 0; i < length - 1; i++)
    	{
    		flag = 1;
    		for (int j = 0; j < length - i - 1; j++)
    		{
    			if (Arr[j] > Arr[j + 1])
    			{
    				temp = Arr[j];
    				Arr[j] = Arr[j + 1];
    				Arr[j + 1] = temp;
    				flag = 0;
    			}
    		}
    		if (flag)
    			return;
    	}
    }
    
    void OutputArr(int Arr[], int length) {
    	for (int i = 0; i < length; i++)
    	{
    		cout << Arr[i] << ", ";
    
    	}
    	cout << endl;
    }
    
    void main() {
    	int Arr[] = { 45,57,12,31,1,60,92,71,87 };
    	BubbleSort(Arr, 9);
    	OutputArr(Arr, 9);
    }

## 三、运行结果 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_25_color_2F9790_t_70][]

大家有什么问题在下面留言哦！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_25_color_2F9790_t_70]: /images/20210516/281e8b6fb71444158a3f0eb421e7d267.png