从0开始学算法--排序（1.1选择排序）

算法理解：给你一个数组，怎么让一个数组最大的数和最后一个数字交换位置。

如：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int maxn=2e5+10;
int a[maxn],n;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    int maxi=0,maxa=a[0];//maxi为最大数的下表，maxa为最大数
    for(int i=1;i<n;i++){
        if(a[i]>maxa){//如果a【i】大于最大数，变更最大数和他的下表
            maxa=a[i];
            maxi=i;
        }
    }
    //交换最大数和尾数
    swap(a[maxi],a[n-1]);
    //输出
    for(int i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    return 0;
}

View Code

如果满足了这样的操作，对长度位n的数组做n-1次操作就可以让数组从小到大排序了，这就是选择排序。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int maxn=2e5+10;
int a[maxn],n;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int j=0;j<n-1;j++){
        //第一次循环找到前n个位置的最大数，放在数组的最后
        //第二次循环找到剩下钱n-1个位置的最大数，以此类推
        //只需要n-1次循环
        int maxi=0,maxa=a[0];//maxi为最大数的下表，maxa为最大数
        for(int i=1;i<n-j;i++){
            if(a[i]>maxa){//如果a【i】大于最大数，变更最大数和他的下表
                maxa=a[i];
                maxi=i;
            }
        }
        //交换最大数和尾数
        swap(a[maxi],a[n-j-1]);
    }
    //输出
    for(int i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    return 0;
}

例题1：

给你一个数组，你可以选任意一个数字放在数组的首位，（不是和首位交换，如1，2，3，4，5操作数字5，数组就会变成5，1，2，3，4）问使数组变为升序的最小操作次数使多少？

/*解：
*首先你一定不会操作最大数，因为这是最坏的情况，操作最大数之后就需要操作所有的数*字，显而易见的如果次大值在最大值的前面，次大值也是不会操作的，此役类推。
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int maxn=2e5+10;
int a[maxn],n;
int b[maxn];
int main(){
    scanf("%d",&n);
    int num=n;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    //选择排序，可以用其他排序方式代替
    for(int j=0;j<n-1;j++){
        int maxi=0,maxa=a[0];
        for(int i=1;i<n-j;i++){
            if(a[i]>maxa){
                maxa=a[i];
                maxi=i;
            }
        }
        swap(a[maxi],a[n-j-1]);
    }
    for(int i=n-1,j=n-1;i>=0;i--){
        if(b[i]==a[j]){
            j--;
            num--;
        }
    }
    //输出
    printf("%d\n",num);
    return 0;
}

View Code

例题2：

给你一个数组，你可以选择任意一个数放在数组的首位或者末尾，问：使数组变为升序的最小操作次数使多少？

这个题类似上一个题，例一其实就是在求原数组和排序数组包含最大值的最长公共子序列，所以可以把数字移到末尾后就是求原数组和排序数组的最长公共子序列，去掉这一部分，剩下的部分就使必须操作的数字，且每个数字只需要操作一次。

从0开始学算法--排序（1.1选择排序）

相关推荐