【算法学习笔记】-排序算法

﹏ヽ暗。殇╰゛Y 2022-08-04 11:51 148阅读 0赞

排序算法常见的有：直接插入排序，归并排序，堆排序，快速排序和冒泡排序等。它们的性能如下表所示：

![Center][]

注：排序算法的稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。  
比较重要的三种排序方法：快速排序、归并排序和堆排序。  
1.快速排序  
快速排序的原理：选择数组的第一个数作为主元，把所有比它小的数移到它的左边，所有比它大的数移到它的右边。以此递归该操作，直到整个数组有序。快速排序的代码如下：

#include<iostream>
    using namespace std;
    
    int part(int p,int q,int num[])
    {
    	int temp;
    	int i=p;
    	for(int j=p+1;j<=q;j++)
    	{
    		if(num[j]<num[p])
    		{
    			i++;
    			temp=num[i];
    			num[i]=num[j];
    			num[j]=temp;
    		}
    	}
    	temp=num[p];
    	num[p]=num[i];
    	num[i]=temp;
    	return i;
    }
    void quicksort(int p,int q,int num[])
    {
    	if(p<q)
    	{
    		int r=part(p,q,num);
    		quicksort(p,r-1,num);
    		quicksort(r+1,q,num);
    	}
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int num[8]={2,8,7,1,3,5,6,4};
    	cout<<"排序前的输出顺序为："<<endl;
    	for(int i=0;i<8;i++)
    	{
    		cout<<num[i]<<"\t";
    	}
    	quicksort(0,7,num);
    	cout<<endl<<"排序后的输出顺序为:"<<endl;
    	for(int i=0;i<8;i++)
    	{
    		cout<<num[i]<<"\t";
    	}
    	return 0;
    }

输出结果为：  
排序前的输出顺序为：  
2 8 7 1 3 5 6 4  
排序后的输出顺序为:  
1 2 3 4 5 6 7 8  
  
2.归并排序  
归并排序算法是一个递归算法，基本思想是：将数组划分为两半，对每一半递归地进行归并排序，当两个子列表都已排序完毕，将它们合并为一个有序列表。归并排序的代码如下：

#include <iostream>
    using namespace std;
    
    void mergearray(int a[],int temp[],int first,int middle,int last)
    {
    	int i=first,j=middle+1,k=0;
    	while(i<=middle && j<=last)
    	{
    		if(a[i]<a[j])
    		{
    			temp[k++]=a[i++];
    		}
    		else
    		{
    			temp[k++]=a[j++];
    		}
    	}
    	while(i<=middle)
    	{
    		temp[k++]=a[i++];
    	}
    	while(j<=last)
    	{
    		temp[k++]=a[j++];
    	}
    	for(i=0;i<k;i++)
    	{
    		a[first+i]=temp[i];
    	}
    }
    void mergesort(int a[],int temp[],int first,int last)
    {
    	if(first<last)
    	{
    		int middle=(first+last)/2;
    		mergesort(a,temp,first,middle);
    		mergesort(a,temp,middle+1,last);
    		mergearray(a,temp,first,middle,last);
    	}
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int num[8]={2,8,7,1,3,5,6,4};
    	cout<<"排序前的输出顺序为："<<endl;
    	for(int i=0;i<8;i++)
    	{
    		cout<<num[i]<<"\t";
    	}
    	int *p = new int[8];
    	mergesort(num,p,0,7);
    	cout<<endl<<"排序后的输出顺序为:"<<endl;
    	for(int i=0;i<8;i++)
    	{
    		cout<<num[i]<<"\t";
    	}
    	return 0;
    }

输出结果为：  
排序前的输出顺序为：  
2 8 7 1 3 5 6 4  
排序后的输出顺序为:  
1 2 3 4 5 6 7 8  
3.堆排序  
堆排序的过程是先建立一个大根堆，大根堆的要求是每个节点的值都不大于其父节点的值。然后把根节点与最后一个叶子节点互换，再重新建立最大堆。递归执行，直到遍历完整个数组。堆排序的代码如下：

#include <iostream>
    using namespace std;
    void adjustHeap(int a[],int size,int index)
    {
    	int left = index*2+1;		//左子节点在数组中的位置
    	int right = index*2+2;		//右子节点在数组中的位置
    	int largest = index;
    	int temp;
    	while(left<size || right<size)		//循环遍历，直到没有子节点为止
    	{
    		if(left<size && a[left]>a[largest])
    		{
    			largest = left;
    		}
    		if(right<size && a[right]>a[largest])
    		{
    			largest = right;
    		}							//找到左右子节点和根节点的最大值
    		if(index!=largest)			//如果根节点不是最大值
    		{
    			temp=a[largest];
    			a[largest]=a[index];
    			a[index]=temp;			//交换子节点和根节点
    			index=largest;			//继续向下遍历，调整堆
    			left=index*2+1;
    			right=index*2+1;
    		}
    		else
    		{
    			break;
    		}
    	}
    }
    void buildHeap(int a[],int size)
    {
    	int begin=size/2-1;		//从该结点往后的值都没有子节点
    	for(int i=begin;i>=0;i--)		//建立最大堆
    	{
    		adjustHeap(a,size,i);
    	}
    }
    void heapSort(int a[],int len)
    {
    	int size=len;
    	int temp;
    	buildHeap(a,size);
    	while(size>1)
    	{
    		temp=a[0];
    		a[0]=a[size-1];
    		a[size-1]=temp;
    		size--;
    		adjustHeap(a,size,0);
    	}
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int num[8]={2,8,7,1,3,5,6,4};
    	cout<<"排序前的输出顺序为："<<endl;
    	for(int i=0;i<8;i++)
    	{
    		cout<<num[i]<<"\t";
    	}
    	heapSort(num,8);
    	cout<<endl<<"排序后的输出顺序为:"<<endl;
    	for(int i=0;i<8;i++)
    	{
    		cout<<num[i]<<"\t";
    	}
    	return 0;
    }

输出结果为：  
排序前的输出顺序为：  
2 8 7 1 3 5 6 4  
排序后的输出顺序为:  
1 2 3 4 5 6 7 8

[Center]: /images/20220731/24929936e8f74a569dbb80cef61d314d.png