【数据结构】快速排序,归并排序

快速排序

1.hoare版本
在这里插入图片描述
根据动图的演示,整理的思路如下,
1.定义left,right,key。key默认是左边第一个元素,像两个指针,左边找比key大的,右边找比k小的,找到的话,交换二者,往返这个过程,当left与right相遇时,交换key和此时相遇的值.

#include<stdio.h>
void swap(int*p,int*q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;

}
int PartSort1(int* a, int left, int right)
{
	int keyi =left;
	while (left < right)
	{
		while (left<right && a[right]>=a[keyi])
		{
			right--;
		}
		while (left<right && a[left]<= a[keyi])
		{
			left++;
		}
		swap(&a[left],&a[right]);

	}
	swap(&a[keyi], &a[left]);
	return left;

}
int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
	PartSort1(arr, 0, 9);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);


	}


}

在这里插入图片描述
单趟下来,6出现在正确的位置。
1.为什么大循环是left<right?
当两个小人走到一块去的时候,我们应该交换key位置的值,和相遇时候的值了,而不是让他们两个岔开.
2.为什么在小循环中要加left<right?
假如说数组是10,10,10,10,10,10,10,10,10
在小循环中一直找小,找不到就会越界.
3.return的值有什么用?
return的值相当于分了界,然后就可以分别对子区间使用快排了.
在这里插入图片描述

针对每个子区间,使用快排

#include<stdio.h>
void swap(int*p,int*q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;

}
int PartSort1(int* a, int left, int right)
{
	int keyi =left;
	while (left < right)
	{
		while (left<right && a[right]>=a[keyi])
		{
			right--;
		}
		while (left<right && a[left]<= a[keyi])
		{
			left++;
		}
		swap(&a[left],&a[right]);

	}
	swap(&a[keyi], &a[left]);
	return left;

}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int mid=PartSort1(a,begin,end);
	QuickSort(a,begin, mid - 1);
	QuickSort(a,mid+1,end);

}
int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
	QuickSort(arr, 0, 9);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);


	}


}

递归结束条件,如果有两个数据的话还能排一次,如果只有一个数据的话就不用排了
1.为什么要右边先走,左边再走,为啥相遇的值一定比key小或者等于key?
情况1:右边找小,找不到小,一直往左走,与key碰面,相遇的值为key;
情况2:右边找到了小,停在那里,左边找大,一直找不到大,相遇点就停在了比key小的那里
情况3:交换值之后,右边一直找不到小,一直走,相遇点就是左边刚交换完,还没有动的比key小的值.
情况4:交换值之后,右边继续移动,找到小停在那,左边找不到大,相遇点就是比key小的.

2.挖坑法
在这里插入图片描述
1.创建临时变量key保存最左侧坑位的值,右边找小找到小之后,将找到的小值填到左边的坑位去,这里变成坑位.左边找大,找到大之后,将该值填入右侧的坑位,依次循环,相遇之后,将key放到相遇点

#include<stdio.h>
void swap(int*p,int*q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;

}

int PartSort2(int* a, int left, int right)
{
	int key = a[left];
	int pole = left;
	while (left < right)
	{
		while (left < right && a[right] >=key)
		{
			right--;
		}
		a[pole] = a[right];
		pole = right;

		
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[pole] = a[left];
		pole = left;
		
	}
	a[left] = key;
	return left;

}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int mid=PartSort2(a,begin,end);
	QuickSort(a,begin, mid - 1);
	QuickSort(a,mid+1,end);

}
int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
	QuickSort(arr, 0, 9);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);


	}


}

3.前后指针法

前后指针法

#include<stdio.h>
void swap(int*p,int*q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;

}
int PartSort3(int* a, int left, int right)
{
	int keyi = left;
	int cur = left + 1;
	int prev = left;
	while (cur<=right)
	{
		if (a[cur] < a[keyi])
		{
			prev++;
			swap(&a[cur], &a[prev]);
		}




		cur++;
    }
	swap(&a[keyi], &a[prev]);
	return prev;

}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int mid=PartSort3(a,begin,end);
	QuickSort(a,begin, mid - 1);
	QuickSort(a,mid+1,end);

}
int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
	QuickSort(arr, 0, 9);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);


	}


}

4.快速排序非递归版
在这里插入图片描述
采用非递归代替递归分割步骤,当区间只有一个值时,将不在入栈.

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void swap(int*p,int*q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;

}
typedef struct Stack//定义一个栈的结构体变量	
{
	int* a;
	int top; // 栈顶
	int capacity; // 容量
}Stack;
void StackInit(Stack* ps)
{
	assert(ps);//断言,防止为空指针
	ps->a = NULL;//所指向的地址为空
	ps->capacity = ps->top = 0;//容量和栈中元素个数均为0
}
void StackPush(Stack* ps, int data)
{
	assert(ps);
	if (ps->capacity == ps->top)//如果栈中的元素个数等于栈的容量时考虑扩容,
	{
		int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;//如果刚开始时都等于0,就先给4个空间大小,后面如果满的话,容量扩大1倍
		int* newnode = (int*)realloc(ps->a, sizeof(int) * newcapcity);//申请空间,将申请好的空间首地址传给newnode指针
		assert(newnode);//断言,防止malloc失败
		ps->a = newnode;//将newnode保存的申请空间的首地址传给ps->a,让ps->a指向创建好的空间
		ps->capacity = newcapcity;//容量大小更新为新容量大小



	}
	ps->a[ps->top] = data;//像存数组一样存数据
	ps->top++;//指向下一个
}
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;//ps->top为栈中元素个数.==0栈中无元素,无元素要返回1, 无元素ps->t0p==0,这个表达式结果是1,返回1;





}
// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//防止栈内无元素,继续出栈
	ps->top--;
}
// 获取栈顶元素
int StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];//ps->top为栈中元素个数,由于数组下标是从0开始,所以栈顶元素下标为ps->top-1;

}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;

}
// 销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);//free掉动态申请的内存
	ps->a = NULL;//防止野指针
	ps->capacity = ps->top = 0;//容量和栈中元素个数置为0



}
int PartSort1(int* a, int left, int right)
{
	int keyi =left;
	while (left < right)
	{
		while (left<right && a[right]>=a[keyi])
		{
			right--;
		}
		while (left<right && a[left]<= a[keyi])
		{
			left++;
		}
		swap(&a[left],&a[right]);

	}
	swap(&a[keyi], &a[left]);
	return left;

}
void QuickSort(int* a, int begin, int end)
{
	Stack st;
	StackInit(&st);
	StackPush(&st,end);
	StackPush(&st,begin);
	while (!StackEmpty(&st))
	{
		
		int left = StackTop(&st);
			StackPop(&st);
		int right = StackTop(&st);
			StackPop(&st);

		int mid = PartSort1(a, left, right);

		if (mid + 1 < right)
		{
			StackPush(&st,right);
			StackPush(&st,mid+1);

		}
		if (left < mid-1)
		{
			StackPush(&st,mid-1);
			StackPush(&st,left);

		}








	}

StackDestroy(&st);
}

int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
	QuickSort(arr, 0, 9);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ",arr[i]);


	}


}

归并排序

基本思想:
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并排序核心步骤:
在这里插入图片描述
在这里插入图片描述

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include<string.h>
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 begin2 = mid + 1;
	int end2 = end;
	int j = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[j++] = a[begin1++];
		}
		if (a[begin2] < a[begin1])
		{
			tmp[j++] = a[begin2++];
		}
}
	while (begin1 <= end1)
	{
		tmp[j++] = a[begin1++];

	}
	while (begin2 <= end2)
	{
		tmp[j++] = a[begin2++];

	}
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));





	
}
//归并排序
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
	
}
int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
	MergeSort(arr, 10);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ",arr[i]);


	}


}

在这里插入图片描述
0-0,1-1return回0-1,
在这里插入图片描述
2-2return回0-2
在这里插入图片描述
归并排序非递归版

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
	}
	int gap = 1;
	while (gap<n)
	{
		int j = 0;
		for (int 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;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				if (a[begin2] < a[begin1])
				{
					tmp[j++] = a[begin2++];
				}





			}
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];

			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];

			}













		}
		memcpy(a, tmp, sizeof(int) * n);
		gap *= 2;

	}
}
int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5 };
	MergeSortNonR(arr, 8);
	for (int i = 0; i < 8; i++)
	{
		printf("%d ",arr[i]);


	}


}

在这里插入图片描述
gap=1,两个两个排序,然后整体拷贝回去.
gap=2,四个四个排序,然后整体拷贝回去.
gap=8 八个排序,然后整体拷贝回去.

int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10 };
	MergeSortNonR(arr, 9);
	for (int i = 0; i < 9; i++)
	{
		printf("%d ",arr[i]);


	}


}

我们换成9个数据,发现程序崩溃.

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
	}
	int gap = 1;
	while (gap<n)
	{
		int j = 0;
		for (int 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;
			printf("gap=%d [%d,%d][%d,%d]\n",gap, begin1, end1, begin2, end2);
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				if (a[begin2] < a[begin1])
				{
					tmp[j++] = a[begin2++];
				}





			}
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];

			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];

			}













		}
		memcpy(a, tmp, sizeof(int) * n);
		gap *= 2;

	}
}

在这里插入图片描述
修正边界

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
	}
	int gap = 1;
	while (gap<n)
	{
		int j = 0;
		for (int 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 || begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				if (a[begin2] < a[begin1])
				{
					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) * (end2 - i + 1));











		}
		
		gap *= 2;

	}
}
int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10 };
	MergeSortNonR(arr, 9);
	for (int i = 0; i < 9; i++)
	{
		printf("%d ",arr[i]);


	}


}

1.修改边界后往回拷贝的就不是n了,而是这个end2 - i + 1
2.如果是9个数据的时候,最后一个数据在gap=8中才开始排序
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/342563.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

《移动通信原理与应用》——QAM调制解调仿真

目录 一、QAM调制与解调仿真流程图&#xff1a; 二、仿真结果&#xff1a; 三、Matlab仿真程序代码如下&#xff1a; 一、QAM调制与解调仿真流程图&#xff1a; QAM调制仿真流程图&#xff1a; QAM解调仿真流程图&#xff1a; 二、仿真结果&#xff1a; &#xff08;1&…

JOSEF约瑟 中间继电器JZ14-44Z/4 不带外罩和接线座

系列型号 JZ14-014Z/0中间继电器;JZ14-014Z/1中间继电器; JZ14-014Z/2中间继电器;JZ14-014Z/4中间继电器; JZ14-014J/0中间继电器;JZ14-014J/1中间继电器; JZ14-014J/2中间继电器;JZ14-014J/3中间继电器; JZ14-014J/4中间继电器;JZ14-140Z/0中间继电器; JZ14-140Z/1中间继…

Web06--JavaScript基础02

1、JS流程控制语句 JS与Java一样&#xff0c;也有三个流程控制语句&#xff1a; 顺序结构 选择结构 循环结构 1.1 选择结构 1.1.1 if结构 <script type"text/javascript">if (条件表达式) {代码块;} else if(条件表达式){代码块;} else {代码块;} </scr…

Flink中的容错机制

一.容错机制 在Flink中&#xff0c;有一套完整的容错机制来保证故障后的恢复&#xff0c;其中最重要的就是检查点。 1.1 检查点&#xff08;Checkpoint&#xff09; 在流处理中&#xff0c;我们可以用存档读档的思路&#xff0c;将之前某个时间点的所有状态保存下来&#xf…

MATLAB实现岭回归数学建模算法

岭回归&#xff08;Ridge Regression&#xff09;是一种线性回归的扩展&#xff0c;用于处理多重共线性&#xff08;multicollinearity&#xff09;的问题。多重共线性是指自变量之间存在高度相关性的情况&#xff0c;这可能导致线性回归模型的不稳定性和过拟合。 岭回归通过在…

风二西CTF流量题大集合-刷题笔记|基础题(4)

61.sql2 sql.pcapng flag{a3eb0ff8-e467-5036-7c9b-287f6848d5f3} 62.冰蝎2.0 swt1.pcapng flag{0867c25f69f0c62c970408ccefe29bb7} 64.gs哥斯拉流量4.0 gs.pcapng flag{0fffbfa87e5508955b397950502db0bd} 65.冰蝎web流量 webshell.pcapng flag{da2c30d9318a0d80b4bfa…

C++——IOStream

什么是IO&#xff1f; C语言和C&#xff0c;我们其实已经接触到了两个IO的概念 #include<stdio.h> #include<iostream> iostream&#xff0c;便是IO流&#xff0c;其中I表示in&#xff0c;O表示out&#xff0c;代表着用户的输入和终端的输出。在之前的C语法中&a…

【服务器】安装Docker环境

目录 &#x1f33a;【前言】 &#x1f33c;1. 打开Xshell软件 &#x1f33b;2. 安装Docker环境 ①&#xff1a;下载docker.sh脚本 ②&#xff1a;列出下载的内容 ③&#xff1a;执行一下get-docker.sh文件&#xff0c;安装docker ④&#xff1a;运行docker服务 ⑤&…

内网安全管理系统(保密管理系统)

在当今信息化的时代&#xff0c;企业的内网已经成为其核心资产的重要组成部分。 随着企业的快速发展和信息化程度的提升&#xff0c;内网安全问题日益凸显&#xff0c;如何保障内网的安全和机密信息的保密性&#xff0c;已经成为企业亟待解决的问题。 内网安全管理系统(保密管…

定时任务组件Quartz

Quartz介绍 Quartz 是一个功能丰富的开源作业调度库&#xff0c;几乎可以集成到任何 Java 应用程序中 - 从最小的独立应用程序到最大的电子商务系统。Quartz 可用于创建简单或复杂的计划&#xff0c;以执行数十、数百甚至数万个作业;其任务被定义为标准 Java 组件的作业&#x…

了解HTTP/1.1、HTTP/1.0 和 HTTP/2.0

HTTP/1.1、HTTP/1.0 和 HTTP/2.0 是超文本传输协议&#xff08;HTTP&#xff09;的三个主要版本 先解释一下什么是超文本协议 超文本传输协议&#xff08;HyperText Transfer Protocol&#xff0c;简称 HTTP&#xff09;是互联网上应用最广泛的一种网络协议。设计 HTTP 的初衷是…

STM32(--001) Win10、Win11 上的驱动安装说明

一、USB线插到 CMSIS-DAP 接口上&#xff0c;将自动识别到两个设备 ① CMSIS-DAP&#xff1a;用于烧录代码、在线硬件仿真; 在Keil里烧录&#xff0c;无需通过FlyMCU; ② USB转TTL&#xff1a;用于开发板与电脑间串口通信 &#xff0c;即USART1, TX-PA9、RX-PA10; 接口备注&a…

Vue前端环境搭建以及项目搭建

安装node.js 安装node.js主要是为了安装npm工具&#xff0c;用于管理js包等&#xff0c;类似于java的maven。 去官网下载安装。 配置新的镜像源 npm config set registry https://registry.npmmirror.com安装webpack webpack是前端项目打包工具。 命令&#xff1a; npm…

2023年春秋杯网络安全联赛冬季赛 Writeup

文章目录 Webezezez_phppicup Misc谁偷吃了外卖modules明文混淆 Pwnnmanagerbook Reupx2023 CryptoCF is Crypto Faker 挑战题勒索流量Ezdede 可信计算 Web ezezez_php 反序列化打redis主从复制RCE&#xff1a;https://www.cnblogs.com/xiaozi/p/13089906.html <?php c…

【办公类-22-01】20240123 UIBOT逐一提取CSDN质量分

背景需求&#xff1a; 最近每天传2份Python&#xff0c;发现平均分从73.5降到了72.7。网上搜索一下原因&#xff0c;发现每篇CSDN都有一个评分&#xff08;以下是查分网站&#xff09; https://www.csdn.net/qchttps://www.csdn.net/qc 但是一篇一篇查询&#xff0c;显然太繁…

【图论--搜索篇】宽度优先搜索,广度优先搜索

今日语录&#xff1a;成功是一种心态&#xff0c;如果你相信自己能做到&#xff0c;那你已经迈出成功的第一步。 文章目录 宽度优先搜索&#xff08;bfs&#xff09;广度优先搜索&#xff08;dfs&#xff09; 宽度优先搜索&#xff08;bfs&#xff09; #include <iostream&…

(M)unity2D敌人的创建、人物属性设置,遇敌掉血

敌人的创建 1.敌人添加与组件设置 1&#xff09;添加敌人后&#xff0c;刚体添加&#xff0c;碰撞体添加&#xff08;一个碰撞体使猪在地上走&#xff0c;不接触人&#xff0c;另一个碰撞体组件使人和猪碰在一起产生伤害&#xff09; ①刚体 ②碰撞体一 设置的只在脚下&a…

图书管理系统-Python

相关代码&#xff1a; # Time: 2024/1/23 16:16 # Author: 马龙强 # File: 图书管理系统.py # software: PyCharm class Book():def __init__(self,name,auther,status,bookindex):self.name nameself.auther autherself.status statusself.bookindex bookindexdef __str…

【第十五课】数据结构:堆 (“堆”的介绍+主要操作 / acwing-838堆排序 / c++代码 )

目录 关于堆的一些知识的回顾 数据结构&#xff1a;堆的特点 "down" 和 "up"&#xff1a;维护堆的性质 down up 数据结构&#xff1a;堆的主要操作 acwing-838堆排序 代码如下 时间复杂度分析 确实是在写的过程中频繁回顾了很多关于树的知识&…

华为发布 HarmonyOS NEXT 鸿蒙星河版

文章目录 个人简介 在 2024-01-18 下午于深圳举办的鸿蒙生态千帆启航仪式上&#xff0c;华为常务董事兼终端BG CEO余承东宣布了HarmonyOS NEXT&#xff08;鸿蒙星河版&#xff09;的开发者预览版面向开发者开放申请。这一版本旨在实现六大极致原生体验&#xff0c;包括原生精致…