1.排序的概念及其运用

排序的概念排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

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

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断地在内外存之间移动数据的排序

今天我主要向大家介绍五种排序算法（冒泡，插入，希尔，堆，选择）

冒泡排序：

基本思想它通过重复地遍历待排序的列表，比较相邻的元素并交换它们的位置来实现排序。该算法的名称来源于较小的元素会像”气泡”一样逐渐”浮”到列表的顶端。

如上图

下面是冒泡排序代码

//冒泡
void Bubblesort(vector&t) {
	for (int i = 0; i < t.size(); i++) {
		for (int j = 0; j < t.size()-1-i; j++) {
			if (t[j] > t[j + 1]) {
				swap(t[j], t[j + 1]);
			}
		}
	}
}

插入排序：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

代码：

//插入
void insertsort(vector&t) {
	for (int i = 0; i < t.size(); i++) {
		int end = i;
		while (end > 0) {
			if (t[end] <= t[end - 1]) {
				swap(t[end], t[end - 1]);
				end--;
			}
			else {
				break;
			}
			
		}
	}
直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

希尔排序：

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序

代码：

void shellsort(vector& t) {
	int gap = t.size();
	while (gap > 1) {
		gap = gap / 3 + 1;
		for (int i = 0; i < t.size() - gap; i++) {
			int end = i;
			while (end + gap <= t.size() - 1) {
				if (t[end] >= t[end + gap]) {
					swap(t[end], t[end + gap]);
					end += gap;
				}
				else {
					break;
				}
			}
		}
	}
}
希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就
会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的
希尔排序的时间复杂度都不固定：一般认为为N^1.3左右

堆排序：在上篇文章已介绍http://www.tgwttt.xyz/?p=194这里不做过多分析

//堆排序
void adjustdown(vector& t, int number, int n) {
	int maxchild = number * 2 + 1;
	while (maxchild < n) {
		if (maxchild + 1 < n && t[maxchild] < t[maxchild + 1]) {
			maxchild++;
		}
		if (t[number] < t[maxchild]) {
			swap(t[number], t[maxchild]);
			number = maxchild;
			maxchild = number * 2 + 1;
		}
		else {
			break;
		}
	}
}
void heapsort(vector&t) {
	for(int i = (t.size() - 1 - 1) / 2; i >=0; i--) {
		adjustdown(t, i,t.size());
	}
	int end = t.size() - 1;
	while (end>0) {
		swap(t[end], t[0]);
		adjustdown(t, 0, end);
		end--;
	}
}

最后是选择排序：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
代码：

void selectsort(vector&t) {
	int begin = 0;
	int end = t.size() - 1;
	while (begin < end) {
		int min = begin;
		int max = end;
		for (int i = begin; i <= end; i++) {
			if (t[i] <= t[min]) { min = i; }
			if (t[i] >= t[max]) { max = i; }
		}
		if (max + min == t.size()-1) {
			swap(t[min], t[max]);
		}
		else {
			swap(t[min], t[begin]);
			swap(t[max], t[end]);
		}
		cout << "第i趟";
		for (auto i : t) {
			cout << i << " ";
		}
		cout << endl;
		begin++;
		end--;
	}
}

直接选择排序的特性总结：
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定