七种常用算法的c++ 实现

朱雀 2022-08-27 10:49 76阅读 0赞

七种常用算法的助记口诀是：冒（冒泡）择（选择）路（直接插入）兮（希尔）快（快速）归（归并）堆（堆排序）

简称MZLXKGD

#ifndef SORT_H
    #define SORT_H
    
    template <typename T>
    void MSort(T* a,int n)
    {
    	T temp;
    	for(int i=0;i<n-1;i++)
    	{
    		for(int j=0;j<n-1-i;j++)
    		{
    			if(a[j]>a[j+1])
    			{
    				temp = a[j+1];
    				a[j+1] = a[j];
    				a[j] = temp;
    			}
    		}
    	}
    }
    
    template <typename T>
    void ZSort(T* a,int n)
    {
    	T temp;
    	int Loc;
    	int j;
    	for(int i=0;i<n-1;i++)
    	{
    		temp =a[0];
    		Loc = 0;
    		for(j=0;j<n-i;j++)
    		{
    			if(a[j]>temp)
    			{
    				Loc = j;
    				temp = a[j];
    			}
    		}
    		temp = a[Loc];
    		a[Loc] = a[j-1];
    		a[j-1]=temp;
    	}
    }
    
    template <typename T>
    void LSort(T* a,int n)
    {
    	T temp;
    
    	for(int i=1;i<n;i++)
    	{
    		for(int j=0;j<i-1;j++)
    		{
    			if(a[i]>=a[j])
    			{
    				continue;
    			}
    			else
    			{
    				temp = a[i];
    				for(int k=i;k!=j;k--)
    				{
    					a[k]=a[k-1];
    				}
    				a[j] = temp;
    				break;
    			}
    		}
    	}
    }
    
    template <typename T>
    void XSort(T* a,int n)
    {
    	T temp;
    	int Increment = n;
    	int loc;
    	while((Increment=Increment/2)!=0)
    	{
    		for(int i=0;i<n/Increment;i++)
    		{
    			for(int j= i;j<n;j+=Increment)
    			{
    				loc = j+Increment;
    				if(loc>=n)break;
    				if(a[j]>a[loc])
    				{
    					temp = a[j];
    					a[j] = a[loc];
    					a[loc] = temp;
    				}
    			}
    		}
    	}
    }
    
    template <typename T>
    void KSort(T* a,int first,int last)
    {
    	if(first>=last)return;
    	int firstLoc = first;
    	int lastLoc = last;
    	int Key = a[first];
    	while(first<last)
    	{
    		while(first<last&&a[last]>=Key)last--;
    		a[first]=a[last];
    		while(first<last&&a[first]<Key)first++;
    		a[last] =a[first]; 
    	}
    	a[first] = Key;
    	KSort(a,firstLoc,first-1);
    	KSort(a,last+1,lastLoc);
    	
    }
    
    template <typename T>
    void GSort(T* a,int first,int last)
    {
    	T temp;
    	if(first>=last)return;
    	int mid = (first+last)/2;
    	GSort(a,first,mid);
    	GSort(a,mid+1,last);
    	for(int j=mid+1;j<=last;j++)
    	{
    		for(int i=first;i<=mid;i++)
    		{
    			if(a[j]>a[i]){}
    			else
    			{
    				temp = a[j];
    				for(int k=mid+1;k!=i;k--)
    				{
    					a[k]=a[k-1];
    				}
    				a[i]=temp;
    			}
    		}
    	}
    
    }
    
    template <typename T>
    void DSort(T* a,int len)
    {
    	T temp;
    	int left;
    	int right;
    	int large;
    	int temploc;
    	//建堆
    	int head = len/2-1;
    	for(int i=head;i>=0;i--)
    	{
    		left = 2*i;
    		right = 2*i+1;
    		large = i;
    		temploc = i;
    		while(left<len ||right<len)
    		{
    			if(left<len&&(a[left]>a[large]))
    			{
    				large = left;
    			}
    			if(right<len&&(a[right]>a[large]))
    			{
    				large = right;
    			}
    			if(large ==temploc){break;}
    			else
    			{
    				temp = a[temploc];
    				a[temploc] =a[large];
    				a[large]=temp;
    				temploc = large;
    				left = 2*temploc;
    				right = temploc*2+1;
    			}
    		}
    	}
    <span style="white-space:pre">	</span>//取元素
    	for(int i=len-1;i!=0;i--)
    	{
    		temp = a[i];
    		a[i]=a[0];
    		a[0]=temp;
    
    		left = 0;
    		right = 1;
    		large = 0;
    		temploc = 0;
    		while(left<i ||right<i)
    		{
    			if(left<i&&(a[left]>a[large]))
    			{
    				large = left;
    			}
    			if(right<i&&(a[right]>a[large]))
    			{
    				large = right;
    			}
    			if(large ==temploc){break;}
    			else
    			{
    				temp = a[temploc];
    				a[temploc] =a[large];
    				a[large]=temp;
    
    				temploc = large;
    				left = 2*temploc;
    				right = temploc*2+1;
    			}
    		}
    	}
    
    }
    #endif

#include<iostream>
    #include"Sort.h"
    using namespace std;
    int main()
    {
    	int a[10] = {6,3,2,7,11,23,4,56,73,12};
    	int n=10;
    
    	//MSort(a,10);
    	//ZSort(a,10);
    	//LSort(a,10);
    	//XSort(a,10);
    	//KSort(a,0,10);
    	//GSort(a,0,9);
    	DSort(a,10);
    
    	for(int i=0;i<n;i++)
    	cout<<a[i]<<"  ";
    	cout<<endl;
    	return 0;
    }