排序算法
排序算法在计算机中具有举足轻重的地位，也是我们在平时码字时最常用到的算法，当然我们可能并没有察觉到，因为这些算法往往都被集成在各种计算机语言中了，比如c,c++,java等。我们在使用的时候都很少去关心它的内部实现。我认为这些算法是很有必要搞懂搞清楚的，在此我做总结下，做个简单的笔记。
一.排序的分类
1. 按照移动对象分为两种：
（1）对数据直接进行移动，从而达成排序的目的；
（2）移动储存数据的地址，比如指针；
2.按照排序过程使用的存储器分两类：
（1）内部排序
a. 冒泡排序
b. 选择排序
c. 希尔排序
d. 快速排序
e. 插入排序
f . 堆排序
g. 基数排序
（2）外部排序
a. 归并排序
二. 复杂度及稳定性
1.复杂度分为 空间复杂度 和 时间复杂度
时间复杂度
算法执行所花费的时间，可分为最好情况，最坏情况，平均情况三种。
对于相同的输入大小，算法执行的时间可能会随着输入的不同而不同，导致最短执行时间的输入称为最好情况输入；导致最长执行时间的输入称为最坏情况输入；介于最好情况和最坏情况之间的称为平均情况；其实在我们分析算法的复杂度时最坏情况分析是最重要的，我们要确保算法永远不会比最坏情况还慢，所以分析都是以最坏情况为主。
空间复杂度
算法在执行的过程中，需要额外付出的存储空间，这里所说的额外存储空间指数据本身之外的数据。
稳定性
稳定性是指数据经过排序后，两个排序前键值相同的记录排序后是否任然可以保持他们俩原有的次序（虽然相同）。
下面以表格的形式列出常见排序算法的复杂度与稳定性：
| 排序算法 | 时间复杂度 最好情况 | 时间复杂度 最坏情况 | 时间复杂度 平均情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
| 希尔排序 | O(nlog2n) | O(nlog2n) | O(n) | O(1) | 不稳定 |
| 插入排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
| 快速排序 | O(nlog2n) | O(n^2) | O(nlog2n) | O(nlog2n) | 不稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(n+r) | 稳定 |
| 归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 |
接下来我会详细介绍具体每个算法的原理和代码实现，未完待续……