一、排序：
概念：将一组杂乱无章的数据按一定的规律次序排列起来。
排序算法的好坏衡量？
时间效率——排序速度控件效率——占用内存辅助空间的大小稳定性——若两个记录A和B的关键字相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的内部排序：指待排序记录全部存放在内存中排序的过程外部排序：指待排序记录的数量很大，以至于内存不能容纳全部记录，在排序过程中尚需要对外存进行访问的过程。排序方法： 插入排序： 直接插入排序希尔排序选择排序： 直接选择排序堆排序交换排序： 冒泡排序快速排序归并排序
=====================
二、插入排序：
每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。
1、直接插入排序：
现将序列中的第一个记录看成一个有序的子序列，然后从第二个记录开始，逐个进行插入，直至整个序列有序，排序过程为n-1次插入。列如：关键字序列T=(13,6,3,31,9,27,5,11)时间效率：因为在最坏的情况下，所有元素的比较次数总和为O(n的平方)空间效率：仅占用1个缓冲单元O(1)算法的稳定性：稳定
2、希尔排序：
先取一个正整数d1<n。把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作，直至di=1,即所有记录放进一个组中排序为止。一般取d1 = n/2 , di + 1 = di/2 ,如果结果为偶数，则加1希尔排序是一种不稳定的排序方法初始序列的不同会影响算法的效率。
三、选择排序
每一次从待排序的数据元素中选出最小的一个元素，存放在已排序列的后面，知道全部待排序的数据元素排完。优点：实现简单缺点：没次只能确定一个元素，表长为n时需要排n-1次前提：顺序存储结构直接选择排序：在所有记录中选出最小的记录，把它与第1个记录交换，然后在剩余的记录内选出最小的记录与第2个交换，依次类推。例如：关键字序列T=（21,25,49,27,16,08）
2、堆排序
小顶堆（小根堆） ri < = r2iri < = r2i + 1大顶堆（大根堆） ri > = r2iri >= r2i + 1若将该数列视作完全二叉树，则r2i 是ri的左孩子；r2i+1是ri的右孩子堆排序就是利用堆的特性对记录序列进行排序的一种排序方法。将无序序列建成一个堆，得到关键字最小（最大）的记录；输出堆顶的最小（最大）的值后，剩余的n-1个元素又建成一个堆，则可以得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫堆排序。输出堆顶元素之后，以堆中最后一个元素替代；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，陈这个从堆顶至叶子的调整过程为“筛选”堆排序的最坏时间复杂度为O(nlog2为底n的对数），对排序的平均性能接近最坏性能。堆排序的辅助空间为O(1)
================
四、交换排序
两两比较待排序记录的关键码，如果发生逆序（排列顺序与排序后的次序相反），则交换，直到所有记录都排好序为止。
1、冒泡排序：
每趟不断将记录两两比较，并按“前小后大”（或前大后小）规则交换。第一趟：第一个与第二个比较，大则交换；第二个与第三个比较，大则交换，.....关键字最大的记录交换到最后一个位置上；第二趟：对前n-1个记录进行同样的操作，关键字大的记录交换到第n-1个位置上；以此类推，则完成排序最好情况：初始排列已经有序，则执行一趟，做n-1次关键码比较，不移动对象最坏情况：初始序列逆序，要执行n-1趟时间效率：O(n的平方),因为要考虑最坏的情况空间效率：O(1) 只在交换时用到一个缓冲单元稳定性：稳定。
2、快速排序
从待排序列中任取一个元素（列如取第一个）作为中心，所有比它小（或相等）的元素一律放前，所有比它大的元素一律放后面，形成左右两个子表；然后再对各个子表重新选择中心元素并按照此规则调整，直到每一个子表中的元素只剩一个。此时便为有序序列了。优点：以为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快。前提：顺序存储结构快速排序过程：对r[0,1....n-1]中记录快速排序，设两个指针i和j，基准记录x=r[0]，初始时令i=0+1,j=n-1 从j所指向位置向前搜索第一个关键字小于x的记录，并和r[j]交换从i所指位置起向后搜索，找到第一个关键字大于x的记录，和r[i]交换重复上述两步，直至i==j为止分别对两个子序列进行快速排序，知道每个子序列只含有一个记录为止。若待排记录的初始状态为按关键字有序时，快速排序将蜕化成冒泡排序，最坏时间复杂度为O(n的平凡），最好时间复杂度为O(n倍log2为底n的对数)快速排序是一种不稳定的排序方法。
五、归并排序
可以把一个长度为n的无序序列看成是n个长度为1的有序子序列，首先做两两归并，得到n/2个长度为2的有序子序列；再做两两归并,如此重复，直到最后得到一个长度为n的有序序列。时间效率：O(nlog2为底n的对数)空间效率：O(n)稳定性：稳定
