不稳定的排序方法往往是按照一定的间隔移动或交换记录对象的位置，从而可能导致具有相等排序码的不同对象的前后相对位置在排序前后颠倒过来。
稳定的排序方法往往在相邻的数据对象间比较排序码，如果发生逆序才交换，具有相等排序码的不同对象在排序前后不会颠倒。
n-1次起泡，第i次起泡从V[n-1]和V[n-2]到V[i]和V[i-1]共执行n-i次比较和交换操作，一共执行n(n-1)/2次。
数据比较次数与输入序列中各待排序的元素的初始排列无关，但数据交换次数与其有关。
如果在待排序码后面的若干排序码比前面的排序码小，则在起跑排序过程中，排序码可能向最终它应移动的位置相反方向移动。
在算法中增加标志exchange，用以标识本次起泡结果是否发生了逆序和交换。每次起泡前将exchange置为false，起泡过程中一旦发生交换就将exchange置为true，每次起泡后检查exchange，为false则已排序完成，直接return。
最好情况需要n-1次比较和0次交换，最差情况下需要n(n-1)/2次比较，3n(n-1)/2次交换。
因此一般情况下，排序算法大约需要n2/2次比较和交换操作。
奇数次排序从前往后，偶数次排序从后往前。也利用exchange进行控制。
奇数次排序时从前往后，每次对两个元素进行交换时把左边那个元素的位置记录了下来，最后修改high。
偶数次排序从后往前，每次对两个元素进行交换时把右边那个元素的位置记录了下来，最后修改high，修改low。
可以认为low左边的和hih右边的元素都已排序完成，low>=high时排序完成。
n-1次插入，排序码比较次数和元素移动次数与元素排列码的初始排列有关。
最好情况下，每次只需要将插入元素和前面的有序元素序列最后一个元素的排序码比较1次，即总比较n-1次移动0次。
最差情况下，第i次插入，需要比较i次、移动i+2次，总比较次数KCN=n(n-1)/2，总移动次数RMN=(n+4)(n-1)/2。
平均情况下排序码比较次数和元素移动次数约n2/2。因此直接插入排序的时间复杂度为O(n2)。
是一种稳定的排序方法。
总排序码比较次数比直接插入排序的最好情况差、最差情况好。
元素初始排列有序或者接近有序时，折半插入排序的排序码比较次数更多。折半插入排序的元素移动次序同样依赖元素初始排列。
将n个元素进行折半插入排序的排序码比较次数约为n·log2n。
n-1次选择，每一次在后面n-i+1个待排序元素中选出排序码最小的元素，作为有序元素序列的第i个元素
排序码比较次数KCN与元素初始排列无关，第i次选择具有最小排序码元素所需的比较次数总是n-i次，共计n(n-1)/2次
元素移动次数与元素序列初始排列有关，最好情况为RMN=0，最差情况RMN=3(n-1)。
是一种不稳定的排序方法。
在复制到辅助数组L2时可以把第二个有序表的元素顺序逆转，这样L2两端元素小中间元素大，检查指针s1和s2初始为left和right，两个待归并的表从两端开始处理向中间归并，两个表的尾端互为监视哨，也可以省去检查子序列是否结束的判断。
同理，链表的归并排序为：
六、分配排序
将元素分配至各个桶中的操作的时间复杂度为O(n)，每个子序列排序的时间与子序列排序算法有关。
整个桶式排序总的时间复杂度也为O(n)，对于均匀分布的元素序列，时间开销线性增长。
利用多排序码排序实现对单个排序码排序。
radix为符号数，每个排序码有d位。
最高位优先：是一个递归过程，首先根据最高位排序码进行排序，得到若干元素组。分别对每组元素依据次高位排序码进行排序，得到更小的分组。
当待排序的排序码大小只取决于高位的少数几位而与大多数低位无关时，MSD比LSD效率更高。
最低位优先：先依据最低位排序码进行排序，然后依据次低位优先码进行排序。
对于有n个元素的链表，执行while循环进行n次分配，把n个元素分配到radix个链表中去。
执行for循环进行radix次收集，从每个队列中把元素收集起来按顺序重新链接成一张链表。
radix一定时，对于元素个数较多而排序码位数较少的情况（例如非负整数），使用链式基数排序较好，它是稳定的排序方法
但其不适合浮点数排序。
需要计数器count[radix]和一个与待排序元素组同样大小的辅助数组auxArray[n]。