浅谈数据结构排序算法中的冒泡排序

        数据结构中的排序算法有：插入类排序、交换类排序、选择排序、堆排序、归并排序、桶排序。而交换类排序包括：冒泡排序和快速排序。

其中：冒泡排序（稳定的排序）

注：下列改进的冒泡排序是从小到大排序

#include <iostream>
#include <stdbool.h>
using namespace std;
#define ElemType int
ElemType A[] = {9,7,8,5,6,4,3,2,1,0};
void BubbleSort(ElemType A[], int n)
{
	bool flag = true;//设定标志位flag，用于判断是否排序完成
	int i, j;
	ElemType temp;//定义中间变量temp，用于暂存要排序的数组元素的值
	for (i = 0;i < n-1 ;i++)//循环执行n-2次，最后一次肯定有序，没必要执行n-1次
	{
		flag = false;//先将标志位置为假
		for (j = n - 1;j > i;j--)//从后向前冒泡
		{
			if (A[j - 1] > A[j])//if前面的元素值比后面的大
			{
				temp = A[j - 1];//执行交换操作
				A[j - 1] = A[j];
				A[j] = temp;
				flag = true;//如果发生数据交换，则将标志位flag置为真
			}
		}
		if (flag == false)//标志位flag为假，代表本轮for循环没有发生交换，因为是从后向前冒泡，所以此时该位置前的元素其实已经是有序的了
			return;//说明已经排序好了，没必要再进行for循环了
		cout << "第" << i<<"次排序：";
		for (int x = 0;x < n;x++)
			cout << A[x] << "  ";
		cout << endl;
	}
	cout <<"排序完成！！！"<< endl;
}
int main()
{	
	int n = size(A);
	cout << "当前数组A[]的元素个数为："<< n<<endl;
	BubbleSort(A, n);//执行冒泡排序子函数
}

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

空间复杂度：O(1)        注：temp变量（常数个空间）

赏

谢谢你请我吃糖果！

微信