数据结构之排序（二）--归并排序

一、递归实现归并排序

其思想说白了就是先分后合，先将需要排序的数组迭代或递归每次分成两份直到分成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");
}