首页 > 试题广场 >

冒泡排序

[编程题]冒泡排序

热度指数：1884 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

牛牛学习了冒泡排序,并写下以下冒泡排序的伪代码,注意牛牛排序的数组a是从下标0开始的。

BubbleSort(a):
    Repeat length(a)-1 times:
        For every i from 0 to length(a) - 2:
            If a[i] > a[i+1] then:
                 Swap a[i] and a[i+1]

牛牛现在要使用上述算法对一个数组A排序。
在排序前牛牛允许执行最多k次特定操作(可以不使用完),每次特定操作选择一个连续子数组,然后对其进行翻转,并且k次特定操作选择的子数组不相交。
例如A = {1, 2, 3, 4, 5, 6, 7}, k = 1,如果牛牛选择的子数组是[2,4](注意下标从0开始),那么翻转之后的数组变为A = {1, 2, 5, 4, 3, 6, 7}。
牛牛知道冒泡排序的效率一定程度上取决于Swap操作次数,牛牛想知道对于一个数组A在进行k次特定操作之后,再进行上述冒泡排序最少的Swap操作次数是多少?

输入描述:

输入包括两行,第一行包括两个正整数n和k(2 ≤ n ≤ 50, 1 ≤ k ≤ 50),表示数组的长度和允许最多的特定操作次数。
第二行n个正整数A[i](1 ≤ A[i] ≤ 1000),表示数组内的元素,以空格分割。

输出描述:

输出一个整数,表示在执行最多k次特定操作之后,对数组进行上述冒泡排序需要的Swap操作次数。

示例1

输入

3 2
2 3 1

输出

算法知识视频讲解

wylu

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        int n = Integer.parseInt(strs[0]), k = Integer.parseInt(strs[1]);
        strs = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(strs[i]);
        }

        //dp[i][j]: 表示进行不多于j次操作后与a[i],...,a[len - 1]形成逆序对数的最小值
        int[][] dp = new int[n + 1][k + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= k; j++) {
                dp[i][j] = countReverseOrder(a, i, i) + dp[i + 1][k];
                if (j > 0) {
                    for (int p = i + 1; p < n; p++) {
                        int[] tmp = new int[p + 1];
                        System.arraycopy(a, 0, tmp, 0, p + 1);
                        reverse(tmp, i, p);
                        dp[i][j] = Math.min(dp[i][j], countReverseOrder(tmp, i, tmp.length - 1) + dp[p + 1][j - 1]);
                    }
                }
            }
        }
        System.out.println(dp[0][k]);
    }

    //求元素arr[begin], ... ,arr[end]的逆序数
    private static int countReverseOrder(int[] arr, int begin, int end) {
        int count = 0;
        for (int i = begin; i <= end; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[i]) count++;
            }
        }
        return count;
    }

    private static void reverse(int[] arr, int i, int j) {
        for (; i < j; i++, j--) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
}

发表于 2019-01-30 22:38:50 回复(0)

元气の悟空

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=55;
int getCnt(vector<int> A,int x){
    int n=A.size(),cnt=0;
    for(int i=x;i<n;i++)
        for(int j=0;j<i;j++)
            if(A[j]>A[i]) cnt++;
    return cnt;
}
int n,dp[maxn][maxn],k,K,i,j;
int main(){
    scanf("%d%d",&n,&K);
    vector<int> A(n);
    for(i=0;i<n;i++) scanf("%d",&A[i]);
    for(i=n-1;i>=0;i--)
        for(k=0;k<=K;k++){
            vector<int> tmp1(A.begin(),A.begin()+i+1);
            dp[i][k]=getCnt(tmp1,i)+dp[i+1][k];
            if(k>=1){
                for(j=i+1;j<n;j++){
                    vector<int> tmp2(A.begin(),A.begin()+j+1);
                    reverse(tmp2.begin()+i,tmp2.begin()+j+1);
                    dp[i][k]=min(dp[i][k],getCnt(tmp2,i)+dp[j+1][k-1]);
                }
            }
        }
    printf("%d",dp[0][K]);
}

发表于 2017-11-29 23:37:50 回复(0)

燃烧的橙子

动态规划

dp[i][j]//下标0到n-1，可以换j次，最多可以消除多少逆序数

ni[i][j]//下标i到j逆序数

shun[i][j]//下标i到j顺序数(相等数字不计)

dp[i][j]=max{dp[i+1][j],{ni[i][t]-shun[i][t]+dp[t+1][j-1] | i<t<n}}

答案为总逆序数减最多消去的逆序数

发表于 2017-11-29 14:29:46 回复(2)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int n, K;

int F(vector<int> a, int x){
    int cnt=0;
    for(int i=x;i<a.size();i++)
        for(int j=0;j<i;j++)
            if(a[j]>a[i])
                cnt++;
    return cnt;
}

int main(){
    scanf("%d%d", &n, &K);
    vector<int> a(n);
    int dp[n+1][K+1];
    memset(dp, 0, sizeof(dp));
    for(int i=0;i<n;i++)
        scanf("%d", &a[i]);
    for(int i=n-1;i>=0;i--)
        for(int k=0;k<=K;k++){
            vector<int> b(a.begin(), a.begin()+i+1);
            dp[i][k] = dp[i+1][k] + F(b, i);
            if(k==0)
                continue;
            for(int j=i+1;j<n;j++){
                vector<int> b(a.begin(), a.begin()+j+1);
                reverse(b.begin()+i, b.begin()+j+1);
                dp[i][k] = min(dp[i][k], dp[j+1][k-1]+F(b, i));
            }
        }
    printf("%d\n", dp[0][K]);
    return 0;
}

发表于 2020-10-16 01:25:07 回复(0)

liandexu

没搞懂啊，特定操作那个具体怎么翻转的

发表于 2019-08-13 09:08:16 回复(1)

自闭了201904090952484

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }
        int[][] dp = new int[n + 1][k + 1];// dp[i][j]表示到前i个字符串最多反转j次能减少的最多逆序数
        for (int i = 2; i <= n; i++){
            for (int j = 1; j <= k; j++){
                int tmp = Integer.MIN_VALUE;
                // 计算从a[t - 1]到a[i - 1]进行反转的话，能够减少的逆序数
                for (int t = 1; t < i; t++){
                    tmp = Math.max(tmp, beforeReverse(a, t - 1, i - 1) - afterReverse(a, t - 1, i - 1) + dp[t - 1][j - 1]);
                }
                dp[i][j] = Math.max(dp[i - 1][j], tmp);
            }
        }
        System.out.println(beforeReverse(a, 0, n - 1) - dp[n][k]);
    }
    // 从a[left] 到 a[right]逆序的个数
    private static int beforeReverse(int[] a, int left, int right){
        int sum = 0;
        for (int i = left; i < right; i++){
            for (int j = i + 1; j <= right; j++){
                if (a[i] > a[j]){
                    sum++;
                }
            }
        }
        return sum;
    }
    // 从left到right进行反转，此时left到right的逆序数
    private static int afterReverse(int[] a, int left, int right){
        int sum = 0;
        for (int i = right; i > left; i--){
            for (int j = i - 1; j >= left; j--){
                if (a[i] > a[j]){
                    sum++;
                }
            }
        }
        return sum;
    }
}

发表于 2019-06-13 17:22:03 回复(0)

Java

头脑风暴_

#采用区间动态规划的思想，具体请参考

https://www.cnblogs.com/***allJunJun/p/10885114.html

public clas***ain1 {
    public static void main(String[] args) {
           Scanner sc = new Scanner(System.in);             
           int n=sc.nextInt();             
           int k=sc.nextInt();             
           int[] a=new int[n];             
           for(int i=0;i<n;i++)         
               a[i]=sc.nextInt();   
            int[][]dp =new int[n+1][k+1];//表示前i个数总共旋转j次最多能够减少的逆序数对       
           for(int i=2;i<=n;i++) {         
                 for(int j=1;j<=k;j++) {             
                    int temp=Integer.MIN_VALUE;             
                    for(int t=i-1;t>=1;t--) {               temp=Math.max(countReverseBefore(a,t-1,i-1)-countReverseAfter(a,t-1,i-1)+dp[t-1][j-1], temp);             }             
                    dp[i][j]=Math.max(dp[i-1][j], temp);  
            }    
          }       
           System.out.println(countReverseBefore(a,0,n-1)-dp[n][k]);

     }
   private static int countReverseBefore(int[] arr, int begin, int end) {  
       int count = 0;        
          for (int i = begin; i <= end; i++) {  
          for (int j = i+1; j <= end; j++) {   
             if (arr[j] < arr[i]) 
                         count++;                 
                 }        
          }             
            return count;
   }

   private static int countReverseAfter(int[] arr, int begin, int end) {
        int count = 0;
        for (int i = end; i >= begin; i--) {
            for (int j = i-1; j >=begin; j--) {
                if (arr[j] < arr[i]) count++;
            }
        }
        return count;
   }
}