博客

INSERT_SORT插入排序:

适用于少量元素,

给定序列为长度为n的arr序列,无序

以x为例,在arr序列中找到一个左边小于等于x,右边大于等于x的位置

#include<bits/stdc++.h>
using namespace std;
int arr[100000];
int n;
void insert_sort()//插入排序
{
    for (int i=1;i<n;i++)
    {
        int key=arr[i];
        int j=i-1;
        while(i>0&&arr[j]>key)
        {
            arr[j+1]=arr[j];
            j=j-1;
        }
        arr[j+1]=key;
    }
}
void out()//输出
{
    for(int i=0;i<n;i++)
        cout<<arr[i]<<' ';
}
int main()
{

    cout<<"输入arr序列长度n:";
    cin>>n;
    cout<<"输入arr序列:";
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    insert_sort();
    cout<<"输出insert_sort后arr序列";
    out();
     return 0;
}

算法分析:

时间分析:每一句代码为o(1)的时间,调用语言内的函数,按其底层时间计算,循环为循环层数乘以每个循环中代码个数

空间分析:所调用或申请的空间计算

分治:



将一个大问题分解成若干小问题进行求解,然后再合并得到大问题的解

MERG_SORT归并排序:

归并操作:给定有序序列L1[1…..n],L2[1……m],归并生成L3[1…..m+n]

建立双指针操作

#include<bits/stdc++.h>
using namespace std;
int L1[100000];
int L2[100000];
int L3[100000];
int n,m;
void merge_()
{
    L1[n]=999999999;
    L2[m]=999999999;
    int i=0,j=0;
    for(int k=0;k<m+n;k++)
    {
        if(L1[i]<L2[j])
        {
            L3[k]=L1[i];
            i++;
        }
        else
        {
            L3[k]=L2[j];
            j++;
        }
    }
}
void out()
{
    for(int i=0;i<m+n;i++)
    {
        cout<<L3[i]<<' ';
    }
}
int main()
{
    cout<<"序列L1的长度n:";
    cin>>n;
    cout<<"序列L2的长度m:";
    cin>>m;
    cout<<"输入序列L1:";
for(int i=0;i<n;i++)
cin>>L1[i];
cout<<"输入序列L2:";
for(int i=0;i<m;i++)
    cin>>L2[i];
merge_();
cout<<"输出归并排序后的L3序列:";
out();
}

MERGR

排序操作:将序列进行分治,分解成最小单元的小问题,再进行归并,然后合并得到所要求排序序列

给定长度为n的无序序列arr序列

#include<bits/stdc++.h>
using namespace std;
int arr[1000000];
int n;
int L[100000];//辅助数组
int R[100000];//辅助数组
void merge_(int l,int m,int r)
{
    for(int i=0;i<m-l+1;i++)
        L[i]=arr[l+i];
    for(int i=0;i<r-m;i++)
        R[i]=arr[m+i+1];
    L[m-l+1]=99999999;
    R[r-m]=99999999;
    int i=0,j=0;
    for(int k=l;k<=r;k++)
    {
        if(L[i]<R[j])
            arr[k]=L[i],i++;
        else
            arr[k]=R[j],j++;
    }
}
void merge_sort(int l,int r)
{
    if(l<r)
    {
        int mid=(l+r)/2;
        merge_sort(l,mid);
        merge_sort(mid+1,r);
        merge_(l,mid,r);
    }
}
void out()
{
    for(int i=0;i<n;i++)
        cout<<arr[i]<<' ';
}
int main()
{
    cout<<"输入序列arr的长度n:";
    cin>>n;
    cout<<"输入序列arr:";
    for(int i=0;i<n;i++)
        cin>>arr[i];
    merge_sort(0,n-1);
    cout<<"输出序列arr:";
    out();
}