数据结构——排序2

目录

归并排序

递归

非递归 

 非比较排序

---

归并排序

递归

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

1.把数组从中间俩边分开进行递归进行分解

2.分解为最小后进行排序，分为左边和右边，将左边和右边的值想比较，最小的先放入tmp数组，之后把大的放入

3.把左边或右边剩余的未拷贝的拷贝到tmp数组中

4.把tmp数组中的数据拷贝回原数组

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; int end1 = mid;
	int i = begin1;
	int begin2 = mid + 1; int end2 = end;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}
	while (begin1 <= end1)
		tmp[i++] = a[begin1++];
	while (begin2<= end2)
		tmp[i++] = 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)
		return;
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n");
}
int main()
{
	int a[8] = {10,6,7,1,3,9,4,2 };
	MergeSort(a,8);
	PrintArray(a, 8);
	return 0;
}

 

非递归 

 

先1个2个归，然后再2个2个归，再4个4个归，这里要重新设置begin1 end1 begin2 end2

因为随着gap的变化这四个变量的范围也有所变化，每归一轮结束后，gap要乘2，当gap>=n时，结束循环

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n");
}
void _MergeSort1(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
		return;
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i = i + 2 * gap)
		{
			int begin1 = i; int end1 = i + gap - 1;
			int begin2 = i + gap; int end2 = i + 2 * gap - 1;
			int j = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
					tmp[j++] = a[begin1++];
				else
					tmp[j++] = a[begin2++];
			}
			while (begin1 <= end1)
				tmp[j++] = a[begin1++];
			while (begin2 <= end2)
				tmp[j++] = a[begin2++];
		
	
		}
		memcpy(a, tmp, n * sizeof(int));
		gap = gap * 2;
	}
	PrintArray(a, 8);
}
void MergeSort1(int* a, int n)
{
 
	_MergeSort1(a, n);
}
int main()
{
	int a[8] = {10,6,7,1,3,9,4,2 };
	MergeSort1(a,8);
	
	return 0;
}

 

 但是这样写会出问题，当数组内数字个数不是2的整数次幂的时候，就会发生越界

9个数据和10个数据等都会发生越界，而越界的数字是end1,begin2,end2，为了防止越界，我们可把上面越界情况写出来end1 >= n，begin2 >= n，end2 >= n ，而在程序中如果要进入循环应执行以下语句

while (begin1 <= end1 && begin2 <= end2)

begin1<=end1,begin2<=end2才进入循环，根据这个循环，我们判断如果end1>=n,begin2>=n,end2>=n时，我们可将他们的范围修改，使其不进入循环或进入循环后没影响，对end1>=，我们可让end1=n-1,这样让其进入循环，但对结果也不会产生影响，如上面的[8,11]，我们设置为[8,8]这样它归并后只会出去一个数字8，然后随便修正begin2和end2，使begin2

加入下面循环语句‘

if(end1>=n)
{
end1=n-1;
begin2=n;
end2=n-1;
}
else if(begin2>=n)
{
begin2=n;
end2=n-1;
}
else if(end2>=n)
{
end2=n-1;
}

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n");
}
void _MergeSort1(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
		return;
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i = i + 2 * gap)
		{
			int begin1 = i; int end1 = i + gap - 1;
			int begin2 = i + gap; int end2 = i + 2 * gap - 1;
			int j = begin1;
			if (end1 >= n)
			{
				end1 = n - 1;
				begin2 = n;
				end2 = n - 1;
			}
			else if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
					tmp[j++] = a[begin1++];
				else
					tmp[j++] = a[begin2++];
			}
			while (begin1 <= end1)
				tmp[j++] = a[begin1++];
			while (begin2 <= end2)
				tmp[j++] = a[begin2++];
		
	
		}
		memcpy(a, tmp, n * sizeof(int));
		gap = gap * 2;
	}
	PrintArray(a, 10);
}
void MergeSort1(int* a, int n)
{
 
	_MergeSort1(a, n);
}
int main()
{
	int a[10] = {10,6,7,1,3,9,4,2,10,11 };
	MergeSort1(a,10);
	
	return 0;
}

修正后的边界 

这样不管对几个都可以进行排序，不存在越界问题

另一种写法，当越界的时候，我们就不归了，但是要归并一次就要拷贝一次

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	int gap = 1;
	while (gap < n)
	{
		//printf("gap=%d->", gap);
		for (int i = 0; i < n; i += 2 * gap)
		{
			// [i,i+gap-1][i+gap, i+2*gap-1]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
 
			// end1越界或者begin2越界，则可以不归并了
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}
			//printf("[%d,%d] [%d, %d]--", begin1, end1, begin2, end2);
 
			int m = end2 - begin1 + 1;
			int j = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
 
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
 
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
 
			memcpy(a + i, tmp + i, sizeof(int) * m);
		}
 
		gap *= 2;
	}
 
	free(tmp);
}

 非比较排序

非比较排序有桶排序，计数排序，基数排序

 计数排序

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

 

0出现2次，1出现0次，2出现2次，3出现3次，4出现0次，5出现1次 

每个数出现几次相对应的位置就++几次

然后再写回原数组 

局限性：1.如果是浮点数，字符串就无法用这种方法

               2.如果数据范围很大，空间复杂度就会很高，相对不适合

如果数组是：1000，1005，1000，1008，1009，1006

不可能开1000多个数据不然比较浪费，此时就要使用绝对映射

使用相对映射：1000-0

                         1001-1

                          ……

                          1009-9

这样即使有负数，也能进行排序

-5对应0 

void CountSort(int *a,int n)
{
	int min = a[0], max = a[0];//先找到最大值和最小值
	for (int i = 0; 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);
	if (count == NULL)
		return;
	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)
	{
		//出现几次，回写几个i+min
		while (count[i]--)
		{
			a[j++] = i + min;
	}
	}
}
int main()
{
	int a[10] = {10,6,7,1,3,9,4,2,10,11 };
	CountSort(a,10);
	return 0;
}

 时间复杂度：O(max（range，N）)

空间复杂度：O(range)