内排序和外排序
- 内排序：是指在排序过程中，待排序的所有记录都被放置在内存中
- 外排序：由于记录数量过多不能够全部放置在内存中，排序需要在内外存之间多次交换顺序
- 排序算法的性能影响因素：
- 时间性能：要尽可能减少比较次数和移动次数
- 辅助空间：执行算法需要的其他存储空间
- 算法复杂性： 算法本身的复杂度
排序的稳定性
- 相同值的元素，经过排序之后，多个相同值对应序列的排序没有发生改变，该排序方法就是稳定的；否则，不稳定
常用的排序算法
- 简单算法 ：冒泡排序<简单选择排序<直接插入排序 (性能)
- 改进算法 ： 希尔排序、堆排序、归并排序、快速排序
- 冒泡排序 ：相邻位做比较；时间复杂度O(n^2)
- 简单选择排序 ：通过n-i次的关键字之间的比较，在n-i+1个记录中找到最小值与第i个记录交换；O(n^2)
- 直接插入排序 ：设置i[0]做哨兵，从第二位（i）记录开始，和前一位比较，如果前一位的数据比较大，则将第i位的数据放到哨兵位，将前一位数据后推一位，知道前面的数据比存到哨兵为的数据小时，将哨兵位的数据放回到由于数据后推空出的位置；O(n^2)
- 希尔排序：相距某个“增量”做直接插入排序，该“增量”逐渐减小至1；O(n^3/2)
- 堆排序：将待排序序列构造成一个大顶堆。将堆顶的最大值与堆数组末尾元素交换，将剩余的n-1个元素重新构造成一个堆。反复执行；O(nlogn)
- 归并排序：（递归实现）元素两两归并成序列，序列再两两归并，重复直到最后变成一个有序的序列，又称“2路归并排序”；O(nlogn)；空间复杂度为O(n+logn)，比较占内存，但是效率高，稳定算法；；（非递归实现）空间复杂度为O(n)，尽量考虑使用非递归算法
- 快速排序：设置low指向尾端元素，high指向顶端元素，high往尾端端逐位移动，直到low>high,交换数据；low往顶端逐位移动，直到low>high,交换数据。重复以上步骤直到low和high靠到一起，此时low指向元素的左边元素都比low指向的元素小，右边则大。分别对左边和右边元素递归调用上面的排序方法。；最好O(logn)，平均O(logn)，最坏O(n)，不稳定排序
- 快速排序优化：
- 优化选取枢轴（三数取中，九数取中）
- 优化不必要的交换（增加哨兵）
- 优化小数组的排序方案
- 优化递归操作（尾递归）