排序算法（一） 冒泡排序；选择排序；双元选择排序；插入排序；折半插入排序

• 前言
• • 说明
• 定义交换函数swap
• 冒泡排序
• • 优化
  • 复杂度
  • 代码
• 选择排序
• • 双元选择排序
  • 复杂度
  • 代码
  • • 选择排序
    • 优化双元选择排序
• 插入排序
• • 折半插入优化
  • 复杂度
  • 代码
  • • 插入排序
    • 折半插入排序

排序算法有很多种

本文主要介绍冒泡排序、选择排序和插入排序

1、我此次所有代码方法均写入SeqSort类对象中，譬如

inline void SeqSort::swap(int& x, int& y) 

在调用的时候改为即可

void swap(int& x, int& y)

2、我在定义数组的时候使用的是vector容器，这里的基础用法和int数组几乎一致，仅在获取数组长度略有差异
3、所有的排序结果均为升序排序
4、本文GIF均为网图，如有冒犯，联系速删

由于在排序是经常需要将两个数的位置进行调换，所以定义交换函数可以很有效的减少开支。
数据通过传地址的方式进行转换，可以很好地节省空间和时间，定义如下：

inline void SeqSort::swap(int& x, int& y)
{
	auto a = x;
	x = y;
	y = a;
}

对于要排序的数组，从第一位开始从前往后比较相邻两个数字，若前者大，则交换两数字位置，然后比较位向右移动一位
譬如比较数组nums[0]和nums[1]如果nums[0] > nums[1]，调换nums[0]和nums[1]

同时我们可以设置布尔值，判断某一轮的比较中，是否发生交换，如果没有发生，代表已经排序完成，可以跳出循环

时间复杂度：
双重for循环，所以总比较次数为：
n * ( n - 1 ) / 2，即为 O ( n 2 ) O(n^2) O(n2)
若输入数组已排序完成，那么最佳时间复杂度为 O ( n ) O(n) O(n)
同时，由于定义变量均为常量，所以空间复杂度为 O ( 1 ) O(1) O(1)

// 冒泡排序
// 平均时间O(n^2),最好时间O(n),最坏时间O(n^2),空间O(1)
vector SeqSort::bubbleSort(vector nums)	
{
	for (int i = 0; i < nums.size()-1; i++) {
		bool is_swap = true;
		for (int j = 0; j < nums.size() - 1 - i; j++) {
			if (nums[j] > nums[j + 1]) {
				swap(nums[j], nums[j + 1]);
				is_swap = false;
			}
		}
		if (is_swap)break;
	}
	return nums;
}

该算法的思想为每次循环寻找该循环链表中最大/最小的数字，放在循环头部
之后从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
直至循环结束

我们可以同时查找循环链表中最大和最小的数，分别放在表头和表尾部，该方法可以将遍历次数减少一半

总比较次数为 n ∗ ( n − 1 ) / 2 n * (n - 1) / 2 n∗(n−1)/2
即时间复杂度 O ( n 2 ) O(n^2) O(n2)
优化双元选择依旧为 O ( n 2 ) O(n^2) O(n2)
空间复杂度为 O ( 1 ) O(1) O(1)

// 选择排序
vector SeqSort::selectSort(vector nums)
{	
	int min_num_place;		// 存储地址
	for (int i = 0; i < nums.size(); i++) {
		min_num_place = i;	// 默认最小数地址
		for (int j = i + 1; j < nums.size()- i; j++) {
			if (nums[j] < nums[min_num_place])
				min_num_place = j;
		}
		swap(nums[i], nums[min_num_place]);
	}
	return nums;
}

// 双元选择排序
// 分别检索相对最小数和相对最大数
vector SeqSort::selectSortDouble(vector nums)
{
	int min_num_place, max_num_place;
	for (int i = 0; i < nums.size() / 2; i++) {
		min_num_place = i;						// 默认最小地址
		max_num_place = nums.size() - i - 1;	// 默认最大地址
		for (int j = i; j < nums.size() - i; j++) {
			if (nums[j] < nums[min_num_place])
				min_num_place = j;
			if (nums[j] > nums[max_num_place])
				max_num_place = j;
		}
		if (max_num_place == i)max_num_place = min_num_place;
		swap(nums[i], nums[min_num_place]);
		swap(nums[nums.size() - i - 1], nums[max_num_place]);
	}
	return nums;
}

这个算法的思想比较类似于我们打扑克牌，手里的牌都是依旧排好序的，我们拿到新牌的时候，只要在排好序的扑克牌中找到需要插入的位置插入即可
所以在实现算法的时候，初始的时候把第一个元素认为是已排好序的，从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置；重复上述过程直到最后一个元素被插入有序子数组中。

这里主要优化的地方为查找插入的位置，通过一次次的遍历，效率会比较低，可以通过二分查找的方式，将原有查找时间复杂度$O(n^2)降为O(nlogn)
二分查找的具体原理大家可以自行查阅相关资料，比较简单，就不多赘述了

时间复杂度： O ( n 2 ) O(n^2) O(n2)
最优情况： O ( n ) O(n) O(n)
空间复杂度为： O ( 1 ) O(1) O(1)

// 插入排序
vector SeqSort::insertSort(vector nums) {
	for (int i = 1; i < nums.size(); i++) {
		for (int j = i - 1; j >= 0; j--) {
			if (nums[j+1] < nums[j])
				swap(nums[j+1], nums[j]);
			else
				break;
		}
	}
	return nums;
}

// 折半插入排序
// 通过二分查找的方法找到要插入的位置
vector SeqSort::insertSortBinary(vector nums) {
	for (int i = 1; i < nums.size(); i++) {
		if (nums[i] > nums[i - 1]) continue;
		int target = nums[i];			// 要插入的节点
		int left = 0, right = i - 1;
		while (left <= right){
			if (nums[(left + right) / 2] < target)
				left = (left + right) / 2 + 1;
			else right = (left + right) / 2 - 1;
		}
		for (int j = i; j > left; j--)
			nums[j] = nums[j - 1];
		nums[left] = target;
	}
	return nums;
}