冒泡排序、选择排序、插入排序一般被称作最简单的 3 种排序算法，接下来介绍三个算法的排序原理以及代码实现。

1. 冒泡排序

冒泡排序算法是一种稳定的排序算法，其算法的时间复杂度为 \(O(n^2)\)，其算法基本思想如下：

• 假设：升序排列
• 两两比较两个相邻的元素，如果第一个比第二个大，交换两个元素，这样就把大的元素放在后面，小的元素放在前面；
• 对每一对相邻元素重复上面的操作，一次循环完毕之后，将会将序列中的最大值放到序列的最后；
• 所有元素遍历一遍则确定一个最大值，直到只剩下一个元素。

#include <iostream>
using namespace std;


// 升序
void bubble_sort(int arr[], int len)
{	
	// 没有完成
	bool not_complete = true;

	for (int i = len - 1; (i > 0) && not_complete; --i)
	{
		for (int j = 0; j < i; ++j)
		{	
			// 假设已经完成
			not_complete = false;

			if (arr[j] > arr[j + 1])
			{	
				// 没有完成
				not_complete = true;
				arr[j] ^= arr[j + 1];
				arr[j + 1] ^= arr[j];
				arr[j] ^= arr[j + 1];
			}
		}
	}
}

int main()
{
	int arr[] = { 6, 8, 5, 7, 4 };
	bubble_sort(arr, sizeof(arr) / sizeof(int));
	
	for (auto v : arr) cout << v << " ";
	cout << endl;

	return 0;
}

程序输出结果：

4 5 6 7 8

2. 选择排序

选择排序不是稳定的排序算法，其算法的时间复杂度为 \(O(n^2)\)，其算法基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

#include <iostream>
using namespace std;


// 升序
void selection_sort(int arr[], int len)
{
	for (int i = 0; i < len; ++i)
	{
		// 假设 i 下标元素为最小值
		int min = i;

		for (int j = i + 1; j < len; ++j)
		{
			if (arr[j] < arr[min])
			{
				min = j;
			}
		}

		// 如果 min 不等于 i，则说明最小值不是 i, 需要交换
		if (min != i)
		{
			arr[i] ^= arr[min];
			arr[min] ^= arr[i];
			arr[i] ^= arr[min];
		}
	}
}

int main()
{
	int arr[] = { 6, 8, 5, 7, 4 };
	selection_sort(arr, sizeof(arr) / sizeof(int));

	for (auto v : arr) cout << v << " ";
	cout << endl;

	return 0;
}

程序执行结果：

4 5 6 7 8

3. 插入排序

插入序算法是一种稳定的排序算法，其算法的时间复杂度为 O(n2)，其算法基本思想如下：

每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

#include <iostream>
using namespace std;


// 升序
void insertion_sort(int arr[], int len)
{

	for (int i = 1; i < len; ++i)
	{
		if (arr[i] < arr[i - 1])
		{	
			int temp = arr[i];
			int j = i - 1;
			for (; j >= 0 && arr[j] > temp; --j)
			{
				arr[j + 1] = arr[j];
			}

			// 将 temp 插入到 j + 1 位置
			arr[j + 1] = temp;
		}
	}
}

int main()
{
	int arr[] = { 6, 8, 5, 7, 4 };
	insertion_sort(arr, sizeof(arr) / sizeof(int));

	for (auto v : arr) cout << v << " ";
	cout << endl;

	return 0;
}

程序执行结果：

4 5 6 7 8