一、什么是排序
排序就是将一组杂乱无章的数据按照一定的次序组织起来，此次序可以是升序也可以是降序
二、为什么需要进行排序
为了满足一些需求，比如在比较学生的成绩时，我们就需要给所有学生的成绩排一个顺序，这样才方便我们查看学生的名词，所以说排序就是为了给我们生活中的事提供方便。
三、数据表
数据表就是待排序数据元素的有限集合
四、排序码&主排序码&次排序码
（1）排序码排序时需要按照一定的规则，才能够排序，而排序码就是规则，比如比较两个学生的名次时，可以用综合成绩来比较，此综合成绩就是排序码
（2）主排序码 & 次排序码如果一个数据表中各个元素的排序码有多个，比如学生的属性有学号、成绩、姓名、班级等，在进行排序时，这些属性都可以作为排序码，如果使用一个排序码排序出来的结果是唯一的，那此排序码就是主排序码，如果使用一个排序码排序出来的结果不唯一，那此排序码就是次排序码。就像学生，使用学号进行排序时，排序结果是唯一的，那学号就是主排序码，因为一个学生的学号是唯一的，而如果使用成绩进行排序时，排序结果可能不唯一，因为一个分数可能会有好几个人，谁的名次在前，谁的名次在后，都是不确定的，那成绩就是次排序码
五、排序算法的稳定性
如果在一个排序表中，有两个元素R[i]==R[j],它们的排序码K[i]==K[j],在排序之前，元素R[i]在元素R[j]的前面，排序之后，元素R[i]还是元素R[j]的前面，那么此算法就是稳定的，否则就认为这个算法不稳定
例如对{1,2,4,7,8,9,5,5,6}进行排序，数据表中有两个5，下标为6的5在下标为7的5前面，如果排序之后，下标为6的5还是在下标为7的5前面，那就说此排序算法是稳定的，否则是不稳定的。
ps：在排序时，如果牵扯到间隔的交换两个元素的话，那此算法就是不稳定的，例如直接选择排序算法就是不稳定的。如果是挨着交换的话，那就认为此算法是稳定的，例如冒泡排序，是紧挨着的元素的两两交换，所以冒泡算法是稳定的。例如在进行快速排序就是不稳定的，因为会牵扯到间隔的元素的交换。
六、内部排序&外部排序
（1）内部排序当在进行排序时，需要进行排序的数据可以一次性的加载到内存
（2）外部排序与内部排序相反，需要进行排序的数据需要多次的加载到内存，不能一次性的加载到内存。
七、排序算法
1.直接插入排序
算法描述
当一个序列进行排序时，把序列分成两个部分，有序和无序，默认第一个元素是有序的，依次把无序序列中的元素通过与有序序列中元素的比较，搬移到有序序列中。
ps：B树在插入数据时，就是使用的插入排序
（1）简单版的插入排序（对数据按升序进行排序）
方法：比较一个元素搬移一个元素
void InsertSort(int array[], int sz)//插入排序{int i = 0;int end = 0;//标记有序序列中的最后一个元素for (i = 1; i < sz; i++){end = i - 1;//默认数组的第一个元素是有序的int key = array[i];//key保存的是待排序的元素while (key < array[end] && end >= 0){array[end + 1] = array[end];end--;}//在while循环中，也可以把key<array[i]写为key<=array[i],但//是如果这样写的话，会使此算法不稳定array[end + 1] = key;}}
（2）使用二分查找来寻找插入位置（对数据按升序进行排序）
优点：在寻找插入位置时，比较的次数少
方法：使用二分寻找位置，然后搬移
//使用二分查找查找插入位置的插入排序void InsertSort_Binary(int array[], int sz){for (int i = 1; i < sz; i++){int key = array[i];//1.第一步：使用2分查找算法找到待插入元素需要插入的位置int left = 0;int right = i-1;while (left <= right){int mid = left + ((right - left) >> 1);if (key < array[mid])right = mid - 1;elseleft = mid + 1;}//2.第二步：插入待插入的元素(搬移left后面到i之前所有的元素）right = i - 1;//注意right==left的元素也需要搬移，因为此时在上面循环的结束//条件是left>right,所以left多往后面动了一下while (right >= left){array[right + 1] = array[right];right--;}array[left] = key;}}
ps：这两个方法搬移的次数一样，但是使用二分查找，会使比较的次数少，从而提高排序的效率
（3）复杂度
时间复杂度：O(N) 到 O(N^2)之间
空间复杂度：O(1)
（4）插入排序的应用场景
应用场景：
a.需要排序的数据序列已经接近有序；
b.数据量少
最差场景
给的数据序列是降序，但是需要一个升序序列
最优场景
给的数据序列是降序，正好需要的也是一个降序序列
（5）插入排序算法是稳定的排序算法
2.希尔排序
ps：此排序时插入排序的升级版，当插入排序处理的数据量大时，采用希尔排序
算法描述
（1）代码
void ShellSort(int array[], int sz)//希尔排序{int gap = sz / 3 + 1;//gap是控制分组的，例如gap=3，那//就是3个元素为一组int i = 0;while (gap){for ( i = gap; i < sz; i++){int end = i-gap;//标记有序序列中的最后一个元素int key = array[i];//待插入元素while (key < array[end] && end >= 0){array[end + gap] = array[end];end -= gap;}array[end + gap] = key;}--gap;}}
（2）希尔排序的应用场景
数据量大的时候，可以采用希尔排序
（3）希尔排序不稳定，因为排序时元素是隔着交换的
（4）复杂度
时间复杂度
与gap的取值规则有关，
时间复杂度一般集中在N^1.25到1.6N^1.25之间，当gap=（元素个数）/3+1时，希尔排序的效率最高空间复杂度：O(1)
数据结构：直接插入排序 希尔排序 选择排序 堆排序 冒泡排序 快速排序归并排序
