gpt4 book ai didi

算法:C++ 实现 快速排序、归并排序

转载 作者:知者 更新时间:2024-03-13 02:45:12 24 4
gpt4 key购买 nike

1、快速排序

快速排序:说白了就是给基准数据找其正确索引位置的过程。

  1. 设置最开始的基准数据定义为数组中间的元素,用变量去存储基准数据,即mid=a[头+尾)/2];
  2. 以mid为界,然后分别从数组的两端扫描数组,设两个指示标志:begin指向起始位置,end指向末尾。当begin与end相遇前,交换位置的值,直到两者相遇。
  3. 重新调用函数qsort(),直到不满足条件if(h<end);if(begin<r)。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int Max = 100; //定义数组长度 
int a[Max];
void qsort(int,int);

int main(){
	int n,i;
	cout<<"输入n个整数:";
	cin>>n;
	cout<<"每个整数按空格隔开:"<<endl; 
	for(i=1;i<=n;i++) 	//输入数据 
		cin>>a[i];
	qsort(1,n);			//调用函数 
	
	cout<<"快速排序结果:"<<endl; 
	for(i=1;i<=n;i++)	//输出数据 
		cout<<a[i]<<" ";
	cout<<endl;
}

void qsort(int h,int r){
	int begin,end,mid,p;
	begin=h;	//标记开头 
	end=r;		//标记尾巴 
	mid=a[(h+r)/2];	// 定义数组中间的元素基准数 
	do
	{
		while(a[begin]<mid) begin++; //左部分寻找比中间大的数位置 
		while(a[end]>mid) end--;	//右部分寻找比中间小的数位置
		if(begin<=end) //找到位置,交换值,直到两个标记相遇 
		{ //在左边数比mid大 or 右边数比mid小的情况-->交换值
			p=a[begin];
			a[begin]=a[end];
			a[end]=p;
			begin++;
			end--; 
		}
	}while(begin<=end);
// 一趟过后,begin>end; mid的左边数<mid; mid的右边数>mid;
	if(h<end) //mid左边满足条件 
		qsort(h,end); // 递归->对h,end的范围进行qsort()判断 
	if(begin<r) //mid右边满足条件 
		qsort(begin,r);	// 递归->
}

快速排序是不稳定的排序方法,时间复杂度是O(nlog2n),速度快,平均时间来说,快速排序是最好的一种内部排序方法。但快速排序需要一个栈空间实现递归,每一趟排序都会将记录序列分割成两个子序列,栈最大深度为log(n+1)。

2、归并排序

归并的思路(分治)是把一个大问题a拆解成两个小问题b和c,解决了两个子问题再整合一下,就解决了原问题。用递归的方法,先分解再合并(分治是一种解决问题的处理思想,递归是一种编程技巧,这两者并不冲突)。

  • 稳定性:稳定;
  • 空间复杂度O(n);
  • 复杂度:时间复杂度O(nlogn);
  • 优缺点:效率高且稳定,但是消耗的辅助空间与原数据空间成正比。

1. 若low>high,则将序列分从中间mid=(low+high)/2分开;
2. 对左半部分[low, mid]递归地进行归并排序;
3. 对右半部分[mid+1, high]递归地进行归并排序;
4. 将左右两个有序子序列Merge为一个。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int Max = 1000; //定义数组长度 
int a[Max]; //定义数组 
int r[Max]; //定义辅助函数 

void merge(int a[],int low,int mid,int high){ //2.3
	int i=low,j=mid+1,k=low;  //i,j标记mid分割后左右序列的首位置,k记录序列首位置 
	for(k;k<=high;k++) //把数组a复制到数组r上; 
		r[k]=a[k];
		
	for(k=i;i<=mid && j<=high; k++){ //在范围内
		if(r[i]<=r[j]) 	  //比较左、右序列的值,把小的值存在数组a;
			a[k]=r[i++]; //以此类推,保证数组a[]顺序存储从小到大; 
		else
			a[k]=r[j++];
	}	//剩下的不在在范围内 
	while(i<=mid) a[k++]=r[i++];   //保存到数组a[]后面 
	while(j<=high) a[k++]=r[j++];
}

void msort(int a[],int low,int high){ //2.1
	if(low<high){
		int mid=(low+high)/2;
		msort(a,low,mid);
		msort(a,mid+1,high);	//当函数msort()递归到只有一个元素组成的序列
		merge(a,low,mid,high);  //2.2 就调用这个方法 
	}
}
int main(){
	int n;
	cout<<"输入n个整数:";
	cin>>n;
	cout<<"每个整数按空格隔开:"<<endl; 
	for(int i=1;i<=n;i++) 	//1、输入数据 
		cin>>a[i];
	msort(a,1,n);	//2、调用函数 
	cout<<"归并排序结果:"<<endl; 
	for(int i=1;i<=n;i++)	//3、输出数据 
		cout<<a[i]<<" ";
	cout<<endl;
}

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com