下面主要写数据结构教材中介绍的“十大排序算法”。如果你不明白，杀了我。堆排序、快速排序、希尔排序、直接选择排序是不稳定排序算法，而基数排序、冒泡排序、直接插入排序、二分插入排序、链表插入排序、归并排序是稳定排序算法。直接插入排序T(n)=O(n^2)直接插入排序“插入排序”的基本思想是：每次将一条待排序的记录根据它在适当的位置，直到插入所有记录。令数组为a[0…n-1]：最初，a[0]自己构成一个有序区域，无序区域为a[1..n-1]。让我=1。将a[i]合并到当前有序区域a[0…i-1]中，形成a[0…i]的有序区间。i++重复第二步，直到i==n-1。排序完成。二分插入排序T(n)=O(n^2)二分插入排序是对直接插入排序的简单改进。对于二分插入排序，当需要插入第i个元素时，并不比较每个元素，而是：计算索引0~i-1的中点，即比较索引i处的元素和位于index(0+i-1)/2，如果indexi处元素的值较大，直接在(0+i-1)/2~i-1的一半范围内查找即可；否则，在0~(0+i-1)/2的一半范围内搜索，也就是所谓的对半范围内搜索时，采用1的方法，不断对半搜索，使得搜索范围可以缩小到1/2、1/4、1/8...，从而快速确定插入位置链表插入排序T(n)=O(n^2)的基本思想链表插入排序是：假设前n-1个节点是有序的，取***节点，顺着链表依次查找比较，直到合适的位置，修改“本节点”和“待定节点”-插入节点“指针。沿头节点遍历链表，比较本节点、待插入节点、后继节点的大小关系，直到：本节点<待插入节点<后继节点。让“本节点”指向“待插入节点”，“待插入节点”指向“后继节点”。Shell排序（Hill排序）T(n)=O(n^1.5)Shell排序的本质是分组插入排序，也叫收缩增量排序。这种方法的基本思想是：先把整个待排序元素序列分成若干个子序列（由按一定“增量”隔开的元素组成）直接插入排序，然后依次减少增量再排序他们。当里面的元素基本有序时（增量足够小，1），再对所有元素进行直接插入排序冒泡排序T(n)=O(n^2)。冒泡排序的基本思想是，相邻的元素两两比较，顺序颠倒，进行交换。这样，每一遍都会将最小或最大的元素“浮”到最上面，最终实现完整的排序。快速排序范围T(n)=O(n*lgn)~O(n^2)|平均T(n)=O(n*lgn)快速排序采用分而治之（递归）的方法，其基本思想是：先从序列中取一个数作为基准数划分过程，把所有的数大于这个数的数放在它的右边，所有小于等于它的数放在它的左边，然后对左右区间重复第二个区间两步，直到每个区间只有一个数，直接选择排序T(n)=O(n^2)直接选择排序（StraightSelectSorting）也是一种简单的排序方法，其基本思想是：从R[0]中选择最小值~R[n-1]，与R[0]交换从R{1}~R[n-1]中选择最小值，从R[i-1]]~R[n-1]中与R[i-1]交换第i个，选择最小值，并与R[i-1]交换堆选择排序T(n)=O(n*log2n)数据结构设计的一种排序算法，是选择排序的一种。堆分为大根堆和小根堆。下图为小根堆：“如图所示，以此类推”归并排序T(n)=O(n*log2n)归并排序是一种基于归并操作的有效方法排序算法采用的思想是分而治之。下图所示的双向归并：radixsort基数排序（radixsort）属于“分布式排序”，有点类似于“桶排序”。分配10个桶，桶号为0-9，依次将个位数放入桶中，取出桶中的数字重新放入桶中，但这次以十位数字为准，进入对应的桶，在同一个桶中有序取出，排序完成
