其思想说白了就是先分后合,先将需要排序的数组迭代或递归每次分成两份直到分成n个数为止,然后再将n个数凉两两排序后合并成n/2个数组,以此类推直到合并排序成一个数组。
1、代码中采用的是线性表的顺序存储结构来存放数据的:
typedef void List_Node; //用于复用加入元素
typedef unsigned long Seqlist_Node; //为了重复使用,所以在这里使用的地址来操作的, 这里要用unsigned long类型,unsingesd int类型是在32位系统下使用的
typedef struct //存储线性表的结构体
{
int MAXSIZE; //线性表最大存储
int length; //线性表当前存储大小
Seqlist_Node* node; //指向下一个元素的地址,这样做的好处是能动态的申请数组,如果不这样,这里是数组
}Tseqlist;
Tseqlist* List_Create(int MAXSIZE) //创建线性表
{
Tseqlist* list = NULL;
if(MAXSIZE > 0)
{
list = (Tseqlist*)malloc( sizeof(Tseqlist) + sizeof(Seqlist_Node)*MAXSIZE );
}
if(list != NULL)
{
list->MAXSIZE = MAXSIZE;
list->length = 0;
list->node = (Seqlist_Node*)(list + 1); //node指向下一个结构体元素的首地址
}
return list;
}
2、基于上面代码实现归并排序:
在代码中merge函数是用来将一个数组的前半部分(已经有序)和它的后半部分(已经有序)排序成一个有序的数组,其中temp[]数组是过渡数组。
#include <stdio.h>
#include <iostream>
using namespace std;
void merge(int arr[],int temp[],int left,int mid,int right){
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while(i<=mid){//将左边剩余元素填充进temp中
temp[t++] = arr[i++];
}
while(j<=right){//将右序列剩余元素填充进temp中
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while(left <= right){
arr[left++] = temp[t++];
}
}
void mergSort(int arr[], int temp[], int start, int end) //1.先将分成两份,排序并合并
{
int m=0; //分为两组数的中间数的位置
//递归结束条件
if(start < end)
{
//递归
m = (start + end)/2;
//1.分出的第一个
mergSort(arr, temp, start, m ); //将原始数据的第一部分归并排序到temp(即utlmate_arr)中保存
//2.分出的第二个
mergSort( arr, temp, m+1, end ); //将第二部分归并排序并保存
//3.排序合并
merge( arr,temp , start, m, end ); //将temp[start]~temp[m]插入到ultimate_arr[m+1]~ultimate_arr[emd]
}
}
void sortMerging( int arr[] ,int arr1[], int length)
{
mergSort(arr, arr1, 0, length-1 );
}
void main()
{
int sr[9] ={50,10,90,30,70,40,80,60,20};
int sr1[9];
//merg(sr,sr1,0,4,8);
int i = 0;
for(; i<9;i++)
{
printf("%d-->",sr[i]);
}
printf("\n\n\n");
sortMerging(sr,sr1,9);
for(i = 0; i<9;i++)
{
printf("%d-->",sr[i]);
}
printf("\n");
system("pause");
}