4.排序算法之一：冒泡排序

排序算法稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

冒泡排序（bubble sort）

列表中每相邻的两个数进行比较，如果前面比后面大，则交换这两个数。

一趟排序完成后，无序区减少了一个数，有序区增加了一个数。

代码关键点：总趟数（n-1），每一趟无序区范围,每一趟下标最大值为(n-i-1)

代码关键点分析：

总趟数（n-1）

无序列表：arr[n] = {val0, val1, ..., val(n-1)};

1. n = 1时，即无序列表只有1个元素，只要进行比较0趟

2. n = 2 时，即无序列表有2个元素，只要进行比较1趟

3. n = 3 时，即无序列表有3个元素，只要进行比较2趟

4. n = n 时，即无序列表有n个元素，只要进行比较 n - 1 趟

每一趟下标最大值为(n-i-1)

n = 3 时，即无序列表有3个元素，只要进行比较2趟，趟数从0开始，那么第0趟下标的最大值为n-i-1即3-0-1 = 2；

代码：

#include <iostream>using namespace std;template<typename T>
void bubble_sort(T *arr, int n)
{T temp;bool exchange;for (int i = 0; i < n-1; i++) //总趟数：n-1{exchange = false;for (int j = 0; j < n-i-1; j++) //每一趟下标最大值（即j+1这个下标的最大值）为：n-i-1{if (arr[j] > arr[j+1]){temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;exchange = true;}}if (!exchange) //一趟中，没有发生任何元素的交换，说明列表已排好序break;}
}int main(int argc, char *argv[])
{int arr[] = {3,5,2,1,4};int n = sizeof(arr)/sizeof(*arr);cout << "---before bubble sort---" << endl;for (int i = 0; i < n; i++){cout << arr[i] << " ";}cout << endl;bubble_sort(arr, n);cout << "---after bubble sort---" << endl;for (int i = 0; i < n; i++){cout << arr[i] << " ";}cout << endl;return 0;
}

结果：

时间复杂度：O()

因为冒泡排序算法，外循环对总趟数进行循环，内循环对每一趟进行循环，所以，算法时间复杂度为：O()

算法稳定性:稳定

冒泡排序算法，原无序列表中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的有序列表中，r[i]仍在r[j]之前，所以冒泡排序算法是稳定的。

ending😃