排序按记录是否全部在内存操作分内排序和外排序；按记录排序前的先后位置关系与排序后的先后位置不变分稳定性排序和不稳定性排序；按平均时间复杂度可分O(n2)，O(nlogn)；按算法行为可分为插入排序（直接插入排序，希尔排序）、选择排序（简单选择排序、堆排序）、交换排序（冒泡派讯，快速排序），归并排序（归并排序）。
冒泡排序：从后面开始两两比较，记录上浮。改进，对已经排序的部分做标记，不再进行交换。平均时间复杂度O（n2）；最好是O(n)，最坏O（n2）；空间复杂度是O（1）；
For(int I = 1; I >=L->length; I ++){
//下标从1开始
For(int j = L->length -1; j>=i;j--){
If(L[j]> L[j+1]){
Swap(L, j,j+1);
}
}
}
改进：
Status flag = true；
For(int I = 1; I >=L->length&& flag; I ++){
//下标从1开始
Flag = false；
For(int j = L->length -1; j>=i;j--){
If(L[j]> L[j+1]){
Swap(L, j,j+1);
Flag= true；
}
}
}
直接插入排序：从记录开头开始，将记录分为有序与无序两部分，不断地将无序部分的记录与有序部分比较，插入到有序部分，插入位置后的有序部分相对地往后移动一位。平均时间复杂度O(n2)，最好是O(n);最坏是O(n2)；空间复杂度为O(1)；
For(int I = 2; I >=L->length; I ++){
//下标从1开始
If(L[i]<L[i-1]){
Int key = L[i];
For(int j = i-1; L[j]>key;j--){
L[j+1] = L[j];
L[j+1]=key;
}
}
}
简单选择排序：基本思想是找出余下记录中最小的记录，将其与当前位置记录交换。通过n-i次关键字比较，从n-i+1各记录中选出关键字最小的记录，并和第i各记录交换之。平均时间复杂度O(n2)，最好是O(n2);最坏是O(n2)；空间复杂度为O(1)；
For(int I = 1; I <=L->length; I ++){
//下标从1开始
min = I;
For(int j = i+1; j> L->Length;j++){
If(L[j]> L[min]){
min = j；
}
}
If(I!=min)Swap(L,I, min );
}
希尔排序：基本思想是先做到基本有序再做到整体有序。方法：选择一个增量（轴），不断比较轴尾与轴头，交换轴长两端；然后轴长不断减小，进行上一步。平均时间复杂度为O（nlog（n））~O(n2)；最好O(n1.3)，最坏O(n2)；不稳定排序。
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 =1( < …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
Int increment = L->Length;
Do{
Increment = increment/3 + 1;
For(int I = increment +1; i <=L->Length; I ++){
//下标从1开始
Int key = L[i];
If(key < L[i-increment]){
For(int j = I – increment; L[j] < key&&j>0; j-=increment){
L[j+ increment] = L[j];
L[j+ increment] = key;
}
}
}while(increment>1)
堆排序：将记录构造为大顶堆，将最后一个叶节点与根节点（最大）交换，余下的继续构造为大顶堆。平均时间复杂度O(nlogn)，最好O(nlogn)，最坏也是O(nlogn)；空间复杂度为O(1)；为不稳定排序。
构造大顶堆：(要点：下标从小到大遍历父节点保证每个父节点大于左右孩子节点)
Void HeadAdjust(SaList *L, int s, int m){
Int length = m-s+1;
Int last_f =length/2;
Last_f = Last_f <1?1: Last_f;//下标从1开始
For(int I = last_f; I >=1; i--){
Int tmp = 2*I;
If(tmp <length && L[tmp] <L[tmp+1])
Tmp += 1;
If(L[i]<L[tmp])swap(L, I, tmp);
}
}
以上算法缺陷在每次调整都要遍历所有父节点，而以下的只需要遍历变化的父节点。
Void HeadAdjust(SaList *L, int s, int m){
Int temp, j;
Temp = L[s];
For(j = 2*s; j<=m; j*=2){
If(j<m && L[j] <L[j+1])
++j;
If(temp >= L[j])
Break;
L[s] = L[j];
s = j;//直接指向修改过的树的根节点
}
L[s]= temp;
}
快速排序：将记录分为比枢轴（pivot）小和比枢轴大两部分。如此不断地递归分割。平均时间复杂度O(nlogn)，最好为O(nlogn)最差为O(n^2)；空间复杂度为O(logn)~O(n)；为不稳定算法。
void Qsort(int a[],int low,int high)
{
//算法要点：从尾部开始，首尾交替向中间移动（首部停在比pivot大的元素（比pivot小则与pivot交换，）， 尾部停在比pivot小的元素（比pivot大则不改变向前移动）， 两元素交换），直到首尾指针下标重叠，则该位置为pivot位置，设置该位置值为枢轴。
if(low>=high) return;
int first=low;
int last=high;
int key=a[first];/*用字表的第一个记录作为枢轴*/
while(first<last)
{
while(first<last&&a[last]>=key) --last;
a[first]=a[last];/*将比第一个小的移到低端*/
while(first<last&&a[first]<=key) ++first;
a[last]=a[first];/*将比第一个大的移到高端*/
}
a[first]=key;/*枢轴记录到位*/
Qsort(a,low,first-1);
Qsort(a,first+1,high);
}
归并算法：将n个记录的待排序序列，看做n个有序的子序列，然后两两归并，得到不大于n/2个长度为2或1的有序子序列，在两两归并，……，如此重复，直到得到一个长度为n的有序序列。平均时间复杂度O(nlogn)，最好O(nlogn)，最坏也是O(nlogn)；空间复杂度为O(n)；
基本有序的记录：用简单的算法即可：冒泡，简单选择、直接插入。