结合归并排序和插入排序 Merge with Insertion Sort

66 阅读 0 评论 44 点赞

我是靠谱客的博主闪闪小白菜，最近开发中收集的这篇文章主要介绍结合归并排序和插入排序 Merge with Insertion Sort，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

程序功能：对n(2的整数幂)个数字进行排序。当n大于8时进行归并排序；当n小于等于8时，进行两次插入排序，然后归并到一起。

写这个程序，是做《算法导论》的一道课后题。

归并排序的时间复杂度为O（nlgn），插入排序为O（n*n）。而此方法介于二者中间。

/*=============================================================================
#
#     FileName: MergeInsertSort.cpp
#         Desc: 结合插入排序和归并排序
#
#       Author: yulu
#        Email: 187373778@qq.com
#
#      Created: 2014-05-01 23:34:00
#      Version: 0.0.1
#      History:
#               0.0.1 | yulu | 2014-05-01 23:34:00 | initialization
#
=============================================================================*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define INSERT_SIZE 8
#define SORT_NUM 32

void print_array(int *list,int len);
void merge_array(int *list1,int list1_size,int *list2,int list2_size);
void insertion_sort(int *list,int list_size);

void merge_insert_sort(int *list,int list_size)
{
	int flag=0;
	if(list_size>INSERT_SIZE || flag==1)
	{
		int list1_size=list_size/2;
		int list2_size=list_size-list1_size;
		int *list1=list;
		int *list2=list+list1_size;
		
		merge_insert_sort(list1,list1_size);
		merge_insert_sort(list2,list2_size);
		merge_array(list1,list1_size,list2,list2_size);
	}
	else
	{
		flag=1;
		int list1_size=list_size/2;
		int list2_size=list_size-list1_size;
		int *list1=list;
		int *list2=list+list1_size;
		
		insertion_sort(list1,list1_size);
		insertion_sort(list2,list2_size);
		merge_array(list1,list1_size,list2,list2_size);
	}
	return;
}

void insertion_sort(int *list,int len)
{
	int key,j;
	for(int i=1;i<len;i++)
	{
		j=i-1;
		key=list[i];
		while(j>=0 && list[j]>key)
		{
			list[j+1]=list[j];
			j--;
		}
		list[j+1]=key;
	}
} 

void merge_array(int *list1,int list1_size,int *list2,int list2_size)
{
	int i,j,k;
	i=j=k=0;
	int list[list1_size+list2_size];
	while(i<list1_size && j<list2_size)
	{
		list[k++]=list1[i]<list2[j]?list1[i++]:list2[j++];
	}
	while(i<list1_size)
	{
		list[k++]=list1[i++];
	}
	while(j<list2_size)
	{
		list[k++]=list2[j++];
	}
	//将list内容复制给list1
	for(int ii=0;ii<(list1_size+list2_size);ii++)
	{
		list1[ii]=list[ii];
	} 
}

void print_array(int *list,int len)
{
	for(int i=0;i<len;i++)
	{
		printf("%3d",list[i]);
		if(i!=len-1)
		    printf(" ");
	}
	printf("n");
}

int main()
{
	int len = SORT_NUM;
    int list[len];
    srand(time(0));
    for (int i = 0; i < len; ++i)
    {
        list[i] = rand() % 100;
    }
 
    print_array(list, len);
    merge_insert_sort(list, len);
    print_array(list, len);
 
    return 0;
}