排序
内部排序：待排序的元素总数相对于内存而言较小，整个排序过程可以在内存中进行。
外部排序：待排序的元素总数较多，不能全部放入内存，排序过程中需要访问外存。
内部排序算法有很多，各有其优缺点和适合的场合。
排序的稳定性：如果在排序的序列中，存在前后相同的两个元素的话，排序前和排序后他们的相对位置不发生变化。
稳定性的定义
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，$r_i$=$r_j$，且$r_i$在$r_j$之前，而在排序后的序列中，$r_i$仍在$r_j$之前，则称这种排序算法是稳定的；否则称为不稳定的。
对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。
稳定性的意义
- 如果只是简单的进行数字的排序，那么稳定性将毫无意义。
- 如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性依旧将毫无意义。
- 如果要排序的内容是一个复杂对象的多个数字属性，但是其原本的初始顺序毫无意义，那么稳定性依旧将毫无意义。
- 除非要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法，例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。
稳定排序
基数排序、冒泡排序、直接插入排序、两两插入排序、归并排序。不稳定排序
堆排序、快速排序、希尔排序、简单选择排序。直接插入排序
基本思想
将数组中第1个元素作为有序序列，然后将剩下的n-1数组元素，按照顺序插入第1个元素的序列中。
插入第1个元素后，第1个元素的序列保持有序。
将待插入有序序列的元素存入临时变量temp中，在有序序列从后往前比较大小，查找插入的位置。
当temp小于有序序列的元素时，该有序序列元素往后移1位，temp元素继续比较。
直到有序序列中有元素比temp小、或者到有序序列第1个元素时结束，这时将temp插入有序序列元素的位置。
插入排序会优于选择排序，理由是它在排序过程中能够利用前部分数组元素已经排好序的一个优势，有效地减少一些比较的次数，当然这种优势得看数组的初始顺序如何，最坏的情况下(给定的数组恰好为倒序)插入排序需要比较和移动的次数将会等于1 + 2 + 3… + n = n * (n + 1) / 2，这种极端情况下，插入排序的效率甚至比选择排序更差。时间复杂度
最好情况比较次数是O(n)(有序)，最坏情况比较次数O(n*n)无序。空间复杂度
O(1)每次都交换一个元素稳定性
插入排序是稳定排序，如果碰到相等的元素，就把新元素插入相等元素的后面，即他们原来的顺序没有变化。（插入排序在全部元素插入完毕之前，都不能确定最终一个元素的位置）temp < A[j - 1]，如果改成temp <= A[j - 1]，则是不稳定排序。Java
