排序稳定性：在排序前后，关键字相同的元素的相对位置不发生改变。
插入类排序
1.直接插入排序：比较适用于待排序记录数目较少且基本有序的情况
最好情况：待排序记录本身已按关键字有序排列，此时总的比较次数是n-1次，时间复杂度为O(n)
最坏情况：待排序记录按关键字逆序排列，总的比较次数达到最大，总的移动次数也达到最大，时间复杂度为O(n2)
平均情况：待排序记录是随机的，总的比较次数和总的移动次数均约为n2/4。因此，直接插入排序的时间复杂度为T(n)=O(n2),空间复杂度S(n)=O(1)
直接插入排序是稳定的排序算法。
在直接插入排序算法中，由于待插入元素的比较是从后向前进行的，循环while(r[0].key<r[j].key)的判断条件就保证了后面出现的关键字不可能插入到与前面相同的关键字之前，因此保证了插入排序的稳定性
2.折半插入排序：适用于有序顺序表
折半插入排序仅减少了关键字的比较次数，该比较次数与待排序表的初始状态无关，元素的移动次数并未改变，它依赖于待排序表的初始状态。折半插入排序的时间复杂度仍为O(n2），是一种稳定的排序算法。算法中if(x.key<r[mid].key) high=mid-1;else low=mid+1;,保证了相同的元素不会排到前面
最好情况：O(nlogn)
最坏情况:O(n2)
3.希尔排序：当子序列记录间的间隔为d时,共有d个子序列，需要对d个子序列分别进行插入排序。在排序过程中，相同关键字记录的领先关系发生变化，是不稳定的排序。
例如{2,4,1,2}，时间复杂度O(n1.5)
交换类排序
1.冒泡排序
时间复杂度：O(n2)
最好情况:O(n），初始序列有序，比较次数n-1,移动次数为0
最坏情况:初始序列为逆序，需要进行n-1趟排序，第i趟排序需要进行n-i次关键字的比较，且每次比较后都必须移动元素3次来交换元素位置,时间复杂度为O(n2)
2.快速排序
最好情况：每趟将序列一分两半，正好在表中间，将表分成两个大小相等的子表,O(nlogn)
最坏情况：已经排好序,第一趟经过n-1次比较，第一个记录定在原位置，左部子表为空表，右部子表为n-1个记录，第二趟n-1个记录经过n-2次比较，第二个记录定在原位置，左部子表为空表，右部子表为n-2个位置，以此类推，共需进行n-1趟排序，其比较次数为约为n(n-1)/2,其时间复杂度为O(n2)
空间复杂度为O(logn)
不稳定：例如{3,3,2}
选择类排序
1.简单选择排序:时间复杂度为O(n2)
最好情况：已经有序，不需要移动记录
最坏情况:第一个元素最大，其余记录从小到大有序排列，此时移动的次数最多，为3(n-1)次。
简单选择排序的比较次数与初始状态下的待排序的记录序列的排列情况无关。
不稳定：例如{3,3,2}
2.堆排序
建初堆时间复杂度为O(n），每次调整的时间复杂度为O(logn),故在最好情况、最坏情况和平均情况下，堆排序的时间复杂度为O(nlogn)
不稳定：如{5，5,3}
归并排序
2路归并每趟归并的时间复杂度为O(n),算法的时间复杂度为O(nlogn)，空间复杂度为O(n),稳定。
基数排序
基数排序需要进行d趟分配和收集，一趟分配需要o(n),一趟收集需要O®,所以基数排序的时间复杂度为O(d(n+r)),它与序列的初始状态无关。
一趟排序需要的辅助存储空间为r(r个队列)，会重复使用，空间复杂度为O®,按位排序必须是稳定的.