冒泡排序（Bubble Sort）
算法思想：假设待排序表长为n，从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1] > A[i]），则交换它们，直至序列比较完。
算法演示：
冒泡排序
注：图片来自冒泡排序动画演示，如若侵权请联系本人删除，谢谢！
基本代码如下：
template<typename T>
void bubbleSort(T arr[], int n) {
for (int i = 0; i < n - 1; ++i) {
// 表示本趟冒泡是否发生交换的标志
bool flag = false;
for (int j = n - 1; j > i; --j) {
if (arr[j - 1] > arr[j]) {
swap(arr[j - 1], arr[j]);
flag = true;
}
}
// 本趟遍历后没有发生交换，说明已有序
if (flag == false) return;
}
}
为了和选择排序、插入排序比较算法效率，故分别创建SelectionSort.h文件、InsertionSort.h文件，并分别添加如下代码：
// SelectionSort.h文件
#include <iostream>
using namespace std;
template<typename T>
void selectionSort(T arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// 寻找[i, n)区间里的最小值
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
if (minIndex != i)
swap(arr[i], arr[minIndex]);
}
}
// InsertionSort.h文件
#include <iostream>
using namespace std;
template<typename T>
void insertionSort(T arr[], int n) {
for (int i = 1; i < n; i++) {
// 寻找元素arr[i]合适的插入位置
T e = arr[i];
// j保存元素e应该插入的位置
int j;
for (j = i; j > 0 && arr[j - 1] > e; j--) {
arr[j] = arr[j - 1];
}
arr[j] = e;
}
}
好了，我们在main()中调用两个算法比较一下它们的性能，具体代码如下：
int main(void) {
int n = 10000;
int *arr_1 = SortTestHelper::generateRandomArray(n, 0, n);
int *arr_2 = SortTestHelper::copyIntArray(arr_1, n);
int *arr_3 = SortTestHelper::copyIntArray(arr_1, n);
SortTestHelper::testSort("Bubble Sort", bubbleSort, arr_1, n);
SortTestHelper::testSort("Insertion Sort", insertionSort, arr_2, n);
SortTestHelper::testSort("Selection Sort", selectionSort, arr_3, n);
delete[] arr_1;
delete[] arr_2;
delete[] arr_3;
return 0;
}
其运行结果如下：
Bubble Sort : 0.662 s
Insertion Sort : 0.076 s
Selection Sort : 0.151 s
从结果中，我们发现冒泡排序在随机数组的情况下运行时间是最长的。为了进一步比较该三种排序算法的效率，我们在main()中调用一个创建近乎有序的随机数组的方法，看看在该数组下三种排序算法的效率如何，具体代码如下：
int main(void) {
int n = 10000;
int *arr_1 = SortTestHelper::generateNearlyOrderdArray(n, 100);
int *arr_2 = SortTestHelper::copyIntArray(arr_1, n);
int *arr_3 = SortTestHelper::copyIntArray(arr_1, n);
SortTestHelper::testSort("Bubble Sort", bubbleSort, arr_1, n);
SortTestHelper::testSort("Insertion Sort", insertionSort, arr_2, n);
SortTestHelper::testSort("Selection Sort", selectionSort, arr_3, n);
delete[] arr_1;
delete[] arr_2;
delete[] arr_3;
return 0;
}
其运行结果如下：
Bubble Sort : 0.175 s
Insertion Sort : 0.002 s
Selection Sort : 0.194 s
此处我们从结果中不难发现，在一个近乎有序的随机数组下，冒泡排序与选择排序效率相差无几，但插入排序的运行效率远远高于前两种排序算法。因此，在处理近乎有序的数据时，我们仍然推荐插入排序算法。
