数据结构 | 第九章内部排序

淡淡的烟草味﹌ 2021-11-27 01:50 317阅读 0赞

**(一) 排序的基本概念**  
这个博主的超级详细：[https://blog.csdn.net/weixin\_41190227/article/details/86600821][https_blog.csdn.net_weixin_41190227_article_details_86600821]  
之前总结的：[https://blog.csdn.net/qq\_43145926/article/details/89964296][https_blog.csdn.net_qq_43145926_article_details_89964296]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2_size_16_color_FFFFFF_t_70]

*  排序是否稳定：会不会因为关键字变化而排序结果不一致。
 *  内部排序：待排序记录存放在计算机随机存储器中进行排序过程。
 *  外部排序：待排序记录的数量很大，以至于内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问排序的过程。

**(二) 插入排序**

*  直接插入排序 时间复杂度O（n^2）  
    把无序序列的第一个未排序的记录插入到已排序的相应位置。

void Insertsort(SqList &L)
    { 
    	for(i=2;i<=L.length;++i)
    		if(LT(L.r[i].key,L.r[i-1].key))//"<" 需将L.r[i]插入有序表{ 
    		L.r[0]=L.r[i]; //复制为哨兵 
    		L.r[i]=L.r[i-1];
    		for(j=i-2;LT(L.r[0].key,L.r[j].key);--j)
    			L.r[j+1]=L.r[j];//记录后移
    		L.r[j+1]=L.r[0]; //插入到正确位置
    		}
    	}

*  折半插入排序  
    时间复杂度O（n^2）

void BInertSort (SqList &L)
    { 
    	for(i=2;i<=L.length;++i)
    	{ 
    		L.r[0]=L.r[2];//将i暂存到0中
    		low=1;high=i-1;
    		while(low<j=high){ 
    			m=(low+high)/2;
    			if(LT(L.r[0].key,L.r[m].key)) high=m-1;
    			else low=m+1;
    		}//while
    		for(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j];//记录后移
    		L.r[high+1]=L.r[0]; //插入
    	}//for
    }

*  希尔排序  
    缩小增量排序。时间复杂度O（nlogn）

void ShellInsert (SqList &L, int dk)
    { 
    	for(i=dk+1;i<=L.length;++i)
    		if(LT(L.r[i].key,L.r[i-dk].key))//需将L.r[i]插入有序增量子表
    		{ 
    		L.r[0]=L.r[i];//暂存在L.r[0]
    		for(j=i-dk;j>0&&LT(L.r[0].key,L.r[j].key);j-=dk)
    		{ 
    			L.r[j+dk]=L.r[j]; //记录后移查找插入位置
    		}
    		L.r[j+dk]=L.r[0];//插入
    		}
    }
    
    void ShellSort(SqList &L, int dlta[],int t)
    { 
    	//按增量序列dlta[0...t-1]对顺序表L做希尔排序
    	for(k=0;k<t;++k)
    	{ 
    		ShellInsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序
    	}
    }

**(三) 气泡排序(bubble sort)**  
依次比较两个相邻的元素，把大的换到后面，一次循环完成后的结果是，最大的数字排在最后。重复以上步骤（除了最后一个），直到排完。

*  平均时间复杂度：O（n^2）
 *  最优时间复杂度：O（n）

void bubble_sort(vector<int>&nums)
    { 
    	int len=nums.size();
    	for(int i=0;i<len;i++)
    	{ 
    		for(int j=0;j<len-i-1;j++)
    		{ 
    			if(nums[j]>nums[j+1])swap(nums[j],nums[j+1]);
    		}
    	}
    }

**(四) 简单选择排序**

*  简单选择排序（不稳定）  
    选择序列中数最小的，把她插到第一个位置，依次类推。
 *  n个数需要进行比较的次数是n(n-1)/2
 *  时间复杂度为O（n^2）
 *  进行移动操作的时间复杂度为O（n）

void select_sort(vector<int>&nums)
    { 
    	int len=nums.size();
    	for(int i=0;i<len;i++)
    	{ 
    		int temp=i;
    		for(int j=i;j<len;j++)
    		{ 
    		if(nums[temp]>nums[j])temp=j;
    		}
    		swap(nums[i],nums[temp]);
    	}
    }

**(五) 快速排序**  
对起泡排序的一种改进。任意取一个记录作为枢纽，将所有大于枢纽的记录放到其之后，将所有小于枢纽的记录放到其之前。

int Partition(SqList &L, int low,int high)
    { 
    	L.r[0]=L.r[low];//用子表的第一个记录做枢纽
    	pivotkey=L.r[low].key; //p做枢纽 记录关键字
    	while(low<high)//从表的两端交替地向中间扫描
    	{ 
    		while(low<high && L.r[high].key>=pivotkey)--high;
    		L.r[low]=L.r[high];//将比枢纽记录小的移到低端
    		while(low<high && L.r[low].key<=pivotkey)++low;
    		L.r[high]=L.r[low];
    	}
    	L.r[low]=L.r[0]; //枢纽记录到位
    	return low; //返回枢纽位置
    }

//递归快排

void QSort (SqList &L,int low, int high)
    { 
    	if(low<high)
    	{ 
    		pivotloc=partition(L,low,high);	//将L.r[low..high]一分为二
    		QSort(L,low,pivotloc-1);//对低子表递归排序，p是枢纽位置
    		QSort(L,pivotloc+1,high);//对高子表递归排序
    	}
    }

**(六) 堆排序**

**(七) 二路归并排序(merge sort)**

void Merge(RcdType SR[], RcdType & TR[], int i,int m ,iny n)
    { 
    	//将有序的SR【i...m】和SR[m+1..n]归并为有序的TR【i...n】
    	for(j=m+1,k=i;i<=m && j<=n;++k)
    	{ //将SR中记录由小到大地并入TR
    		if(LQ(SR[i].key,SR[j].key))TR[k]=SR[i++];
    		else TR[K]=SR[j++];
    	}
    	if(i<=m) TR[k..n]=SR[i..m];//将剩余SR[i..m]复制到TR
    	if(j<=n)TR[k..n]=SR[j..n];	
    }
    
    void MSort(RcdType SR[],RcdType &TR1[],int s,int t)
    { 
    	//将SR[s..t]归并为TR1【s..t】
    	if(s==t) TR1[s]=SR[s];
    	else{ 
    		m=(s+t)/2;//将SR[s..t]平分
    		MSort(SR,TR2,s,m);//递归地将SR【s..m】归并为有序的TR2【s..m】
    		MSort(SR,TR2,m+1,t);
    		Merge(TR2,TR1,s,m,t);//归并
    		}
    }
    
    void MergeSort (SqList &L)
    { 
    	MSort(L.r,L.r,l,L.length);
    }

**(八) 基数排序**  
有多个排序的关键字，先按优先级高的关键字排序，再按次一级的关键字排序，直至排完。  
**(九) 树形选择排序/锦标赛排序**  
对n个记录的关键字进行两两比较，再在其中n/2个较小者之间再进行两两比较，重复直至选出最小的关键字为止。  
**（十）计数排序**  
新开辟空间，记录每个数字出现的次数，然后将数字按数量一次填充出来。  
**（十一）桶排序**  
将记录分布到不同的桶里面，然后再将每个桶分别排序（可以用其他排序算法排）。

> 基数排序 vs 计数排序 vs 桶排序
> 
> 这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
> 
> 基数排序： 根据键值的每位数字来分配桶  
> 计数排序： 每个桶只存储单一键值  
> 桶排序： 每个桶存储一定范围的数值

**（十二）各种内部排序算法的比较**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2_size_16_color_FFFFFF_t_70 1]  
**(十三) 内部排序算法的应用**

[https_blog.csdn.net_weixin_41190227_article_details_86600821]: https://blog.csdn.net/weixin_41190227/article/details/86600821
[https_blog.csdn.net_qq_43145926_article_details_89964296]: https://blog.csdn.net/qq_43145926/article/details/89964296
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2_size_16_color_FFFFFF_t_70]: /images/20211126/5231f11c4d2e4e7b917e68127de2a528.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2_size_16_color_FFFFFF_t_70 1]: /images/20211126/780eafee21174df199bb0df0c6affed4.png