算法设计与分析实验2 ：利用蛮力法、减治法和分治法解决排序问题

最新推荐文章于 2025-05-08 21:44:07 发布

Blossom i

最新推荐文章于 2025-05-08 21:44:07 发布

阅读量1k

点赞数 11

分类专栏：算法设计文章标签：算法排序算法数据结构

本文链接：https://blog.csdn.net/weixin_60530224/article/details/135655109

版权

本文介绍了利用蛮力法（选择排序、冒泡排序）、减治法（插入排序）和分治法（合并排序、快速排序）解决排序问题的实验。实验详细阐述了各种排序算法的原理、核心代码实现，以及时间复杂度和空间复杂度分析。实验总结指出，根据输入规模和数据特性选择合适的排序算法，如小规模数据用选择排序或插入排序，大规模且要求速度时用快速排序或合并排序。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

算法设计与分析实验2 利用蛮力法、减治法和分治法解决排序问题

一、实验目的

二、实验内容和要求

【选择排序函数原型及功能说明】

【核心函数实现代码及时间复杂度与空间复杂度分析】

【冒泡排序函数原型及功能说明】

【核心函数实现代码及时间复杂度与空间复杂度分析】

【插入排序函数原型及功能说明】

【核心函数实现代码及时间复杂度与空间复杂度分析】

【合并排序函数原型及功能说明】

【核心函数实现代码及时间复杂度与空间复杂度分析】

【快速排序函数原型及功能说明】

【核心函数实现代码及时间复杂度与空间复杂度分析】

算法设计与分析实验2 利用蛮力法、减治法和分治法解决排序问题

一、实验目的

1. 掌握蛮力法、减治法和分治法的思想与实现。

2. 掌握利用利用蛮力法、减治法和分治法解决排序问题。

3. 分析核心代码的时间复杂度和空间复杂度。

二、实验内容和要求

基于蛮力法（选择排序、冒泡排序）、减治法（插入排序）和分治法（合并排序、快速排序）的思想分别编写一个排序算法。

【选择排序函数原型及功能说明】

选择排序开始的时候，我们扫描整个列表，找到它的最小元素，然后和第一个元素交换，将最小元素放到它在有厅表中的最终位置上。然后我们从第二个元素开始扫描列表，找到最后n-1个元素中的最小元素，再和第二个元素交换位置,把第二小的元素放在它的最终位置上。一般来说，在对该列表做第i遍扫描的时候(i的值从0到n-2)，该算法在最后n-i个元素中寻找最小元素，然后拿它和A交换。

算法 SelectionSort(A[0..n-1])

//该算法用选择排序对给定的数组排序//输入:一个可越序数组 A[0..n-1]

//输出:升序排列的数组A[0..-9年-1n

For i←0 ton-2 do

Min ← i

for j←i+l to n-l do

if A[j]< A[min] min ← j

swap A[i] and A[min]

【核心函数实现代码及时间复杂度与空间复杂度分析】

void SelectSort(int A[],int n)
{
	int i,j,min,temp;
    for(i = 0;i <= n-2;i++)  //最外层遍历
	{
		min=i;
		for(j = i+1;j < n;j++) //开始找无序区的最小元素
		if(A[j] < A[min]) 
			min=j;   //记录最小值
        if(min!=i)
		{
    
			temp=A[i];
			A[i]=A[min]; 
			A[min]=temp; //将最小值放到有序区中
  }
 }
}

时间复杂度：O（n^2）

空间复杂度：O（1）

完整代码

#include <stdio.h>
void SelectSort(int A[],int n)
{
	int i,j,min,temp;
    for(i = 0;i <= n-2;i++)  //最外层遍历
	{
		min=i;
		for(j = i+1;j < n;j++) //开始找无序区的最小元素
		if(A[j] < A[min]) 
			min=j;   //记录最小值
        if(min!=i)
		{
    
			temp=A[i];
			A[i]=A[min]; 
			A[min]=temp; //将最小值放到有序区中
  }
 }
}
void disp(int a[],int n)  //输出a中所有元素
{ 
	int i;
 for (i=0;i<n;i++)
  printf("%d ",a[i]);
 printf("\n");
}

int main()
{ 
	int n=10;
	int a[]={2,5,1,7,10,6,9,4,3,8};
	printf("排序前:"); disp(a,n);
	SelectSort(a,n);
	printf("排序后:"); disp(a,n);
}

【冒泡排序函数原型及功能说明】

蛮力法在排序问题上还有另一个应用之它比较表中的相邻元素，如果它们是逆序的话

就交换它们的位置。重复多次以后，最终，最大的元素就“沉到”列表的最后一个位置。

第二遍操作将第二大的元素沉下去。这样一直做，直到n-1遍以后，该列表就排好序了。

算法 BubbleSort(A[0..n-1])

//该算法用冒泡排序对数组 A[0..n-1]进行排序/输入:一个可排序数组 A[0..n-1]

//输出:非降序排列的数组A[0..n-1]

For i←b to n-2 do

for j←0 to n-2-i do

if A[ j+1]< A[j]

swap A[j]and A[j+1]

【核心函数实现代码及时间复杂度与空间复杂度分析】

void BubbleSort(int A[],int n)
{
 int i, j;
 int temp;
 for(i = 0; i < n-2; i++)
 {
  for (j = 0; j <= n-2-i; j++)
  {
   if(A[j + 1] < A[j])
   {
    temp = A[j];
    A[j] = A[j + 1];
    A[j + 1] = temp;
   }
  }
 }
}

时间复杂度：O（n^2）

空间复杂度：O（1）

完整代码1

#include <stdio.h>
void swap(int &x,int &y)  //交换x和y
{ int tmp=x;
 x=y; y=tmp;
}
void BubbleSort(int A[],int n) //对a[0..n-1]按递增有序进行冒泡排序
{ 
	int i,j;

	bool exchange;
 
	for (i=0;i<n-1;i++)  //进行n-1趟排序
 
	{ 
	
		exchange=false;  //本趟排序前置exchange为false
  
		for (j=n-1;j>i;j--) //无序区元素比较,找出最小元素
   
			if (A[j]<A[j-1])  //当相邻元素反序时
   
			{ 
	   
				swap(A[j],A[j-1]); //a[j]与a[j-1]进行交换
    
				exchange=true;//本趟排序发生交换置exchange为true
   
			}
  
			if (exchange==false) //本趟未发生交换时结束算法
  
				return;

	}

}

void disp(int a[],int n)  //输出a中所有元素

{ 
	int i;
 
	for (i=0;i<n;i++)
  
		printf("%d ",a[i]);
 
	printf("\n");

}
int main()
{ 
	int n=10;
 
	int a[]={2,5,1,7,10,6,9,4,3,8};
 
	printf("排序前:"); disp(a,n);
 
 
	BubbleSort(a,n);
 
	printf("排序后:"); 
	disp(a,n);
	return 0;
}

完整代码2