手搓交换排序、归并排序、计数排序_业界新闻

发布时间:2024-08-03 01:34

阅读量:0

文章目录

交换排序
归并排序
实现计数实现排序
代码测试排序算法性能

交换排序

冒泡排序

void BubbleSort(int* arr, int n) { 	for (int i = 0; i < n; i++) 	{ 		int flag = 0; 		for (int j = 0; j < n - i - 1; j++) 		{ 			if (arr[j] > arr[j + 1]) 			{ 				Swap(&arr[j], &arr[j + 1]); 				flag = 1; 			} 		} 		if (0 == flag) 			break; 		 	} }

时间复杂度：O(N^2)

快速排序

快速排序是一种二叉树结构的交换排序方式，基本思想：任取待排元素序列中的某元素作为基准值，按照该基准值将待排序列分割成两子序列，左子序列所有元素均小于该基准值，右子序列均大于该基准值，然后在左子序列，和右子序列重复上述过程，直到待排元素符合预期结果。

void QuickSort(int* arr, int left, int right) { 	if (left >= right)//left 等于 right说明此时子序列里只有一个数据了，若left 大于 right说明此时子序列为空 	{ 		return; 	} 	//int meet = hoare_QuickSort(arr, left, right); 	//int meet = hole_QuickSort(arr, left, right); 	//int meet = lomuto_QuickSort(arr, left, right); 	QuickSort(arr, left, meet - 1); 	QuickSort(arr, meet + 1, right); }

时间复杂度：O(nlogn~n^2)，在以下查找基准值的方法，是以待排序列首元素位基准值，这种方法存在缺陷，使得快速排序的性能下降，时间复杂度及较高。

情景：

待排序列位有序，降序、升序、所有元素大小相同，这三种场景中将待排序列排序位升序的序列，时间复杂度位O(n^2)，挖坑，找基准值的方法后续补充。（我在详细讲解为什么这三种场景，这么找的基准值）

空间复杂度：O(logn ~ n)

hoare版本

随机选择一个基准值例如：待排序列首元素，定义两个指针，left和riight。
left指针负责从左到右寻找比基准值大的元素
right指针负责从右向左寻找比基准值小的元素
找到后将left和right交换，重复以上过程直到left的值大于right的值时，将基准值与right交换。
此时right所在的位置就是基准值应该在的位置

int hoare_QuickSort(int* arr, int left, int right) {     int key = left;     left++;     while(left <= right)     {         while(left <= right && arr[right] > arr[key])         {             right--;         }         while(left <= right && arr[left] < arr[key])         {             left++;         }         if(left <= right)             Swap(&arr[left++], &arr[right]--);     }     Swap(&arr[right], &arr[key]);     return right; }

此时走完循环的最后一步，在left7的位置和right3的位置发生交换后，此时right–,left++，若最外层循环的条件是left < right，此时跳出循环，right和key发生交换，交换完的结果不满足左子序列都小于基准值的标准，是一个错误的代码。不止最外层循环的条件必须是 left <= right，包括内层的两个while循环和if判断语句都是避免这种情况的发生，使得最后一次跳出循环right在left的左边，left在right的右边。

如果不等与使最后的left越过right，是用left < right的限制条件，不保证left和right同时所指的数据满足右子序列大于基准值，或左子序列小于基准值，而直接与rgiht交换

找基准值的函数，看似有两层循环，实际上是一层循环，通过left和right遍历数组元素，时间复杂度O(N)

时间复杂度：找相遇点的时间复杂度为O（n）

挖坑法

不断挖坑找坑填坑的过程

随机选择一个基准值，设待排序列首元素为坑位hole，通过变量key保存基准值，此时这个位置就是一个坑，可以用别的数据进行填坑，再定义两个指针，left和riight。
right指针负责从右向左寻找比基准值小的元素，找到后与将其填入坑中，让right此时所指向的位置设位新的坑
left指针负责从左到右寻找比基准值大的元素，找到后与将其填入坑中，让left此时所指向的位置设位新的坑
如此循环直到，不满足left < right后跳出循环，最后将key填入坑hole里，此时hole的位置就是基准值的位置。

int hole_QuickSort(int* arr, int left, int right) { 	int hole = left; 	int key = arr[left]; 	while (left < right) 	{ 		while (left < right && arr[right] > key) 		{ 			right--; 		} 		arr[hole] = arr[right]; 		hole = right; 		while (left < right && arr[left] < key) 		{ 			left++; 		} 		arr[hole] = arr[left]; 		hole = left; 	} 	arr[hole] = key; 	return hole; }

不同于hoare版本的找基准值，通过挖坑法，在循环里，当left == right就直接跳出，hoare版本的left和right相等时需要判断，当前它们所指的值比基准值大还是小，而挖坑法就不需要考虑，left和right相等时，同时指向的位置是一个坑，坑内不存在有效数据，最后直接将基准值填坑即可。

lomuto前后指针

定义两个指针prec，cur，它们只负责找比基准值小的元素。

初始条件prev指向数组首元素，cur指向prev的下一个元素，初始基准值位于基准值首元素位置
交换条件：当cur此时指向的值比基准值还要小的话prev加1，然后交换两者指向的值，大的跑到后边，小大跑到前面，若jprev和cur相等就不需要交换，让cur继续向走，找比基准值小的元素。
直到cur越过边界right，跳出循环，此时prev指向的位置就为基准值的位置

int lomuto_QuickSort(int* arr, int left, int right) {     int prev = left;     int cur = left + 1;     int key = left;     while(cur <= right)     {         if(arr[cur] < arr[key] && ++prev != cur)         {             Swap(&arr[cur], &arr[prev]); 		}         cur++; 	}     Swap(&arr[prev], &arr[key]);     return prev; }

非递归快速排序

实现非递归的快速排序，需要借组数据结构栈。栈：先进后出

递归版本的快速排序，通过基准值分割左右子序列，定义了left和right来限定左右子序列的取值范围，也是通过left和right来实现对序列的分割。找完待排序列的基准值后，通过栈保存左右子序列的取值范围，来模拟递归的场景。

由于栈的特殊结构，入栈时先入右区间，最后入左区间，出栈的顺序就为左区间、右区间。

先将初始左右区间入栈
在循环里出栈，为了和left，right区分开来，使用begin个end来接收序列的左右区间。
找基准值，找到基准值后，通过基准值分割新的左右子序列。[begin, key - 1]和[key + 1, begin]
可以先模拟递归左子序列，然后再模拟递归右子序列。先入栈右区间，再入栈左区间
直至栈为空时，结束循环，排序完成

void QuickSort_NonR(int* arr, int left, int right) { 	Stack st; 	StackInit(&st); 	StackPush(&st, right); 	StackPush(&st, left); 	while (st.top) 	{ 		int begin = StackTop(&st); 		StackPop(&st); 		int end = StackTop(&st); 		StackPop(&st);          		int prev = begin; 		int cur = begin + 1; 		int key = begin; 		while (cur <= end) 		{ 			if (arr[cur] < arr[key] && ++prev != cur) 			{ 				Swap(&arr[prev], &arr[cur]); 			} 			cur++; 		} 		Swap(&arr[prev], &arr[key]); 		key = prev;                   		if (begin < key -1) 		{ 			StackPush(&st, key - 1); 			StackPush(&st, begin); 		} 		if (key + 1 < end) 		{ 			StackPush(&st, end); 			StackPush(&st, key + 1); 		}          	} 	StackDestory(&st); }

时间复杂度：O(nlogn)

归并排序

归并排序是一种稳定的排序算法，该算法采用分治法，通过递归数组进行分半，递归的对两半序列进行排序，通过不断的将两组有序序列合并为一个有序序列

通过将两个有序序列合并为一个有序序列，称为二路归并
将1 和 3合并为一个有序序列， 1 3
将 1 3和 9合并为一个有序序列，1 3 9
将10 和 6 合并为一个有序序列 6 10
将 6 10和 1 3 9合并为一个有序序列，1 3 6 9 10，排序完成。

void _MergeSort(int* arr, int left, int right, int* temp) { 	if (left >= right)//递归结束条件 [left, right] 	{//一但left与right重合或left大于right，结束递归 		return; 	} 	int mid = (left + right) / 2; 	_MergeSort(arr, left, mid, temp); 	_MergeSort(arr, mid + 1, right, temp);//递归，分半  	int begin1 = left; 	int end1 = mid;//第一个序列的区间，左区间 	int begin2 = mid + 1; 	int end2 = right;//第二个序列的区间，右区间 	int index = begin1;//临时数组的下标起始，从左区间开始   	while (begin1 <= end1 && begin2 <= end2)//对两个有序序列进行排序 	{ 		if (arr[begin1] < arr[begin2]) 		{ 			temp[index++] = arr[begin1++]; 		} 		else 		{ 			temp[index++] = arr[begin2++]; 		} 	} 	while (begin1 <= end1)//避免该区间还有剩余 	{ 		temp[index++] = arr[begin1++]; 	} 	while (begin2 <= end2)//避免该区间还有剩余 	{ 		temp[index++] = arr[begin2++]; 	} 	for (int i = left; i <= right; i++)//将临时数组所有元素拷贝到原数组中。 	{ 		arr[i] = temp[i]; 	} } void MergeSort(int* arr, int n) { 	int* temp = (int*)malloc(sizeof(int) * n); 	_MergeSort(arr, 0, n - 1, temp); 	free(temp); }

实现对两个有序序列排序，合成为一个有序序列，并不会在数组里发生，一但这样做，在归并过程会造成数据丢失、覆盖，这里创建一个同等大小的临时数组，来对序列进行排序。
这样做就无法在 MergeSort函数里实现递归，需要在创建一个函数命名为 _MergeSort，别忘了将临时数组传递过去
使用 (left + right) / 2;，来完成对数组进行分半 [left, mid]和[mid + 1, right]
这里的递归步骤与二叉树的后续遍历，特别相似。

时间复杂度：O(nlogn)

空间复杂度：O(n)

实现计数实现排序

计数排序：

基于原序列的最大值和最小值相减后加1的结果开辟一个新数组，用来统计相同元素出现个数
根据该元素的大小所对应下标，放置该元素出现的个数
根据统计的结果将序列回收到原来的序列中

适用范围

与数据范围集中的情况
只适用于整数排序，不适用小数
数据过多，可能会对内存消耗造成负担

假设现在有一组数据：6 1 2 9 4 2 4 1 4，

先根据最大值最小值的差值开辟空间，若是根据最大值开辟，当最大值为109万，最小值为100，一共有10个数据，此时根据最大值直接开辟空间会很浪费，109个整形大小的空间，只用来存放10个数据。
1：2次， 2：2次，4：3次， 6：1次， 9：1次。其余没有出现的数据，默认使用0
根据下标打印，下标为1的元素出现2次，打印两个1，下标为2的元素出现两次，打印两个2，依次类推，最终打印的结果为 1 1 2 2 4 4 4 6 9，这就排序完成。

此时对 100 101 109 105 101 105，进行计数排序。
更具最大值减去最小值后加1开辟空间，109 - 100 + 1 = 10，给count开辟10个整形大小空间。
统计每个数据出现的个数，根据该数据对应下标存放在count数组里，而此时数组里下标从0开始，待排序列最小值从100开始，无法一一对应。
通过将待排序列的每个元素大小减去最小值 0 1 9 5 1 5，即可解决上述问题。
0：出现1次， 1：出现2次， 5，出现2次， 9：出现1次
此时，根据下对对应的此时，打印下标的值，和原序列并不相同，既然之前减去最小值，打印的时候加上最小值即可。100 101 101 105 105 109

当待排序列中存在负数，此时还是更具将待排序列中每个元素减去最小值，更具这个值来对应count下标存放它出现的次数。
-5 -3 2 4 2 1，将每个数据减去最小值，0 2 7 9 2 6，在根据count的次数取下标时，加上最小值即可。

void CountSort1(int* arr, int n) { 	int max = arr[0]; 	int min = arr[0]; 	for (int i = 1; i < n; i++) 	{ 		if (arr[i] < min) 			min = arr[i]; 		if (arr[i] > max) 			max = arr[i]; 	} 	//确定数组大小 	int range = max - min + 1; 	int* count = (int*)malloc(sizeof(int) * range); 	if (count == NULL) 	{ 		perror("malloc"); 		exit(1); 	} 	memset(count, 0, sizeof(int) * range); 	//统计数组中每个元素出现的次数，并放在对应下标的count数组里 	for (int i = 0; i < n; i++) 	{ 		count[arr[i] - min]++; 	} 	int index = 0; 	for (int i = 0; i < range; i++) 	{ 		while (count[i]--) 		{ 			arr[index++] = i + min;//放完数据，index++到下一个位置 		} 	} }