学习之后，自己练习手写一下排序算法，加深印象
原理：假设初始序列含有n个记录，则可以看做是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的子序列；再两两归并，如此重复，最终得到一个长度为n的有序序列
递归方法
#define MAXSIZE 10
#include <stdio.h>
struct a{
int array[MAXSIZE]; //数组用于存储排序数据
int length; //用于存储数组长度信息，
};
void init_array(struct a *L){ //初始化数组
int i;
L->length = MAXSIZE-;
for (i=;i<=L->length;i++){ //索引为0的项留作备用
scanf("%d",&(L->array[i]));
}
}
void swap(struct a *L,int i,int j){ //交换数组项
int temp = L->array[i];
L->array[i] = L->array[j];
L->array[j] = temp;
}
void print(struct a *L){ //打印数组项
int i;
for (i=;i<=L->length;i++){
printf("%d ",L->array[i]);
}
}
void Merge(struct a *L, int first, int middle, int last){ //将L->array中的两个子序列合并
int Index1 = first, Index2 = middle+, mergeIndex = first; //Index1和Index2分别为两个子序列的索引，mergeIndex为合并后序列的索引
int temp[L->length+]; //创建临时序列，用作存储合并后的值
int i;
for(; Index1<=middle && Index2 <=last; mergeIndex++){ //依次对比两个子序列的值，并将较小的值填入临时序列中，当一个子序列没有值可以比较时，终止
if (L->array[Index1] < L->array[Index2]){
temp[mergeIndex] = L->array[Index1++];
}else{
temp[mergeIndex] = L->array[Index2++];
}
}
if (Index1 <= middle){ //将剩下的第一个子序列填入到临时序列
for (; Index1 <= middle; Index1++){
temp[mergeIndex++] = L->array[Index1];
}
}
if (Index2 <= last){ //将剩下的第二个子序列填入到临时序列
for (; Index2 <= last; Index2++){
temp[mergeIndex++] = L->array[Index2];
}
}
for (i=first; i<mergeIndex; i++){ //将临时序列的值复制给L->array
L->array[i] = temp[i];
}
}
void MSort(struct a*L, int first, int last){ //first和last分别为序列第一项和最后一项的索引
int middle;
if (first < last){ //当first和last相等时，即子序列只有一个数时，不必再继续划分子序列了
middle = first + (last-first)/; //作为中点坐标，平分整个序列
MSort(L,first,middle); // 归并索引从first到middle的子序列
MSort(L,middle+,last); //归并索引从middle+1到last的子序列
Merge(L,first,middle,last); //将两个子序列合并
}
}
void MergeSort(struct a *L){ //排序算法
MSort(L,,L->length);
}
int main(){
struct a List;
init_array(&List);
printf("排序前:");
print(&List);
MergeSort(&List);
printf("\n排序后:");
print(&List);
return ;
}
两个子序列的合并过程如上图所示，首先比较10和20这两个数，10比较小，则将其填入临时序列的第一项，再比较30和20这两个数，20比较小，则将20填入临时序列的第二项，如此比较下去，直到一个子序列到头，此时将另一个子序列剩下的，没有比较的值依次填入临时序列，最终得到合并完成的临时序列，再将其赋值给原始序列即可。
非递归算法
#define MAXSIZE 10
#include <stdio.h>
struct a{
int array[MAXSIZE]; //数组用于存储排序数据
int length; //用于存储数组长度信息，
};
void init_array(struct a *L){ //初始化数组
int i;
L->length = MAXSIZE-;
for (i=;i<=L->length;i++){ //索引为0的项留作备用
scanf("%d",&(L->array[i]));
}
}
void swap(struct a *L,int i,int j){ //交换数组项
int temp = L->array[i];
L->array[i] = L->array[j];
L->array[j] = temp;
}
void print(struct a *L){ //打印数组项
int i;
for (i=;i<=L->length;i++){
printf("%d ",L->array[i]);
}
}
void Merge(struct a *L, int first, int middle, int last){ //将L->array中的两个子序列合并
int Index1 = first, Index2 = middle+, mergeIndex = first; //Index1和Index2分别为两个子序列的索引，mergeIndex为合并后序列的索引
int temp[L->length+]; //创建临时序列，用作存储合并后的值
int i;
for(; Index1<=middle && Index2 <=last; mergeIndex++){ //依次对比两个子序列的值，并将较小的值填入临时序列中，当一个子序列没有值可以比较时，终止
if (L->array[Index1] < L->array[Index2]){
temp[mergeIndex] = L->array[Index1++];
}else{
temp[mergeIndex] = L->array[Index2++];
}
}
if (Index1 <= middle){ //将剩下的第一个子序列填入到临时序列
for (; Index1 <= middle; Index1++){
temp[mergeIndex++] = L->array[Index1];
}
}
if (Index2 <= last){ //将剩下的第二个子序列填入到临时序列
for (; Index2 <= last; Index2++){
temp[mergeIndex++] = L->array[Index2];
}
}
for (i=first; i<mergeIndex; i++){ //将临时序列的值复制给L->array
L->array[i] = temp[i];
}
}
void MergeSort(struct a *L){ //排序算法
int step; //每个子序列的长度
int i;
for (step=; step<L->length; step*=){ //子序列的长度随着归并的进行，以2为倍速增大
for (i=; i<=L->length/(*step); i++){ //i为将整个序列划分为包含两个子序列的组数
Merge(L,(i-)*step*+,i*step*-step,i*step*); //将两两子序列进行合并
}
if (L->length/(*step) == ){ //当不足以再划分子序列时
Merge(L,,step,L->length); //合并最后两个子序列
}
}
}
int main(){
struct a List;
init_array(&List);
printf("排序前:");
print(&List);
MergeSort(&List);
printf("\n排序后:");
print(&List);
return ;
}
非递归归并排序做法直接了当，从最小的序列开始归并直至完成。不需要像递归归并算法那样，需要先拆分递归，再归并退出递归，节省了时间和空间
算法时间复杂度：O(nlogn)