冒泡排序

需求

使用冒泡排序对一个数组进行排序。

实现思路

首先看冒泡排序的规则：

相邻两个元素之间一一比较，出现有前一个值比后一个值大的情况，就交换两个元素的位置，没执行完一轮就有一个最大值（最小值）冒出来，直到最后顺序排列。

这个动图看着很直观，但是却不能很形象的解决问题。这个问题的难点在于到底要比较多少次，每次应该需要多少个元素比较。

下图是我简化了数组个数，画的冒泡排序的图解。

如上图所示，我们不难得出：

• 1.冒泡排序排序前的数组个数与第几轮比较和每轮比较次数之间的关系。即

数组个数 = 第几轮比较 + 每轮比较的次数;

• 2.每轮比较都会挑选出一个最值，这里升序以最大值为例。选出之后下一轮就不再比较。这就是冒泡排序所谓的冒泡特征，每轮冒出一个最值。

  • 通过上面第一点，我们不难想出，使用两个for循环嵌套完成冒泡排序，外层循环掌管第几轮比较，内层循环掌管每轮比较的次数。
  • 通过上面第二点，又可以知道，从低到高两两比较，挑出一个最值，两两之间比较要交换位置时，会用到一个temp中间值存储零时变量。

代码实现

代码如下：我将在bubbleSort 函数中，使用两个形参，一个是数组指针，另外一个是数组长度。这是用户使用时，需要传递的参数。

int * bubbleSort(int * parray,int length)
{
	//外层循环：第几轮比较
	for(int i=1; i<length; i++)
	{
		//内层循环：每轮怎么比较
		for(int j=0; j<length-i; j++)
		{
			if(*(parray+j) > *(parray+j+1))
			{
				int temp = *(parray+j);
				*(parray+j) = *(parray+j+1);
				*(parray+j+1) = temp;
			}
		}
	}
	return parray;
}

完整的示例代码如下：

其中，我将交换的代码封装成了swap函数。

#include "iostream"
#include "cstdlib"

//函数原型
int * bubbleSort(int *,int);
void swap(int *,int *);

int main()
{
	//动态生成一个int类型的数组
	int n = 10;
	int *array = new int[n];

	std::cout << "执行冒泡排序前动态生成的数组是：" << std::endl;
	for(int i=0; i<n; i++)
	{
		// rand() 生成的随机数一般是几万
		// 这里除1000取余+1，生成0-1000的随机数
		array[i] = (rand()%1000)+1;
		std::cout << "array[" << i << "]=" << array[i] << std::endl; 
	}

	std::cout << "--------------------------------" << std::endl;

	bubbleSort(array, n);

	std::cout << "执行冒泡排序后的数组改变成了：" << std::endl;
	for(int i=0; i<n; i++)
	{
		std::cout << "array[" << i << "]=" << array[i] << std::endl; 
	}
	//清理数组内存
	delete []array;
	return 0;
}

// 这里排序是升序排序
int * bubbleSort(int *parray,int length)
{
	for(int i=0; i<length-1; i++)		// 比较 length-1 轮
	{
		for(int j=0; j<length-i-1; j++)	// 每轮要比较的元素
		{
			if(parray[j] > parray[j+1])
			{
				swap(&parray[j],&parray[j+1]);
			}
		}
	}
	return parray;
}

// -- Swap 交换 A，B
void swap(int *A,int *B)
{
	int temp = *A;
	*A = *B;
	*B = temp;
}