区块链技术博客
www.b2bchain.cn

白话讲解排序算法

这篇文章主要介绍了白话讲解排序算法的讲解,通过具体代码实例进行20146 讲解,并且分析了白话讲解排序算法的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=20146

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

我是自动化专业的应届研究生,最终拿到了tplink、华为、vivo等公司的ssp的offer,分享自己学习过的计算机基础知识(C语言+操作系统+计算机网络+linux)以及数据结构与算法的相关知识,保证看完让你有所成长。
欢迎关注我,学习资料免费分享给你哦!还有其他超多学习资源,都是我自己学习过的,经过过滤之后的资源,免去你还在因为拥有大量资源不知如何入手的纠结,让你体系化学习。
白话讲解排序算法

文章目录

        • 内部排序
          • 插入排序
          • 冒泡排序
          • 希尔排序
          • 堆排序
          • 归并排序
          • 快速排序
          • 排序算法时间复杂度总结

内部排序

排序算法因为数据量的不同,就是一次是否可以全部读入内存分为外部排序和内部排序。内部排序就是数据可以一次全部读入内存的情况。

插入排序

插入排序就是从头至尾逐渐有序的过程。对于一个数组A,从下标为i=1开始,首先将下标为1的元素取出A[1],暂时存储起来tmp。然后逐渐与i前面的元素比较,只要元素比tmp大,那么就需要将这个元素后移,这也是为什么需要暂时把A[1]存储起来,因为防止把前面元素后移的时候把这个值覆盖。这样直到比较到比tmp小的,此时说明tmp应该插入到这个位置上。这就是插入排序的基本思路。来看一下具体的过程。

白话讲解排序算法

首先i等于1,将A[1]=15存入tmp,然后比较A[0]与tmp,发现A[0]大于tmp,所以将A[0]后移到A[1],然后A[0]已经到了数组的界限,不能在比较了,所以tmp插入到A[0]处。然后此时i加1,等于2,将A[2]的元素取出放在tmp中。

白话讲解排序算法

重复之前的步骤,比较A[1]和tmp,发现40大于21,那么将40后移。
白话讲解排序算法

在比较A[0]和tmp,发现A[0]小于tmp,那么此时说明A[0]前面的所有元素都是比tmp小的(如果A[0]前面还有元素的话,因为我们是从首开始进行的插入排序,说明A[i]以前的元素都是排序好的,如果有一个元素比A[i]小的话,那么它前面的所有元素都是比tmp小的。)此时将tmp插入到A[1].然后在将i+1,此时i等于3,将A[3]放入tmp。
白话讲解排序算法

此时比较A[2]与tmp,发现A[2]比tmp小,说明tmp还是插入在A[3]处,还是前面所说A[2]前面都是排好序的,如果A[2]比tmp小,那么A[2]之前的所有元素都比tmp小。这就是插入排序的基本过程。下面来看实现代码。

//A是数据的数组,n是数组中元素的个数 void insert_sort(int *A,int n) {    int i,j,tmp;    for(i=1;i<n;i++)    { 	   tmp=A[i]; 	   for(j=i;j>0&&A[j-1]>tmp;j--) 	   { 		   A[j]=A[j-1]; 	   } 	   A[j]=tmp;    } } 
冒泡排序

冒泡排序的思路与插入排序不同,它是将已经排好序的数据放在最后,逐渐缩小需要排序的范围,最开始是整个数组A的大小n,从数值的开始比较j=0,如果A[j]>A[j+1],那么就交换两个元素,这样就保证了A[j+1]是两者之间最大的,然后j=j+1,然后继续比较A[j]与A[j+1],如果A[j]>A[j+1],那么继续交换两个元素。直到比较到j+1==(n-1)为止,因为每一次都是相当于把j之前的元素最大值与A[j+1]比较,所以这一轮下来之后,就是把数组中的最大值放在了数组的最后一个位置。然后下一轮的排序就会比较到n-2停止,就是把数组中第二大的元素放在数组的倒数第二个位置了,如此反复,实现了排序。

白话讲解排序算法

首先比较21和15,21大于15,所以交换,然后将j加1.

白话讲解排序算法

然后比较21和40,21小于40,不交换。将j加一。

白话讲解排序算法

比较40与100,40小于100,不交换。将j加一。

白话讲解排序算法
比较100与24,100大于24,交换两个元素。j加一。可以看到j所指向的元素,一定是j扫描过的最大元素,但j扫描过的不一定有序,下标0-3都是扫描过的,但是并不满足递增的顺序。
白话讲解排序算法
最后比较100与31,100大于31,将100和31交换。完成了一轮排序。此时最后一个元素就是数组中最大的元素,然后将比较界限前移一个位置,j从0重新开始扫描,直到比较界限达到1,这就完成了排序。

白话讲解排序算法

懂了基本思想,就可以将其转换为代码了,如下:

void swap(int *a,int *b) { 	int tmp; 	tmp=*a; 	*a=*b; 	*b=tmp; } void bubble_sort(int *A,int n) { 	int i,j; 	for(i=n-1;i>0;i--) 	{ 		for(j=0;j<i;j++) 		{ 			if(A[j]>A[j+1]) 			{ 				swap(&A[j],&A[j+1]); 			} 		} 	} } 

假如在某一轮循环之后,数组已经是排好序的了,也就是没有必要在继续去循环了,那么应该采用什么办法呢?其实很简单,就是判断是否发生了交换,如果一轮循环判断下来,没有发生交换,说明已经排好序了,所以这个时候停止就可以了。

void swap(int *a,int *b) { 	int tmp; 	tmp=*a; 	*a=*b; 	*b=tmp; } void bubble_sort(int *A,int n) { 	int i,j; 	int flag=0; 	for(i=n-1;i>0;i--) 	{ 		flag=0; 		for(j=0;j<i;j++) 		{ 			if(A[j]>A[j+1]) 			{ 				swap(&A[j],&A[j+1]); 				flag=1; 			} 		} 		if(flag==0) 		{ 			break; 		} 	} } 
希尔排序

希尔排序其实就是改进版本的插入排序,它不是直接对于所有数据做插入排序,而是采用了将数据分组,一个组一个组的做插入排序,然后将分组扩大,在插入排序,直到分组就是整个数组,完成排序。

白话讲解排序算法

假设有如上的待排序数组,首先选取分组的间隔,将数组分组,首先选取incre=n/2=6/2=3,那么就有如下分组

白话讲解排序算法

然后每个分组分别插入排序,可以得到如下的顺序:21,24;15,100;31,40;

白话讲解排序算法

然后缩小incre=incre/2=1,这样就是整个数组进行插入排序,就可得到排序完成的数组了。

白话讲解排序算法

写成代码如下:

void shell_sort(int *A,int n) { 	int i,j,ins,tmp; 	for(ins=n/2;ins>0;ins=ins/2) 	{ 		for(i=ins;i<n;i++) 		{            tmp=A[i]; 		   for(j=i;j>=ins&&A[j-ins]>tmp;j-=ins) 		   { 			   A[j]=A[j-ins]; 		   } 		   A[j]=tmp; 		} 	} } 
堆排序

堆排序的思路其实很简单,在最大堆中,最大的元素在数组首地址处,那么只需要将最大值与数组最后一个值交换,然后将堆的大小缩小1,原来的范围为0-n-1,现在n-1下标处已经存放了最大值的元素,然后将堆的范围缩小至0-n-2,就是相当于堆的删除操作,然后重新将0-n-2的堆重新构造成最大堆,本质就是删除操作,只是将删除后的元素放在了数组的后面。

//这里与堆不同的地方在于没有哨兵了,父节点下标为i,那子节点下标为2*i+1、2*i+2 void perdown(int *A,int d,int n) { 	int parent,child; 	int data; 	data=A[d]; 	for(parent=d;parent*2+1<n;parent=child) 	{ 		child=parent*2+1; 		if((child+1)<n&&(A[child]<A[child+1])) 		{ 			child++; 		} 		if(data>=A[child]) 		{             break; 		} 		A[parent]=A[child]; 	} 	A[parent]=data; }  void heap_sort(int *A,int n) { 	int i; 	for(i=(n-1)/2;i>=0;i--) //将数组构建为最大堆 	{ 		perdown(A,i,n); 	} 	for(i=n-1;i>0;i--) 	{ 		swap(&A[0],&A[i]);  //将最大交换到堆的最后一个位置 	    perdown(A,0,i);//重新构建最大堆 	} } 
归并排序

归并排序是采用了递归的思想来逐渐将数组分成两个部分,比如一个数组有6个元素,首先分成两个部分,前3个为一组,后3个为一组。
白话讲解排序算法

然后继续分组。

白话讲解排序算法

将每个元素分到最小之后,然后每两个进行合并,合并的时候按照顺序合并,如下图15和21合并时交换了位置。

白话讲解排序算法
白话讲解排序算法

然后继续合并,直达整个数组排好顺序。这就是归并的思路,首先将排序的数组分离,分离之后在逐渐按照顺序合并。

void merge(int *A,int *tmp,int left,int right,int right_end) { 	int left_end,tmpPos=left,lengthofdata; 	left_end=right-1; 	lengthofdata=right_end-left+1; 	while(left<=left_end&&right<=right_end) 	{ 		if(A[left]<A[right]) 		{ 			tmp[tmpPos++]=A[left++]; 		} 		else 		{             tmp[tmpPos++]=A[right++]; 		} 	} 	while(left<=left_end) 	{         tmp[tmpPos++]=A[left++]; 	} 	while(right<=right_end) 	{         tmp[tmpPos++]=A[right++]; 	} 	for(lengthofdata;lengthofdata>0;lengthofdata--,right_end--) 	{ 		A[right_end]=tmp[right_end]; 	}  } void mergesort(int *A,int *tmp,int left,int right_end) { 	int right; 	if(left>=right_end) 	{ 		return; 	} 	right=(left+right_end)/2; 	mergesort(A,tmp,left,right); 	mergesort(A,tmp,right+1,right_end); 	merge(A,tmp,left,right+1,right_end); } void merge_sort(int *A,int n) { 	int *tmp; 	tmp=(int *)malloc(sizeof(int)*n); 	if(tmp!=NULL) 	{ 		mergesort(A,tmp,0,n-1); 		free(tmp); 	} 	else 	{ 		printf("内存不足"); 	} } 
快速排序

快速排序基本思想与归并排序类似,归并排序一个是按照等分的策略,将待排序的数组分成两部分,然后迭代处理;另一点是需要额外的空间。快速排序不同的地方是不是等分的策略而是选取一个值作为参考值,将这次排序区域中的比它小的放到左边,比它大的放在右面,然后将左面和右面分别按照这种办法进行递归求解,直到待排序的值只有一个为止。
白话讲解排序算法
以上面数组为例,首先选取一个数字作为分界的参考值,这里以数组的第一个元素作为参考值,x=A[0],之后从数组的最前面和最后面开始扫描数组,过程是这样的,定义i=0,j=9,

白话讲解排序算法

从A[j]开始比较,如果A[j]>=x,那么j就前移,即j–,如果A[j]<x,那么就将这个值插入到A[i]中,因为A[i]的值已经保存到了X中,然后i++,在从A[i]开始比较。如果A[i]<x,就i向前移动,即i++。

白话讲解排序算法

下图所示,直到i移动到83这个位置,此时A[i]>=x。

白话讲解排序算法

此时将83插入到A[j]的位置,然后j前移,在从A[j]处重复上述过程,直到i>=j结束。
白话讲解排序算法

这样就完成了一次快速排序,红色部分左侧比72小,右侧比72大,然后将左侧下标为0-4的数据进行上述过程,右侧下标为7-9的数据进行上述过程,直到只有一个数据。就完成了快速排序,代码如下:

void q_sort(int *A,int left,int right_end) { 	int privot,i,j; 	privot=A[left];     i=left;     j=right_end; 	if(i<j) 	{ 		 		while(1) 		{ 			while(i<j&&A[j]>=privot) 			{ 				j--; 			} 			if(i<j) 			{ 				A[i++]=A[j]; 			} 			while(i<j&&A[i]<privot) 			{ 				i++; 			} 			if(i<j) 			{ 				A[j--]=A[i]; 			} 			else 			{ 				break; 			} 		} 		A[i]=privot; 		q_sort(A,left,i-1); 		q_sort(A,i+1,right_end);     } } //为了使排序接口一致 void quick_sort(int *A,int n) {     q_sort(A,0,n-1);	 } 
排序算法时间复杂度总结
排序方法 平均时间复杂度 最坏时间复杂度 额外空间复杂度 稳定性
插入排序 O(n^2) O(n^2) O(1) 稳定
冒泡排序 O(n^2) O(n^2) O(1) 稳定
归并排序 O(nlogn) O(nlogn) O(n) 稳定
希尔排序 O(n^d) O(n^2) O(1) 不稳定
堆排序 O(nlogn) O(nlogn) O(1) 不稳定
快速排序 O(nlogn) O(n^2) O(logn) 不稳定

本文转自互联网,侵权联系删除白话讲解排序算法

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 白话讲解排序算法
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们