初探几种排序算法

青旅半醒 2022-08-08 06:40 199阅读 0赞

多种排序算法的总结(不包括复杂度的详细推算）

稳定排序与不稳定排序

稳定排序：相同元素在排序中的相对位置不改变。

不稳定排序：相同元素在排序中的相对位置改变。

内部排序与外部排序：

内部排序：待排的记录与内容都放在计算机的随机存储器中进行的排序过程

外部排序：一般指待排序记录的数量很大，以致内存中一次不能完全容纳全部的记录，在排序过程中，需要对外存进行访问的排序过程。

排序算法的复杂度：

在此我们一般只要考虑的就是时间复杂度，当然个别排序的空间复杂度也很大，如希尔排序。这里时间复杂度的计算方法和一般复杂度计算方法类似。

按照排序的过程中所依据的不同可以分类为：

插入排序，交换排序，选择排序，归并排序，基数排序，二叉排序树排序

插入排序：

利用有序表的插入操作进行排序

有序表的插入：将一个记录插入到已经安排好的有序表中，从而得到一个新的有序表。

直接插入排序算法主要应用比较和移动两种操作。

void insertsort(int R[],int n){
 	int i,j,temp;
 	for(i=1;i<n;i++)
 	{
 		temp=R[i];
 		j=i-1;
 		while((j>=0)&&(temp<R[j]))
 		{
 			R[j+1]=r[j];
 			j--;
 		}
 		R[j+1]=temp;//put single on first
 	}

希尔排序（有一种直接插入排序的改进）

方法：先将待排序列分割成为若干的子序列分别进行直接插入排序；待整个序列中的记录基本有序后，在进行一次直接插入排序。

希尔排序的时间复杂度：

O（nlog2n)和O（N平方）之间大约O（N的1.3次方）

void shellsort(int a[],int arrsize)
 {
 	int temp;
 	int gap=arrsize/2;
 	while(gap != 0){
 		for(int i=gap;i<arrsize;i++){
 			temp=a[i];
 			for(int j=i;j>=gap;j-=gap){
 				if(temp < a[j-gap])
 					a[j]=a[j-gap];
 				else
 					break;
 			}
 			a[j] = temp;
 		}
 		gap = (int)(gap/2);
 	}
 }

交换排序--冒泡排序

思想：通过不断比较相邻元素的大小，进行交换实现排序

void bubblesort(int a[],int n)
 {
 	int flag = 1;
 	for(i=1;i<n;i++)
 	{
 		flag=0;
 		for(int j=n-1;j>=i;j--)
 			if(R[j]<R[j-1])
 			{
 				t = R[j];
 				R[j]=R[j-1];
 				R[j-1]=t;
 				flag=1;
 			}
 		if(flag==0)
 			return ;
 	}
 }

交换排序--快速排序

冒泡排序的一种改进算法

思想：以首记录作为轴记录，从前，后向扫描序列，通过交换，实现大值记录后移，小值记录前移，最终将轴记录安置在一个适当的位置（小值记录在前，大值记录在后）

轴记录将原序列分割成两个部分，依次对前后两部分重新设定轴记录，继而分别在进行快速排序。直至整个序列有序。

快速排序----分割过程

快速排序是一个分治的算法

对于一个序列，取它的一个元素作为轴，把所有小与轴的元素放在它的左边，大于它的元素放在它的右边

分割算法：

用临时变量对轴进行备份

取链噶个指针LOW 和HING ，他们的初始值就是序列的两端小表，在整个过程中保证LOW 不大于HIGH

移动两个指针

首先从HING 所知的位置向左搜索，找到第一个小与轴的元素，把这个元素放在LOW 的位置

在从LOW开始向右，找到第一个大与轴的元素，把它放在HING 的位置

重复上述过程，直到LOW=HIGH

把轴放在LOW 所指的位置

这样所有大于轴的元素北方在右边，所有小与轴的元素被放在左边。

void Fquick_sort(int *addr,int low,int high)
 {
 	int lowpos = low;
 	int highpos= high;
 	int povite = addr[low];
 	if(lowpos >= highpos){
 		return ;
 	}
 	while(lowpos < highpos){
 		while((lowpos < highpos)&&(add[highpos]>=povite)){
 			highpos--;
 		}
 		if(lowpos < highpos){
 			addr[lowpos] = addr[highpos];
 			lowpos++;
 		}
 		while((lowpos < highpos)&&(addr[lowpos]<=povite)){
 			lowpos++;
 		}
 		if(lowpos < highpos){
 			addr[highpos]=addr[lowpos];
 			highpos--;
 		}
 	}
 	addr[lowpos]=povit;
 	Fquick_sort(addr,low,lowpos-1);
 	Fquick_sort(addr,lowpos+1,high);
 	return ;
 }

时间复杂度：平均O（nlog2n)

空间复杂度：O（N平方）

快速排序是一种不稳定的排序方法

简单选择排序：

每一趟都选出一个最大或最小的元素，并放在适当的位置。

void selsectSort(int a[],int n)
 {
 	int i,j;
 	int temp;
 	for(i=0;i<n-1;i++)
 		for(j=i+1;j<n;j++)
 		{
 			if(a[i]>a[j])
 			{
 				temp=a[i];
 				a[i]=a[j];
 				a[j]=a[i];
 			}
 		}
 }

归并排序：

思想：将两个有序的序列合并成一个有序的序列，所以如果只有两个元素，所以归并排序就是将一个序列不停拆分，直到拆成一个一个元素为止，然后再进行合并排序。

void merge(int *add,int len)
 {
 	int lenA = 0,lenB = 0,lenC = 0,lentmp = 0;
 	int *arrC = NULL;
 	if(len <= 1){
 		return ;
 	}
 	arrC = (int *)malloc(len*sizeof(int));
 	lentmp = len/2;
 	merge(add,lentmp);
 	merge(&add[lentmp],len-lentmp);
 	lenA = 0;lenB = lentmp;
 	lenC = 0;
 	while((lenA != lentmp)&&(lenB != len)){
 		if(add[lenA]<add[lenB]){
 			arrC[lenC] = add[lenA];
 			lenA++;
 		}else{
 			arrC[lenC] = add[lenB];
 			lenB++;
 		}
 		lenC++;
 	}
 	if(lenA == lentemp){
 		while(lenB < len){
 			arrC[lenC++]=add[lenB++];
 		}
 	}else if(lenB == len){
 		while(lenA < lentmp){
 			arrC[lenC++]=add[lenA++];
 		}
 	}else{
 		//printf("all ok !\n");
 	memcpy(add,arrC,len*sizeof(int));
 	free(arrC);