[Day22]程序菜鸟自学C++资料结构演算法 – 气泡排序法(Bubble Sort)

前言：上一篇结束了搜寻的部分，终於进入到铁人赛的最後一哩路了，之後的篇幅大概会介绍排序法的各个种类，今天就先来讲解插入排序法

在进入正题之前，先来说明一下排序的基础
资料 (Data)：只收集好但没有经过整理和分析的原始数据，也可称为资料的原始型态。电脑会将资料储存成档案，档案是一种有组织的资料，各种不同的资料组织称为资料阶层。

资料阶层 (Data Hierarchy)
可分为6个阶层，最小的存取单位是位元(8个位元唯一个位元组)，数个位元组结合成一个栏位，多个栏位组成纪录，最後再将一组纪录存成档案。

排序的方法：排序主要是处理资料阶层档案中的纪录，一纪录的某些栏位称为键值(key)，以特定规则排列成的曾获递减顺序。也就是说，排序的工作就是执行键值得比较和交换，使得键值的顺序能重新排列。

排序的种类：可分为内部排序法(Internal Sorting)和外部排序法(External Sorting)两种。内部排序法是将键值储存在电脑记忆体来执行排序；外部排序法因为键值的资料量大，无法全部储存在记忆体，所以排序过程需要使用到外部储存装置(例如硬碟等)。
这系列主要都是实作内部排序法居多。

排序的分类标准：

执行效率 (Computational Complexity)
使用时间复杂度常用的Big-O来评估执行效率，范围大约是从O(n log n)到O(n^2)。

记忆体的使用 (Memory Usage)
排序演算法所要用到的电脑资源，主要是指额外的记忆体空间。

稳定性 (Stability)
指在排序完成後，重复的键值顺序并不会改变，依然保持原顺序。
例如：1号同学A和2号同学B的成绩(键值)都是82，在排序後不会交换到资料，所以查询1号依旧会是A同学，不会变为B同学。

气泡排序法：

可以说是最出名也是相对简单的排序法了，做法非常容易记住，只需将一串数组的相邻键值进行比较，键值较小的就往前移，键值较大的就往後挪，直到没有办法再移动，就完成了。

执行效率分析：以最怀的情况来看，资料完全是相反的排序，总共需花 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 次，取最高项次n^2，所以执行效率为O(n^2)。
气泡排序不需要额外的记忆体，属於稳定性的排序法，因为键值在比较，相同键值的元素并不会交换。

实作练习：

结果出来了，跟预期的一样！

也可以将原素转换的过程印出来，这样也比较清楚真正的运作方式。

将每次转换的结果记录下来，结果如下。

但其实这样的方法不是最有效率的，假如有一段数列已经符合排序了(例如上图第四行的56,61,76,88)，但是现在写的程序码依然会检查那段有没有符合，这样会影响程序执行的效率，所以还能再修改一下程序码。

这样也会得到相同的结果，虽然这只是小程序不会有太大差别，但还是养成习惯会比较好喔！

本日小结：今天带大家认识排序法的入门阶段，讲解完基础观念和实作一个气泡排序也花了不少时间，不过繁琐的定义已经结束了，下一篇开始会开始有比较多练习，大家加油୧༼✿ ͡◕ д ◕͡ ༽୨

#include <iostream>
#include <vector>
using namespace std;

template <typename T>
void print(const vector<T>& vec) { //编写print函式，印出结果
	for (auto e : vec)
		std::cout << e << " ";
	std::cout << endl;
}

template <typename T>
void Swap(T& a, T& b) { //编写两两元素交换的方法
	T t = a;
	a = b;
	b = t;
}

template <typename T>
void bubble_sort(vector<T> & a) { //编写气泡排序
	for (int i = a.size() - 1; i > 0; i--) {
		bool swaped = false; //先建立bool类型的变数
		for (int j = 0; j < i; j++)
			if (a[j + 1] < a[j]) {
				Swap(a[j], a[j + 1]);
				swaped = true; //当有交换发生，将swaped改为true
			}
				
		print(a);
		if (!swaped) break; //若这次回圈没有交换到，代表之後的元素已排序好，可以直接退出回圈
	}
}

主程序码有许多方法可以呈现，这里就不放上来了，还是不清楚怎麽操作的参考文章内的图片