首先，我们要知道处理一堆不规则的数据是很低效的。所以，我们通常在处理数据之前都要对其进行排序。待排序的记录是需要一个排序的关键字的。关键字不同，排序的结果也就不同。
其次，排序又分为内排序和外排序两种。内排序是指整个文件都放在内存中使用，排序时不涉及数据的内、外存交换。外排序是指在排序过程中需要进行数据的内、外存的额交换。其中内排序适合在记录数少时使用，外排序适合在记录数多时使用。
关于外排序，可以分为合并排序法和直接合并排序法。关于内排序，可以分为插入排序、选择排序、交换排序、归并排序、分配排序
一、内排序
1、插入排序
插入排序是，每次将一个待排序的记录按其关键字大小插入到前面已经排好序的自文件的适当位置，直到全部记录插入完成为止。应用该思想的主要有直接插入排序和希尔排序
1.1、直接插入排序
就是将记录插入到已经排好序的有序表里面，从而得到一个新的有序表，下面是该排序的算法过程：
前提条件：序列S = {S0,S1,S2,...,Sn-1}是n个待排序的序列
（1）循环遍历i，从1到n-1，重复步骤(2)~(4)
（2）将元素Si保存到临时变量中
（3）确定使得条件Sj>=Si成立的最小的j
（4）将子序列{Sj,...,Si-1}后移一个位置到{Sj+1,...,Si}
（5）将保存在临时变量中的原来的Si复制到Sj
（6）打印排序结果
这个排序方法，如果有n个元素需要你排序，那你需要做n-1趟排序
2.1、希尔排序
前提条件：序列S = {S0,S1,S2,...,Sn-1}是n个待排序的序列
（1）首先取一个小于n的数d1作为第一个增量，也就是两数之间的差距
（2）然后把全部记录分成d1个组，然后把所有距离为d1的倍数的记录放在同一个组中，然后再在各小组中继续进行插入排序
（3）然后取第二个增量d2<d1，在各个小组里面重复步骤2，一直到所取的增量dt=1（dt<dt-1<...<d2<d1），即所有记录放在同一组中进行直接插入排序为止
2、交换排序
交换排序就是两两比较待排序记录的关键字，如果两个记录之间的次序反了，就把这两条数据进行交换，直到没有反序的记录为止。应用该思想的主要有冒泡排序和快速排序
2.1、冒泡排序
假设有一堆重量不一的气泡，轻的在上面，从下往上比较，违反规则的轻气泡就让它往上挪。如此反复，直到完全符合规则为止，算法思想如下：
前提条件：序列S = {S0,S1,S2,...,Sn-1}是n个待排序的序列
（1）首先令j从n-1递减到1，重复步骤(2)~(4),也就是以j作为排序次数的最大值
（2）然后令i从1递增到j，重复步骤3，正式开始进行排序
（3）如果Si-1和Si成反序，交换他们
（4）排序完成之后，Sj是最大的
2.2、快速排序
快排利用的分治的思想，所谓的分治就是将原问题分解成若干个规模更小但是结构和原问题相似的子问题。然后递归的解决这些子问题，最后将这些子问题的解组合成原问题的解。也就是分为三步：分解、求解、组合。
前提条件：序列S = {S0,S1,S2,...,Sn-1}是n个待排序的序列
（1）从这个序列里面任选一个记录作为基准，以该基准划分为左右两个无序序列，左边的比基准值小，右边的比基准值大
（2）然后利用递归，再重复（1）的操作，对左右的无序序列分别进行快排
（3）将所有的结果组合起来即可
3、选择排序
选择排序是每一趟从待排序的记录中选择关键字最小的记录，顺序放在已经排好序的序列后面，直到全部记录排序完毕。主要有直接选择排序和堆排序
3.1、堆排序
堆排序就是利用堆实现的排序算法，堆首先是一棵完全二叉树，满足子结点的键值或索引总是小于（或者大于）它的父节点。堆排序有利用大根堆排序和小根堆排序两种。
通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：
父节点i的左子节点在位置(2i+1)
父节点i的右子节点在位置(2i+2)
子节点i的父节点在位置floor((i-1)/2)
其中大根堆排序的基本操作是：将R[1,2...n]构造成初始堆，利用数组。每一趟排序就是将当前无序的堆项记录R[1]和该区间的最后一个记录交换，然后再将新的无序区调整为堆。小根堆排序完全与此类同。
4、归并排序
归并排序就是将两个或两个以上的有序表组合成一个新的有序表。基本思想就是：将有N个序列的元素看成是N个长度为1的序列，然后将相邻的两两合并。得到N/2个长度为2的序列，依次类推，依次进行合并。直到所有数据被合并成长度为N的序列。
网友评论