数据结构—排序算法（归并&&非比较）网站首页 技术杂谈

数据结构—排序算法（归并&&非比较）

IfYouHave 2024-06-17 11:28:16

简介数据结构—排序算法（归并&&非比较）

1、归并排序

1.1 基本思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序核心步骤：

1.2 归并排序递归方式的实现

归并排序相当于后序遍历，此时可以求出中间位置，控制归并区间

【begin , mid】【mid + 1，end】，递归，直到只有一个值，返回左右区间，对左右区间进行归并，完成后返回，在对右区间递归，递归完后，在返回，归并左右区间。

void _MergeSort(int* a,int begin,int end,int* tmp) {
	if (begin >= end) {
		return;
	}
	int mid = (begin + end) / 2;
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);
	//归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int tmpPos = begin1;
	while (begin1 <= end1 && begin2 <= end2) {
		if (a[begin1] > a[begin2]) {
			tmp[tmpPos++] = a[begin2++];
		}
		else {
			tmp[tmpPos++] = a[begin1++];
		}
	}
	while (begin1 <= end1) {
		tmp[tmpPos++] = a[begin1++];
	}
	while (begin2 <= end2) {
		tmp[tmpPos++] = a[begin2++];
	}
	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n) {
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) {
		printf("malloc fail
");
		exit(-1);
	}
	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
}

1.3 归并排序非递归方式的实现

问题分析：

快排类似于先序遍历，先处理 keyi 值，因此可以利用数据结构栈和队列记录后续区间，进行非递归实现，由于其keyi值先进行了处理，并不关注左右起始位置是否记录，依次进行左右位置出栈入栈数据处理，最终获得有序序列。

但是归并排序，在出栈获得序列左右边起始位置后，处理完左边子序列和右边子序列后，仍需对原序列再次进行归并处理，而此时栈内已不再有原序列，因此借助数据结构方式进行实现非递归是困难的。

解决方法：

此时可借助循环，控制起始序列方式，进行处理。此时需要控制其两组数据如果第一组以达到边界，下一组数据便会越界，出现越界访问错误。

void MergeSortNonR(int* a, int n) {
	assert(a);
	int* tmp = (int*)malloc(sizeof(int) * n);
	assert(tmp);
	int gap = 1;
	while (gap < n) {
		for (int i = 0; i < n; i += 2 * gap) {
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			//修正边界
			if (end1 >= n) {
				end1 = n - 1;
				//begin2、end2 修正为一个不存在的空间
				begin2 = n;
				end2 = n - 1;
			}
			else if (begin2 >= n) {
				begin2 = n;
				end2 = n - 1;
			}
			else if (end2 >= n) {
				end2 = n - 1;
			}
			int tmpPos = begin1;
			while (begin1 <= end1 && begin2 <= end2) {
				if (a[begin1] > a[begin2]) {
					tmp[tmpPos++] = a[begin2++];
				}
				else {
					tmp[tmpPos++] = a[begin1++];
				}
			}
			while (begin1 <= end1) {
				tmp[tmpPos++] = a[begin1++];
			}
			while (begin2 <= end2) {
				tmp[tmpPos++] = a[begin2++];
			}
		}
		memcpy_s(a, sizeof(int) * n, tmp, sizeof(int) * n);
		gap *= 2;
	}
	free(tmp);
}

1.4 归并排序的特性总结

归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定

2、计数排序

2.1 计数排序基本思想

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。操作步骤：

1. 统计相同元素出现次数

2. 根据统计的结果将序列回收到原来的序列中

3.局限性：
1）如果是浮点数、字符串就不能排序
2）如果数据范围很大，空间复杂度高，不合适
3）如果使用绝对映射，容易浪费空间，且负数不便于处理

2.2 计数排序的实现

优化，统计最小，将其所计数映射位置减去最小值，可以相对减少空间浪费，同时可以排序负数

void CountSort(int* a, int n) {
	assert(a);
	int min = a[0], max = a[0];
	for (int i = 1; i < n; i++) {
		if (a[i] < min) {
			min = a[i];
		}
		if (a[i] > max) {
			max = a[i];
		}
	}
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	assert(count);
	memset(count, 0, sizeof(int) * range);
	//计数
	for (int i = 0; i < n; i++) {
		count[a[i] - min]++;
	}
	//回写排序
	int j = 0;
	for (int i = 0; i < range; i++) {
		while (count[i]--) {
			a[j++] = i + min;
		}
	}
}