冒泡排序
冒泡排序的思想是每一趟排序都将最值放到最右边，比如现在要排的是升序，则一趟冒泡排序就可以将最大值放到右边，每一趟都将剩余数的最大值放到最右边。需要进行 n - 1趟排序。第一次比较 n - 1次，第二次 n - 2次，以此类推
以下为动图演示与代码实现：
//冒泡排序 void Bubble(vector<int>& v) { for (int i = 0; i < v.size() - 1; ++i) { for (int j = 0; j < v.size() - i - 1; ++j) { //比较交换 if (v[j] > v[j + 1]) { int tmp = v[j]; v[j] = v[j + 1]; v[j + 1] = tmp; } } } }
冒泡排序是一种稳定的排序，其时间复杂度为O(N ^ 2)。效率并不是很好，不管是最好还是最坏情况。
选择排序
选择排序的思想与冒牌排序很相似。选择排序也是需要比较大小，以升序为例，其每一趟排序都会把数组的头元素当成是最小元素，然后遍历数组找到除头元素外的最小元素，最后两个元素比较将最小的元素放置数组头元素，这样一趟排序下来最小的元素就到了数组首元素了。需要进行n - 1趟排序，第一次比较 n - 1次，第二次 n - 2次，以此类推
以下为动图演示与代码实现：
//选择排序 void Select(vector<int>& v) { for (int i = 0; i < v.size() - 1; ++i) { int mini = i + 1; for (int j = i + 1; j < v.size(); ++j) { if (v[j] < v[mini]) mini = j; } if (v[i] > v[mini]) { int tmp = v[i]; v[i] = v[mini]; v[mini] = tmp; } } }
选择排序的时间复杂度为O(N ^ 2)，效率较低且不稳定。
插入排序
插入排序的思想为：遍历数组，每一个元素前的所有元素都看成是一个有序数组，然后将当前元素寻找在前面那个数组的合适位置进行插入。需要进行n - 1 趟排序
以下为动图演示与代码实现：
//插入排序 void Insert(vector<int>& v) { for (int i = 0; i < v.size() - 1; ++i) { int end = i; int tmp = v[end + 1]; while (end >= 0) { if (tmp < v[end]) { v[end + 1] = v[end]; --end; } else break; } v[end + 1] = tmp; } }
插入排序的时间复杂度为O(N ^ 2)，但是数组越接近有序它的效率就越高。是一个稳定的排序
希尔排序
希尔排序法的基本思想是先选定一个整数，把待排序文件中所有记录分成整数个组，所有距离为的记录分在同一组内，并对每一组进行插入排序。然后改变整数值，重复上述分组和排序的工作。当到达整数=1时最后一次整体插入排序
因为插入排序在接近有序的情况下效率会更好，所以希尔排序是对直接插入排序的一种优化，通过预排序达到接近有序的目的
//希尔排序 void Shell(vector<int>& v) { int gap = v.size(); while (gap > 1) { //gap值 gap = gap / 3 + 1; //每一组的每个元素进行插入排序 for (int i = 0; i < v.size() - gap; ++i) { int end = i; int tmp = v[end + gap]; while (end >= 0) { if (tmp < v[end]) { v[end + gap] = v[end]; end -= gap; } else break; } v[end + gap] = tmp; } } }
希尔排序是一种不稳定的排序，但是其本身的分析非常的复杂。《数据结构（C语言版）》 — 严蔚敏，这本书提到希尔排序的时间是所取“增量”序列的函数，涉及一些数学上还未解决的难题。
对于希尔排序的gap值可以采用Knuth提出的方法取值，这种方法取值得出的复杂度在 O(n ^ 1.25) – O(1.6 * n ^ 1.25)这个区间内，可见效率还是比较可观的
堆排序
堆排序的思想与其大堆和小堆的性质相关。以升序为例：首先可以知道的是大堆的根节点是整个堆中最大的，因此当升序时只需要将根节点和最后的节点一交换，最大值就跑到了最后面了，这就符合了升序的规则。以此类堆下去，每一次交换后就固定住往下走的那个大节点，交换到根节点的就向下调整，每次都保证除了固定住的节点外其他节点符合大堆，这样每次都可以保证根节点是当前的最大值
关于向下调整
向下调整的思路就是将当前指定的节点向下去找合适的位置，以大堆为例，就拿当前节点和其最大的那个子节点去比较，如果子节点比其大，那两个就交换。以此反复直至遇到当前节点比其最大的子节点还要大或者整颗树的节点已经遍历完了。下图示例单个节点向下调整情况
关于堆排
对一个数组进行堆排序，以升序为例：首先需要将数组建成大堆结构，常用的方法为从数组的倒数第一个非叶子节点开始直至根节点，依次向下调整。数组为堆结构后，循环n - 1次，每一次都将当前根节点也就是当前最大值固定到数组后面，固定一次后，要将交换后的根节点向下调整保证堆结构不被破坏
代码示例：
//堆排序 //向下调整 void AdJustDown(vector<int>& v, int n, int parent) { //因为父节点可能会有两个子节点，因此需要找到最大的子节点 //先默认左子节点为大的，在进行比较 int minchild = parent * 2 + 1; while (minchild < n) { //找出最小子节点 if (v[minchild] < v[minchild + 1] && minchild + 1 < n) ++minchild; //大堆 if (v[parent] < v[minchild]) { swap(v[parent], v[minchild]); parent = minchild; minchild = parent * 2 + 1; } else break; } } void Heap(vector<int>& v) { //建堆 //从倒数第一个非叶子节点开始调整 for (int i = (v.size() - 1 - 1) / 2; i >= 0; i--) { AdJustDown(v, v.size(), i); } //排序 int i = 1; while (i < v.size()) { //交换根节点与最后一个节点 swap(v[0], v[v.size() - i]); //根节点向下调整 AdJustDown(v, v.size() - i, 0); ++i; } }
排升序建大堆，降序建小堆—思路都是将最大或最小节点调整到根节点方便与最后节点进行交换
堆排序的效率很高，时间复杂度为O(N * logN)，空间复杂度O(1)
是一个不稳定的排序方法
