【数据结构】——归并排序和计数排序

目录

一、前言

二、正文

1.归并排序

1.1 基本思想

1.2【递归版】具体实现 

1.3【递归版】代码部分 

1.4【非递归版】具体实现 

1.5【非递归版】代码部分 

1.6特性总结

 2.计数排序

 2.1基本思路

2.2具体实现

2.3代码部分

2.4特性总结

三、结语

一、前言

二、正文

1.归并排序

1.1 基本思想

1.2【递归版】具体实现 

1.3【递归版】代码部分 

//归并排序[递归]
void _mergesort(int* arr, int begin, int end, int* tmp)
{
	//区间只有一个元素
	if (begin == end)
		return;
	int mid = (begin + end)/2;
	//左区间归并
	_mergesort(arr, begin,mid, tmp);
	//右区间归并
	_mergesort(arr, mid+1, end, tmp);
	//排序
	int begin1=begin;
	int end1 = mid;
	int begin2 = mid+1;
	int end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
			tmp[i++] = arr[begin1++];
		else
			tmp[i++] = arr[begin2++];
	}
	while(begin1 <= end1)
		tmp[i++] = arr[begin1++];
	while (begin2 <= end2)
		tmp[i++] = arr[begin2++];
	//拷贝
	memcpy(&arr[begin], &tmp[begin], sizeof(int) * (end-begin+1));

}

void mergesort(int* arr, int n)
{
	//申请一个数组用于归并排序
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == null)
	{
		perror("malloc failed");
	}
	//排序
	_mergesort(arr, 0, n-1, tmp);
	//释放
	free(tmp);
	tmp = null;
}

1.4【非递归版】具体实现 

1.5【非递归版】代码部分 

//归并排序[非递归梭哈版]
void mergesortnonr1(int* arr, int n)
{
	//申请一个数组用于归并排序
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == null)
	{
		perror("malloc failed");
	}
	//排序
	int gap = 1;
    //所有相同长度的序列的归并
	while (gap < n)
	{
		int i = 0;
		int j = 0;
        //一对序列的归并
		for (i = 0; i < n; i += 2 * gap)
		{
            //划分边界
		    int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
            //边界判断
			if (end1 > n - 1 || begin2 > n - 1)
			{
				break; 
			}
			if (end2 > n - 1)
			{
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
					tmp[j++] = arr[begin1++];
				else
					tmp[j++] = arr[begin2++];
			}
			while (begin1 <= end1)
				tmp[j++] = arr[begin1++];
			while (begin2 <= end2)
				tmp[j++] = arr[begin2++];
			memcpy(&arr[i], &tmp[i], sizeof(int) * gap);
            //增大序列长度
            gap *= 2;
		}
	}
}

//归并排序[非递归非梭哈版]
void mergesortnonr2(int* arr, int n)
{
	//申请一个数组用于归并排序
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == null)
	{
		perror("malloc failed");
	}
	//排序
	int gap = 1;
    //所有相同长度的序列的归并
	while (gap < n)
	{
		int i = 0;
		int j = 0;
        //一对序列的归并
		for (i = 0; i < n; i += 2 * gap)
		{
            //划分边界
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
            //边界判断
			if (end1 > n - 1)
			{
				end1 = n - 1;
				begin2 = n;
				end2 = n - 1;
			}
			if (begin2 > n - 1)
			{
				begin2 = n;
				end2 = n - 1;
			}
			if (end2 > n - 1)
			{
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
					tmp[j++] = arr[begin1++];
				else
					tmp[j++] = arr[begin2++];
			}
			while (begin1 <= end1)
				tmp[j++] = arr[begin1++];
			while (begin2 <= end2)
				tmp[j++] = arr[begin2++];
		}
		memcpy(arr, tmp, sizeof(int) * n);
        //增大序列长度
		gap *= 2;
	}
}

1.6特性总结

 2.计数排序

 2.1基本思路

2.2具体实现

2.3代码部分

//计数排序
void countsort(int* arr, int n)
{
	//找出数组中最大数和最小数
	int i = 0;
	int max = arr[0];
	int min = arr[0];
	for (i = 0; i < n; i++)
	{
		if (arr[i] > max)
			max = arr[i];
		if (arr[i] < min)
			min = arr[i];
	}
	int sz = max - min + 1;
	//申请一个数组
	int* a = (int*)malloc(sizeof(int) * sz);
	if (a == null)
	{
		perror("malloc failed");
	}
	memset(a, 0, sizeof(int) * sz);
	//记录元素出现的次数
	for (i = 0; i < n; i++)
	{
		a[arr[i] - min]++;
	}
	//对数组进行排序
	int num = 0;
	for(i=0;i<sz;i++)
	{
		while (a[i]--)
		{
			arr[num++] =i+min;
		}
	}
}

2.4特性总结

三、结语