冒泡排序C++实现

比较类排序系列-冒泡排序

1. 原理

冒泡排序的核心思想是，如果有必要，不断的交换相邻的元素，让大的元素逐步向后移动，就像是水底的水泡浮出水面的过程，故称之为冒泡排序。

如下图所示

上述动图演示的为一轮冒泡排序的过程，每一轮冒泡排序，都会把未排序数据中最大的移动到最后面。相当于一轮冒泡排序给一个数据拍好序。所以一般有几个数据，就要进行对应次数的冒泡过程。

冒泡排序的优化

冒泡排序也可以进行优化，如果在某一轮冒泡的过程中，没有发生元素交换，则整个排序就结束了，剩余的冒泡过程不需要再进行了。主要的原因在于，如果在一轮冒泡的过程中，相邻元素之间没有发生交换，则说明每一个元素都大于其前面的元素，则整个数据已经有序。

2. 代码

void swap(int* array, int i, int j)
{
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}

void bubbleSort(int* array, int n)
{
int end = n;
while (end > 0)
{
//一趟排序
// flag: 1 ---->已经有序
int flag = 1;
for (int i = 1; i < end; ++i)
{
//大的向后移动， 相等的元素不会交换，相等位置不会改变
if (array[i - 1] > array[i])
{
flag = 0;
swap(array, i - 1, i);
}
}
//如果没有发生交换，说明序列元素之间就是一个递增的关系，已有序
if (flag)
break;

--end;
}
}public static void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}

public static void bubbleSort(int[] arr){
// len: 未排序的元素个数
int len = arr.length;
while(len > 0){
//flag: true ---->已经有序
boolean flag = true;
//一轮冒泡排序， 排好一个元素的位置
for(int i = 0; i < len - 1; ++i){
if(arr[i] > arr[i + 1]){
swap(arr, i, i + 1);
flag = false;
}
}
//如果没有发生交换，说明序列元素之间就是一个递增的关系，已有序
if(flag)
break;
--len;
}
}

3. 时间空间复杂度

3.1 时间复杂度

• 最坏时间复杂度：如果数据是逆序的，则每一轮的冒泡中，相邻元素都需要发生交换，需要发生交换的次数即为：1 + 2 + 3 + … + n - 1 = n(n - 1)/2 = O(n^2)。
• 最好时间复杂度：如果数据本身有序，则进行完一轮冒泡过程之后，提前结束，此时相当于只是把数据序列遍历了一遍，故时间复杂度为O(n)。
• 平均时间复杂度：O(n^2)。

3.2 空间复杂度

冒泡排序过程中，只创建了几个局部变量，故空间复杂度为O(1)。

总结

实际中，并不会使用冒泡排序进行数据排序，因为冒泡排序的时间性能比较差。