排序算法的一些应用

╰+哭是因爲堅強的太久メ 2021-11-16 07:26 348阅读 0赞

![1300168-20190720191019731-129347418.png][]

思路：

![1300168-20190720191034332-1984462772.png][]

#include<iostream>
    #include<vector>
    using namespace std;
    class ThreeColor {
    public:
        vector<int> sortThreeColor(vector<int> &A, int n)
        {
            int f,r,i,temp;
            //遍历之前数组的左设置一个为空的0区，数组右侧设置一个为空的2区
            for(i=f=0,r=n-1;i<=r;i++)//f指向0区的下一位置，r指向2区的下一位置
            {
                if(A[i]==0)//当前值是0，把当前值和0区的下一个位置的元素进行交换，0区向后扩一个位置
                {
                    temp=A[f];
                    A[f]=A[i];
                    A[i]=temp;
                    f++;
                    //因为是从前向后遍历，所以从前面换来的数字已经遍历过，无需从新遍历
                }
                if(A[i]==2)//当前值是2，把当前值和2区的前一个位置的元素进行交换，2区向前扩一个位置
                {
                    temp=A[r];
                    A[r]=A[i];
                    A[i]=temp;
                    r--;
                    i--;//从后面换来的数字还没有遍历过，需从新遍历
                }
            }
            return A;
        }
    };
    int main()
    {
        int a[6]={
        1,2,0,2};
        vector<int> b(a,a+4);
        ThreeColor c;
        c.sortThreeColor(b,4);
        for(int i=0;i<4;i++)
            cout<<b[i]<<" ";
        cout<<endl;
        return 0;
    }

![1300168-20190720192621854-490197706.jpg][]

#include<iostream>
    #include<vector>
    using namespace std;
    class ScaleSort
    {
    public:
        vector<int> sortElement(vector<int> &A, int n, int k)
        {
            vector<int> B(n,0);
            int i,j;
            //从0——n-1排序
            for(i=k/2-1;i>=0;--i)//(i-1)/2：根
                HeapAdjust(A,i,k-1);
    
            B[0]=A[0];
            for(i=1,j=k;j<n;j++)
            {
                A[0]=A[j];
                HeapAdjust(A,0,k-1);
                B[i++]=A[0];
            }
            heapSort(A,k);
            for(i=0,j=n-1;i<k;j--,i++)
                A[j]=A[i];
            for(i=0;i<n-k;i++)
                A[i]=B[i];
            return A;
        }
        //堆排序
        void heapSort(vector<int> &A, int n)
        {
            int i,temp;
            for(i=n/2-1;i>=0;--i)
                HeapAdjust(A,i,n-1);
    
            for(i=n-1;i>0;i--)
            {
                temp=A[0];
                A[0]=A[i];
                A[i]=temp;
                HeapAdjust(A,0,i-1);
            }
        }
        //已知A[s,...,m]中记录的关键字除A[s]之外均满足堆的定义，本函数调整A[s]
        //的关键字，使A[s,...,m]成为一个小顶堆(对其中记录的关键字而言)
        void HeapAdjust(vector<int> &A,int s,int m)
        {
            int j,rc=A[s];
            for(j=2*s+1;j<=m;j=2*j+1)//2*i+1:左孩子，2*i+2：右孩子
            {
                if(j<m&&A[j]>A[j+1])
                    j++;
                if(rc<A[j])
                    break;
                A[s]=A[j];
                s=j;
            }
            A[s]=rc;
        }
    };
    
    int main()
    {
        int b[]={
        2,1,4,3,6,5,8,7,10,9};
        vector<int> arr(b,b+10);
        ScaleSort a;
        a.sortElement(arr,10,2);
        for(int i=0;i<10;i++)
            cout<<arr[i]<<" ";
        cout<<endl;
        return 0;
    }

![1300168-20190720214013886-830108737.png][]

#include<iostream>
    #include<vector>
    using namespace std;
    class Finder 
    {
    public:
        bool findX(vector<vector<int> > mat, int n, int m, int x) 
        {
            int hang=0,lie=m-1;
            while(hang<n&&lie>=0)
            {
                if(mat[hang][lie]==x)
                    return true;
                if(mat[hang][lie]>x)
                    lie--;
                if(mat[hang][lie]<x)
                    hang++;
            }
            return false;
        }
    };
    int main()
    {
        int a[3][3]={
        {
        1,2,3},{
        4,5,6},{
        7,8,9}};
        vector<vector<int>> b(3,vector<int>(3));//二维数组初始化
        for(int i=0;i<3;i++)
            copy(a[i][0],a[i][2],b[i]);
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
                cout<<b[i][j];
            cout<<endl;
        }
        Finder c;
        bool d=c.findX(b,3,3,10);
        cout<<d;
        return 0;
    }

![1300168-20190720214131598-192132570.png][]

#include<iostream>
    #include<vector>
    using namespace std;
    class Merge
    {
    public:
        int* mergeAB(int* A, int* B, int n, int m)
        {
            int i,j,NewLength=m+n;
            for(i=n-1,j=m-1;i>=0&&j>=0;NewLength--)
            {
                if(B[j]<=A[i])
                    A[NewLength-1]=A[i--];
                else
                    A[NewLength-1]=B[j--];
            }
            while(j>=0)
            {
                A[NewLength-1]=B[j--];
                NewLength--;
            }
            return A;
        }
    };
    int main()
    {
        int a[10]={
        1,3,7,8};
        int b[]={
        0,2,5,9};
        Merge c;
        c.mergeAB(a,b,4,4);
        for(int i=0;i<8;i++)
            cout<<a[i]<<" ";
        cout<<endl;
        return 0;
    }

![1300168-20190720214356377-1235368864.png][]

#include<iostream>
    #include<vector>
    using namespace std;
    class Checker
    {
    public:
        bool checkDuplicate(vector<int> &a, int n)
        {
            heapSort(a,n);
            int i;
            for(i=0;i<n-1;i++)
                if(a[i]==a[i+1])
                    return true;
            return false;
        }
        void heapSort(vector<int> &A, int n)
        //堆排序
        {
            int i,temp;
            for(i=n/2-1;i>=0;--i)
                HeapAdjust(A,i,n-1);
            for(i=n-1;i>0;i--)
            {
                temp=A[0];
                A[0]=A[i];
                A[i]=temp;
                HeapAdjust(A,0,i-1);
            }
        }
        void HeapAdjust(vector<int> &A,int s,int m)
        //已知A[s,...,m]中记录的关键字除A[s]之外均满足堆的定义，本函数调整A[s]
        //的关键字，使A[s,...,m]成为一个大顶堆(对其中记录的关键字而言)
        {
            int j,rc=A[s];
            for(j=2*s+1;j<=m;j=2*j+1)
            {
                if(j<m&&A[j]<A[j+1])
                    j++;
                if(rc>A[j])
                    break;
                A[s]=A[j];
                s=j;
            }
            A[s]=rc;
        }
    };
    
    int main()
    {
        int b[]={
        1,2,3,4,5,5,6};
        vector<int> arr(b,b+7);
        Checker a;
        bool c=a.checkDuplicate(arr,7);
        cout<<c;
        return 0;
    }

![1300168-20190720214521092-1619081882.png][]

![1300168-20190720223459910-749264070.png][]![1300168-20190720223511216-525971309.png][]

![1300168-20190720223521908-1513640153.png][]

#include<iostream>
    #include<vector>
    using namespace std;
    class Subsequence
    {
    public:
        int shortestSubsequence(vector<int> A, int n)
        {
            int max=A[0],min=A[n-1],i,rd1,rd2;
            for(i=1,rd1=0;i<n;i++)//从左向右遍历，遍历过的最大值大于当前数的情况，记录当前最右的情况
            {
                if(A[i]>=max)
                    max=A[i];
                else
                    rd1=i;
            }
            for(i=n-2,rd2=n-1;i>=0;i--)//从右向左遍历，记录遍历过的最小值，记录最小值比当前数小的情况，记录最左的情况
            {
                if(A[i]<=min)
                    min=A[i];
                else
                    rd2=i;
            }
            if(!rd1)
                return 0;
            else
                return rd1-rd2+1;
        }
    };
    int main()
    {
        int a[6]={
        1,4,6,5,9,10};
        vector<int> b(a,a+6);
        Subsequence c;
        int d=c.shortestSubsequence(b,6);
        cout<<d<<endl;
        return 0;
    }

![1300168-20190720215040445-2101275245.png][]

思想：

来自于桶排序的思想，首先遍历数组，找到最小值和最大值，然后把数组等量分成n个区间（n为元素的个数）每个区间对应一个桶，每个数根据对应的区间选择进入相应的桶，把最大值放入n+1号桶，同一桶中的相邻数的差值不会大于桶区间，空桶两侧的相邻数的差值会大于桶区间，所以不用考虑同一桶中的差值，只需考虑来自两个桶的相邻数的差值，也就是前一个桶的最大值和后一个桶的最小值，也就是每个桶的最小值和上一个非空桶的最大值之间的差值，记录其中的最大差值。

![1300168-20190720220008964-1411593424.png][]

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    class Gap
    {
    public:
        int maxGap(vector<int> A, int n)
        {
            vector<vector<int>> B(n+1);
            int max,min,i,j,maxGap;
            //找到最小值和最大值
            for(i=1,max=min=A[0];i<n;i++)
            {
                if(A[i]>max)
                    max=A[i];
                if(A[i]<min)
                    min=A[i];
            }
    
            float gap=1.0*(max-min)/n;
            for(i=0;i<n;i++)
            {
                j=(int)((A[i]-min)/gap);
                if(B[j].empty())
                {
                    B[j].push_back(A[i]);
                    B[j].push_back(A[i]);
                }
                else
                {
                    if(B[j][0]>A[i])
                        B[j][0]=A[i];
                    if(B[j][1]<A[i])
                        B[j][1]=A[i];
                }
            }
            for(i=j=0,maxGap=0;i<n;i=j)
            {
                while(B[i].empty())
                    i++;
                max=B[i][1];
                j=i+1;
                if(j<n+1)
                {
                    while(B[j].empty())
                        j++;
                    if(j>=n+1)
                        break;
                    min=B[j][0];
                    if(min-max>maxGap)
                        maxGap=min-max;
                }
            }
            return maxGap;
        }
    };
    int main()
    {
        int a[5]={
        1,2,5,4,6};
        vector<int> arr(a,a+5);
        Gap b;
        int c=b.maxGap(arr,5);
        cout<<c<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/tianzeng/p/11218875.html

[1300168-20190720191019731-129347418.png]: /images/20211116/db82f772e6d9431c8f042bfd09928b72.png
[1300168-20190720191034332-1984462772.png]: /images/20211116/e8db812e7d70442695efa43c1f9970ca.png
[1300168-20190720192621854-490197706.jpg]: /images/20211116/1ef03ecfbe924342a5d94594be7d43c5.png
[1300168-20190720214013886-830108737.png]: https://img2018.cnblogs.com/blog/1300168/201907/1300168-20190720214013886-830108737.png
[1300168-20190720214131598-192132570.png]: https://img2018.cnblogs.com/blog/1300168/201907/1300168-20190720214131598-192132570.png
[1300168-20190720214356377-1235368864.png]: https://img2018.cnblogs.com/blog/1300168/201907/1300168-20190720214356377-1235368864.png
[1300168-20190720214521092-1619081882.png]: https://img2018.cnblogs.com/blog/1300168/201907/1300168-20190720214521092-1619081882.png
[1300168-20190720223459910-749264070.png]: https://img2018.cnblogs.com/blog/1300168/201907/1300168-20190720223459910-749264070.png
[1300168-20190720223511216-525971309.png]: https://img2018.cnblogs.com/blog/1300168/201907/1300168-20190720223511216-525971309.png
[1300168-20190720223521908-1513640153.png]: https://img2018.cnblogs.com/blog/1300168/201907/1300168-20190720223521908-1513640153.png
[1300168-20190720215040445-2101275245.png]: https://img2018.cnblogs.com/blog/1300168/201907/1300168-20190720215040445-2101275245.png
[1300168-20190720220008964-1411593424.png]: https://img2018.cnblogs.com/blog/1300168/201907/1300168-20190720220008964-1411593424.png