算法导论

港控/mmm° 2023-10-08 09:53 47阅读 0赞

## 算法导论 ##

说明：文章里面所有下标都从0开始，这里跟算法导论不同，算法导论从1开始

##### 插入排序 #####

1.从序列 A n A\_n An中取出一元素 A j A\_j Aj， j ∈ \_j\\in j∈\[1,n\]，让 A j A\_j Aj与 \[ A 0 , A j − 1 \] \[A\_0,A\_\{j-1\}\] \[A0,Aj−1\]区间的所有元素做比较  
2.把满足条件的 A x A\_x Ax（ A x ∈ A\_x\\in Ax∈ \[ A 0 , A j − 1 \] \[A\_0,A\_\{j-1\}\] \[A0,Aj−1\])向右移动  
3.当条件不满足后，说明 A j A\_j Aj找到了合适的位置，然后把 A j A\_j Aj放到该位置上

int a[12]={
        2,1,2,3,4,7,5,9,22,33,123,456};
       for(int j=1;j<12;++j)
       {
        
       		int key=a[j];
    	   int i=j-1;
    	   while(i>=0&&a[i]>key)
    	   {
        
    	   		a[i+1]=a[i];
    		   --i;
    	   }
    	   
    	   a[i+1]=key;
       }

#### 归并排序 ####

1.将序列 A n A\_n An分为两个序列 L m L\_m Lm、 R n R\_n Rn  
2. 比较 L m L\_m Lm、 R n R\_n Rn，复合条件的元素送入 A n A\_n An中  
3. 把 L m L\_m Lm、 R n R\_n Rn剩余的元素追加到 A n A\_n An中  
以上为合并  
4.将序列拆成2组进行然后进行合并

#include <iostream>
    #include <vector>
    using namespace std;
    
    void Merge(std::vector<int>& sequence,int L,int M,int R)
    {
        
    	int s=L;
    	int s2=M+1;
    	std::vector<int> LArr;
    	for(int i=s;i<=M;++i)
    		LArr.push_back(sequence[i]);
    	std::vector<int> RArr;
    	for(int i=s2;i<=R;++i)
    		RArr.push_back(sequence[i]);
    	
    	int i=0;
    	int j=0;
    	int k=L;
    	while(i<LArr.size()&&j<RArr.size())
    		sequence[k++]=LArr[i]>RArr[j]?RArr[j++]:LArr[i++];
    	
    	while(i<LArr.size())
    		sequence[k++]=LArr[i++];
    	while(j<RArr.size())
    		sequence[k++]=RArr[j++];
    }
    
    void MergeSort(std::vector<int>& sequence,int L,int R)
    {
        
    	if(L<R)
    	{
        
    		int mid=(L+R)/2;
    		MergeSort(sequence,L,mid);
    		MergeSort(sequence,mid+1,R);
    		Merge(sequence,L,mid,R);
    	}
    }
    
    int main()
    {
        
       std::vector<int> A{
        2,1,2,3,4,7,5,9,22,33,123,456};
       MergeSort(A,0,A.size()-1);
       for(int i=0;i<A.size();++i)
       {
        
    		cout<<A[i]<<' ';
       } 
       return 0;
    }

#### 选择排序 ####

1.从数组A里找出一个最小的元素；  
2.从数组A移除这个元素，将最小的元素追加到数组B；

void SelectSort(std::list<int>& seq,std::vector<int>& res)
    {
        
    	auto selectMin = [&seq]()->int{
        
    		auto iter = seq.begin();
    		decltype(iter) minIter=iter;
    		int min = *iter;
    		for (;iter!=seq.end();++iter)
    		{
        
    			if (*iter < min)
    			{
        
    				min = *iter;
    				minIter = iter;
    			}
    		}
    		seq.erase(minIter);
    		return  min;
    	};
    
    	for (;!seq.empty();)
    	{
        
    		int min = selectMin();
    		res.emplace_back(min);
    	}
    }

#### 冒泡排序 ####

跟选择排序差不多  
1.找出最大的元素；  
2.交换最大的元素与数组最后面的元素，交换完成的元素及以后的元素都不用再比较（就需要减去i），减1是为了防止j+1访问越界；  
3.重复上面两步；

void BubblingSort(std::vector<int>& seq)
    {
        
    	for(int i=0;i<seq.size();++i)
    	{
        
    		for(int j=0;j<seq.size()-i-1;++j)
    		{
        
    			if(seq[j]>seq[j+1])
    			{
        
    				std::swap(seq[j],seq[j+1]);
    			}
    		}
    	}
    }

#### 快速排序 ####

1.选择数组第一个元素为基值(k)（用于做比较）；  
2.从起始（i）向后找比基值大的元素，找到就放后面；  
3.从结尾(j)向前找比基值小的数，找到就放前面；  
4.在i==j的时候，把基值K放数组中间；  
5.从i处断开分两份递归执行；

void QuickSort(std::vector<int>& seq,int minIndex,int maxIndex)
    {
        
    	if(minIndex>=maxIndex)
    		return;
    		
    	int i=minIndex;
    	int j=maxIndex;
    	int key=seq[i];
    	while(i<j)
    	{
        
    		while(seq[i]<=key&&i<j)
    			i++;
    		seq[j]=seq[i];
    		
    		while(seq[j]>=key&&i<j)
    			j--;
    		seq[i]=seq[j];
    	}
    	seq[i]=key;
    	
    	QuickSort(seq,minIndex,i-1);
    	QuickSort(seq,i+1,maxIndex);
    }