美文网首页
程序设计导论-3 基本算法实现 代码实现

程序设计导论-3 基本算法实现 代码实现

作者: CraXyG | 来源:发表于2019-11-18 20:01 被阅读0次

    辅助分析的工具

    这一部分设置计数器采用的是程序设计导论2中,二分查找的部分作为例子。

    设置计数器

    C

    #include<stdio.h>
    #include<math.h>
    int cnt;
    int binarysearch(int arr[],int l,int r,int x){
        if (l >= r)
            cnt += 1 ;
            return -1;
        int mid = l+r/2;
        cnt += 1;
        if (arr[mid]==x){
            return mid;
            cnt += 2; 
        }
        else if(arr[mid] >x){
            return binarysearch(arr,l,mid,x);
            cnt += 3;
        }
        else{
            return binarysearch(arr,mid,r,x);
            cnt += 4;
        }
    }
    int main(){
        int n;
        int arr[1000];
        int x;
        scanf("%d",&n);
        for(int i = 0;i<n;i++){
            scanf("%d",&arr[i]);
        }
        scanf("%d",&x);
        printf("%d",binarysearch(arr,0,n,x));
        printf("计数器指示:%d",cnt);
        return 0;
    }
    

    C++

    #include<iostream>
    #include<cmath>
    using namespace std;
    int cnt;
    int binarysearch(int arr[],int l,int r,int x){
        if (l >= r)
            cnt += 1 ;
            return -1;
        int mid = l+r/2;
        cnt += 1;
        if (arr[mid]==x){
            return mid;
            cnt += 2; 
        }
        else if(arr[mid] >x){
            return binarysearch(arr,l,mid,x);
            cnt += 3;
        }
        else{
            return binarysearch(arr,mid,r,x);
            cnt += 4;
        }
    }
    int main(){
        int n;
        int arr[1000];
        int x;
        cin>>n;
        for(int i = 0;i<n;i++){
            cin>>arr[i];
        }
        cin>>x;
        cout<<binarysearch(arr,0,n,x)<<endl;
        cout<<"计数器指示:"<<cnt<<endl;
        return 0;
    }
    

    Java

    import java.util.Scanner;
    class binarysea{
        public static int cnt = 0;
        public static int binarysearch(int arr[],int l,int r,int x){
            if (l >= r){
                cnt+=1;
                return -1;
            }
            int mid = l+r/2;
            cnt+=1;
            if (arr[mid]==x){
                cnt+=2;
                return mid;
            }
            else if(arr[mid] >x){
                cnt+=3;
                return binarysearch(arr,l,mid,x);
            }
            else{
                cnt+=4;
                return binarysearch(arr,mid,r,x);
            }
        }
        public static void main(String args[]){
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();5
            int arr[] = new int[1000];
            for(int i = 0;i<n;i++){
                arr[i]=sc.nextInt();
            }
            int x = sc.nextInt();
            System.out.println(binarysearch(arr,0,n,x));
            System.out.println("计数器指示:"+cnt);
        }
    }
    

    Python

    arr = input().split(" ")
    x = input()
    sorted(arr)
    cnt = 0
    def binarysearch(arr,l,r,x):
        global cnt
        if l >= r:
            cnt += 1 
            return -1
        mid = int((l + r)/2)
        cnt += 1
        if arr[mid] == x:
            cnt += 2 #将判断条件的过程计算进去
            return mid
        elif arr[mid] > x:
            cnt += 3 #将之前判断的过程计算进去
            return binarysearch(arr,l,mid,x)
        else :
            cnt += 4 #将之前判断的过程计算进去
            return binarysearch(arr,mid,r,x)
    print(binarysearch(arr,0,len(arr)-1,x))
    print("计数器指示:{}".format(cnt))
    

    设置定时器

    这一部分设置计数器采用的是程序设计导论2中,e的近似的部分作为例子。

    C

    #include<stdio.h>
    #include<math.h>
    #include<time.h>
    int prod(int n){
        int prd = 1;
        for(int i = 1; i<= n;i++){
            prd = prd * i;
        }
        return prd;
    }
    int main(){
        int n;
        scanf("%d",&n);
        double e = 0;
        int cnt = 0;
        double item = 1;
        clock_t start_t,end_t;
        start_t = clock();
        while(fabs(item)>pow(0.1,n)){
            item = 1.0 / prod(cnt);
            e = e + item;
            cnt = cnt + 1;
        }
        end_t = clock();
        printf("%lf",e);
        printf("程序运行耗时:%f\n", (double)(end - start) / CLOCKS_PER_SEC);
        return 0;
    }
    

    C++

    #include<iostream>
    #include<cmath>
    #include<ctime>
    using namespace std;
    int prod(int n){
        int prd = 1;
        for(int i = 1; i<= n;i++){
            prd = prd * i;
        }
        return prd;
    }
    int main(){
        int n;
        cin>>n;
        double e = 0;
        int cnt = 0;
        double item = 1;
        clock_t start_t,end_t;
        start_t = clock();
        while(fabs(item)>pow(0.1,n)){
            item = 1.0 / prod(cnt);
            e = e + item;
            cnt = cnt + 1;
        }
        end_t = clock();
        cout<<e<<endl;
        cout<<"程序运行耗时:%f\n"<<(double)(end - start) / CLOCKS_PER_SEC)<<endl;
        return 0;
    }
    

    Java

    import java.util.Scanner;
    class eapprox{
        public static int prod(int n){
            int prd = 1;
            for(int i = 1; i<= n;i++){
                prd = prd * i;
            }
            return prd;
        }
        public static void main(String args[]){
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            double e = 0;
            int cnt = 0;
            double item = 1;
            long startTime =  System.nanoTime();
            while(Math.abs(item)>Math.pow(0.1,n)){
                item = 1.0 / prod(cnt);
                e = e + item;
                cnt = cnt + 1;
            }
            long endTime =  System.nanoTime();
            long usedTime = endTime-startTime;
            System.out.println(e);
            System.out.println(usedTime+"ms");
        }
    }
    

    Python

    import time
    n = int(input())
    e = 0
    cnt = 0
    item = 1
    def prod(n):
        prd = 1.0
        for i in range(1,n+1):
            prd = prd * i
        return prd
    start_time = time.process_time()#程序开始
    while abs(item) > pow(0.1,n):
        item = 1.0  /prod(cnt)
        e = e + item
        cnt = cnt +1
    end_time = time.process_time()#程序结束
    print(e)
    print("计数器指示:{}".format(end_time-start_time))
    

    设置进程资源检测

    大数四则运算

    加法

    C

    #include<string.h>
    #include<stdio.h>
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    char a[1000000];
    char b[1000000];
    char c[1000001];
    void add(char a[],char b[]){
        strrev(a);
        strrev(b);
        int tem = 0;
        int cnt = 0;
        int len_a = strlen(a);
        int len_b = strlen(b);
        int item = 0;
        for(int i = 0 ; i < min(len_a,len_b);i++){
            item = a[i]-'0'+b[i]-'0'+tem;
            if (item>10){
                tem = 1;
                item %= 10;
            }
            else{
                tem = 0;
            }
            c[cnt++]=item+'0';
        }
        if(len_a>len_b){
            for(int i = len_b;i<len_a;i++){
                item = a[i]-'0'+tem;
                if(item >= 10){
                    tem = 1;
                    item %= 10;
                }
                else{
                    tem = 0;
                }
                c[cnt++]=item+'0';
            }
        }
        if(len_b>len_a){
            for(int i = len_a;i<len_b;i++){
                item = a[i]-'0'+tem;
                if(item >= 10){
                    tem = 1;
                    item %= 10;
                }
                else{
                    tem = 0;
                }
                c[cnt++]=item+'0';
            }
        }
        if (tem != 0){
            c[cnt++]=tem+'0';
        }
        strrev(c);
    }
    int main(){
        scanf("%s %s",&a,&b);
        add(a,b);
        printf(c);
        return 0;
    }
    

    C++

    #include<algorithm>
    #include<string.h>
    #include<iostream>
    using namespace std;
    char a[1000000];
    char b[1000000];
    char c[1000001];
    void add(char a[],char b[]){
        strrev(a);
        strrev(b);
        int tem = 0;
        int cnt = 0;
        int len_a = strlen(a);
        int len_b = strlen(b);
        int item = 0;
        for(int i = 0 ; i < min(len_a,len_b);i++){
            item = a[i]-'0'+b[i]-'0'+tem;
            if (item>10){
                tem = 1;
                item %= 10;
            }
            else{
                tem = 0;
            }
            c[cnt++]=item+'0';
        }
        if(len_a>len_b){
            for(int i = len_b;i<len_a;i++){
                item = a[i]-'0'+tem;
                if(item >= 10){
                    tem = 1;
                    item %= 10;
                }
                else{
                    tem = 0;
                }
                c[cnt++]=item+'0';
            }
        }
        if(len_b>len_a){
            for(int i = len_a;i<len_b;i++){
                item = a[i]-'0'+tem;
                if(item >= 10){
                    tem = 1;
                    item %= 10;
                }
                else{
                    tem = 0;
                }
                c[cnt++]=item+'0';
            }
        }
        if (tem != 0){
            c[cnt++]=tem+'0';
        }
        strrev(c);
    }
    int main(){
        cin>>a>>b;
        add(a,b);
        cout<<c<<endl;
        return 0;
    }
    

    Java

    Python

    def add(a,b):
        a = a[::-1]
        b = b[::-1]
        c = []
        tem = 0
        for x,y in zip(a,b):
            item = int(x)+int(y)+tem
            if item >= 10:
                tem = 1
                item %= 10
            else:
                tem = 0
            c.append(str(item))
        if len(a) > len(b):
            for i in range(len(b),len(a)):
                item = int(a[i])+tem
                if item >= 10:
                    tem = 1
                    item %= 10
                else:
                    tem = 0
                c.append(str(item))
        if len(a) < len(b):
            for i in range(len(a),len(b)):
                item = int(b[i])+tem
                if item >= 10:
                    tem = 1
                    item %= 10
                else:
                    tem = 0
                c.append(str(item))
        if tem != 0:
            c.append(str(tem))
        c = "".join(c)
        return c[::-1]
    a,b = input().split(" ")
    print(add(a,b))
    

    减法

    C

    #include<string.h>
    #include<stdio.h>
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    char a[1000000];
    char b[1000000];
    char c[1000001];
    void sub(char a[],char b[]){
        strrev(a);
        strrev(b);
        int tem = 0;
        int cnt = 0;
        int len_a = strlen(a);
        int len_b = strlen(b);
        int item = 0;
        for(int i = 0; i < min(len_a,len_b);i++){
            if(a[i]+tem>=b[i]){
                item = a[i]-'0'+tem-(b[i]-'0');
                tem = 0;
            }
            else{
                item = a[i]-'0'+10+tem-(b[i]-'0');
                tem = -1;
            }
            c[cnt++]=item+'0';
        }
        if(len_a>len_b){
            for(int i = len_b;i<len_a;i++){
                item = a[i]-'0'+tem;
                if(item<0){
                    tem = -1;
                    item += 10;
                }
                else{
                    tem = 0;
                }
                c[cnt++] = item+'0';
            }
        }
        strrev(c);
    }
    int main(){
        scanf("%s %s",&a,&b);
        sub(a,b);
        printf(c);
        return 0;
    }
    

    C++

    #include<string.h>
    #include<iostream>
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    using namespace std;
    char a[1000000];
    char b[1000000];
    char c[1000001];
    void sub(char a[],char b[]){
        strrev(a);
        strrev(b);
        int tem = 0;
        int cnt = 0;
        int len_a = strlen(a);
        int len_b = strlen(b);
        int item = 0;
        for(int i = 0; i < min(len_a,len_b);i++){
            if(a[i]+tem>=b[i]){
                item = a[i]-'0'+tem-(b[i]-'0');
                tem = 0;
            }
            else{
                item = a[i]-'0'+10+tem-(b[i]-'0');
                tem = -1;
            }
            c[cnt++]=item+'0';
        }
        if(len_a>len_b){
            for(int i = len_b;i<len_a;i++){
                item = a[i]-'0'+tem;
                if(item<0){
                    tem = -1;
                    item += 10;
                }
                else{
                    tem = 0;
                }
                c[cnt++] = item+'0';
            }
        }
        strrev(c);
    }
    int main(){
        cin>>a>>b;
        sub(a,b);
        cout<<c<<endl;
        return 0;
    }
    

    Java

    Python

    def sub(a,b):
        a = a[::-1]
        b = b[::-1]
        c = []
        tem = 0
        for x,y in zip(a,b):
            if int(x)+tem >= int(y):
                item = int(x)+tem-int(y)
                tem = 0
            else:
                item = int(x)+tem+10-int(y)
                tem = -1
            c.append(str(item))
        if len(a) > len(b):
            for i in range(len(b),len(a)):
                item = int(a[i])+tem
                if item < 0:
                    tem = -1
                    item += 10
                else:
                    tem = 0
                c.append(str(item))
        c = "".join(c)
        return c[::-1]
    a,b = input().split(" ")
    print(sub(a,b))
    

    乘法

    除法

    素数筛

    暴力算法

    C

    #include<stdio.h>
    #include<math.h>
    int a[10000000];
    int violet_sieve_core(int num){
        if (num<=1){
            return 0;
        }
        for(int i = 2;i < num;i++){
            if(num%i == 0){
                return 0;
            }
        }
        return 1;
    }
    int cnt;
    void violet_sieve(int n){
        for(int i = 2;i < n+1;i++){
            if(violet_sieve_core(i)){
                a[cnt++]=i;
            }
        }
    }
    int main(){
        int n;
        scanf("%d",&n);
        violet_sieve(n);
        for(int i = 0 ;i<cnt;i++){
            printf("%d ",a[i]);
        }
        return 0;
    }
    

    C++

    #include<iostream>
    #include<cmath>
    int a[10000000];
    int violet_sieve_core(int num){
        if (num<=1){
            return 0;
        }
        for(int i = 2;i < num;i++){
            if(num%i == 0){
                return 0;
            }
        }
        return 1;
    }
    int cnt;
    void violet_sieve(int n){
        for(int i = 2;i < n+1;i++){
            if(violet_sieve_core(i)){
                a[cnt++]=i;
            }
        }
    }
    int main(){
        int n;
        cin>>n;
        violet_sieve(n);
        for(int i = 0 ;i<cnt;i++){
            cout<<a[i]<<endl;
        }
        return 0;
    }
    

    Java

    Python

    def violet_sieve(num):
        if num < 2:
            return False
        for i in range(2,num):
            if num % i == 0:
                return False
        return True
    n = int(input())
    for i in range(2,n+1):
        if violet_sieve(i):
            print(i)
    

    埃筛

    C

    #include<stdio.h>
    #include<math.h>
    int a[10000000];
    int cnt;
    int p[100000000];
    void eratos_sieve(int n){
        for(int i = 2;i<n;i++){
            for(int j = 2; i *j <= n;j++){
                p[i*j] = 0;
            }
            if(!p[i]){
                a[cnt++]=i;
            }
        }
    }
    int main(){
        int n;
        scanf("%d",&n);
        eratos_sieve(n);
        for(int i = 0 ;i<cnt;i++){
            printf("%d ",a[i]);
        }
        return 0;
    }
    

    C++

    #include<iostream>
    #include<cmath>
    int a[10000000];
    int cnt;
    int p[100000000];
    void eratos_sieve(int n){
        for(int i = 2;i<n;i++){
            for(int j = 2; i *j <= n;j++){
                p[i*j] = 0;
            }
            if(!p[i]){
                a[cnt++]=i;
            }
        }
    }
    int main(){
        int n;
        cin>>n;
        eratos_sieve(n);
        for(int i = 0 ;i<cnt;i++){
            cout<<a[i]<<endl;
        }
        return 0;
    }
    

    Java

    Python

    def eratos_sieve(n):
        primes = [True] * (n+1)
        p = 2
        while p*p <= n:
            if primes[p]:
                for i in range(p*2,n+1,p):
                    primes[i] = False
            p += 1
        primes = [element for element in range(2,n) if primes[element]]
        return primes
    n = int(input())
    for i in eratos_sieve(n):
        print(i)
    

    欧拉筛

    C

    #include<stdio.h>
    #include<math.h>
    int a[10000000];
    int cnt;
    int p[100000000];
    void euler_sieve(int n){
        for(int i = 2;i<n;i++){
            if(!p[i]){
                a[cnt++]=i;
            }
            for(int j = 0; j<cnt &&i *a[j] <= n;j++){
                p[i*a[j]]= 1;
                if(i % a[j] == 0) break;
            }
        }
    }
    int main(){
        int n;
        scanf("%d",&n);
        euler_sieve(n);
        for(int i = 0 ;i<cnt;i++){
            printf("%d ",a[i]);
        }
        return 0;
    }
    

    C++

    #include<iostream>
    #include<cmath>
    using namespace std;
    int a[10000000];
    int cnt;
    int p[100000000];
    void euler_sieve(int n){
        for(int i = 2;i<n;i++){
            if(!p[i]){
                a[cnt++]=i;
            }
            for(int j = 0; j<cnt &&i *a[j] <= n;j++){
                p[i*a[j]]= 1;
                if(i % a[j] == 0) break;
            }
        }
    }
    int main(){
        int n;
        cin>>n;
        euler_sieve(n);
        for(int i = 0 ;i<cnt;i++){
            cin>>a[i]<<endl;
        }
        return 0;
    }
    

    Java

    Python

    def euler_sieve(n):
        cnt = 0
        flag = [True] * (n+1)
        primes = []
        for i in range(2,n):
            if flag[i]:
                primes.append(i)
                cnt += 1
            j = 0
            while j < cnt and i * prime[j] < n:
                flag[i*prime[j]] = False
                if i%prime[j] == 0:
                    break
                j += 1
        return primes
    n = int(input())
    for i in euler_sieve(n):
        print(i)
    

    求最大公约数

    辗转相除法

    C

    #include<stdio.h>
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    int gcd(int a,int b){
        int a_ = max(a,b);
        int b_ = min(a,b);
        return b==0?a:gcd(b,a%b);
    }
    
    int main(){
        int m,n;
        scanf("%d %d",&m,&n);
        printf("%d",gcd(m,n));
        return 0;
    }
    

    C++

    #include<iostream>
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    using namespace std;
    int gcd(int a,int b){
        int a_ = max(a,b);
        int b_ = min(a,b);
        return b==0?a:gcd(b,a%b);
    }
    
    int main(){
        int m,n;
        cin>>m>>n;
        cout<<gcd(m,n)<<endl;
        return 0;
    }
    

    Java

    Python

    def gcd(a,b):
        a,b = max(a,b),min(a,b)
        if b == 0:
            return a
        else:
            return gcd(b,a%b)
    m,n = [int(i) for i in input().split()]
    print(gcd(m,n))
    

    stein算法

    C

    #include<stdio.h>
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    int stein(int m,int n){
        int a = max(m,n);
        int b = min(m,n);
        if(b == 0){
            return a;
        }
        if(a%2==0 && b%2==0){
            return stein(a>>1,b>>1)<<1;
        }
        if(a%2==0){
            return stein(a>>1,b);
        }
        if(b%2==0){
            return stein(a,b>>1);
        }
        return stein((a+b)>>1,(a-b)>>1);
    }
    int main(){
        int m,n;
        scanf("%d %d",&m,&n);
        printf("%d",stein(m,n));
        return 0;
    }
    

    C++

    #include<iostream>
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    using namespace std;
    int stein(int m,int n){
        int a = max(m,n);
        int b = min(m,n);
        if(b == 0){
            return a;
        }
        if(a%2==0 && b%2==0){
            return stein(a>>1,b>>1)<<1;
        }
        if(a%2==0){
            return stein(a>>1,b);
        }
        if(b%2==0){
            return stein(a,b>>1);
        }
        return stein((a+b)>>1,(a-b)>>1);
    }
    int main(){
        int m,n;
        cin>>m>>n;
        cout<<stein(m,n)<<endl;
        return 0;
    }
    

    Java

    Python

    def stein(a,b):
        a,b = max(a,b),min(a,b)
        if b == 0:
            return a
        if a % 2 == 0 and b % 2 == 0:
            return stein(a>>1,b>>1)<<1
        if a % 2 == 0:
            return stein(a>>1,b)
        if b % 2 == 0:
            return stein(a,b>>1)
        return stein((a+b)>>1,(a-b)>>1)
    m,n = [int(i) for i in input().split()]
    print(stein(m,n))
    

    排序算法

    插入排序

    C

    #include<stdio.h>
    void insert_sort(int arr[], int len){
        int i,j,key;
        for (i=1;i<len;i++){
            key = arr[i];
            j=i-1;
            while((j>=0) && (arr[j]>key)) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = key;
        }
    }
    int main(){
        int n;
        int arr[100000];
        scanf("%d",&n);
        for(int i = 0 ;i < n;i++){
            scanf("%d",&arr[i]);
        }
        insert_sort(arr,n);
        for(int i = 0 ;i < n;i++){
            printf("%d ",arr[i]);
        }
    }
    

    C++

    #include<iostream>
    using namespace std;
    void insert_sort(int arr[], int len){
        int i,j,key;
        for (i=1;i<len;i++){
            key = arr[i];
            j=i-1;
            while((j>=0) && (arr[j]>key)) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = key;
        }
    }
    int main(){
        int n;
        int arr[100000];
        scanf("%d",&n);
        for(int i = 0 ;i < n;i++){
            scanf("%d",&arr[i]);
        }
        insert_sort(arr,n);
        for(int i = 0 ;i < n;i++){
            printf("%d ",arr[i]);
        }
    }
    

    Java

    Python

    def insertsort(arr):
        n = len(arr)
        for i in range(1,n):
            key = arr[i]
            j = i - 1
            while j >= 0 and key < arr[j]:
                arr[j+1]=arr[j]
                j -= 1
            arr[j+1] = key
    arr = [int(i)for i in input().split(" ")]
    insertsort(arr)
    print(arr)
    

    快速排序

    C

    #include<stdio.h>
    void swap(int *x, int *y) {
        int t = *x;
        *x = *y;
        *y = t;
    }
    void quick_sort_recursive(int arr[], int start, int end) {
        if (start >= end)
            return;
        int mid = arr[end];
        int left = start, right = end - 1;
        while (left < right) {
            while (arr[left] < mid && left < right)
                left++;
            while (arr[right] >= mid && left < right)
                right--;
            swap(&arr[left], &arr[right]);
        }
        if (arr[left] >= arr[end])
            swap(&arr[left], &arr[end]);
        else{
            left++;
            swap(&arr[left], &arr[end]);
        }
        if (left)
            quick_sort_recursive(arr, start, left - 1);
        quick_sort_recursive(arr, left + 1, end);
    }
    
    void quick_sort(int arr[], int len) {
        quick_sort_recursive(arr, 0, len - 1);
    }
    int main(){
        int n;
        int arr[100000];
        scanf("%d",&n);
        for(int i = 0 ;i < n;i++){
            scanf("%d",&arr[i]);
        }
        quick_sort(arr,n);
        for(int i = 0 ;i < n;i++){
            printf("%d ",arr[i]);
        }
    }
    

    C++

    #include<iostream>
    using namespace std;
    void swap(int *x, int *y) {
        int t = *x;
        *x = *y;
        *y = t;
    }
    void quick_sort_recursive(int arr[], int start, int end) {
        if (start >= end)
            return;
        int mid = arr[end];
        int left = start, right = end - 1;
        while (left < right) {
            while (arr[left] < mid && left < right)
                left++;
            while (arr[right] >= mid && left < right)
                right--;
            swap(&arr[left], &arr[right]);
        }
        if (arr[left] >= arr[end])
            swap(&arr[left], &arr[end]);
        else{
            left++;
            swap(&arr[left], &arr[end]);
        }
        if (left)
            quick_sort_recursive(arr, start, left - 1);
        quick_sort_recursive(arr, left + 1, end);
    }
    
    void quick_sort(int arr[], int len) {
        quick_sort_recursive(arr, 0, len - 1);
    }
    int main(){
        int n;
        int arr[100000];
        cin>>n;
        for(int i = 0 ;i < n;i++){
            cin>>arr[i];
        }
        quick_sort(arr,n);
        for(int i = 0 ;i < n;i++){
            cin>>arr[i];
        }
    }
    

    Java

    Python

    def quick_sort(arr, first, last):
        if first >= last:
            return
        mid = arr[first]
        low = first
        high = last
        while low < high:
            while low < high and arr[high] >= mid:
                high -= 1
            arr[low] = arr[high]
            while low < high and arr[low] < mid:
                low += 1
            arr[high] = arr[low]
        arr[low] = mid
        quick_sort(arr, first, low-1)
        quick_sort(arr, low+1, last)
    arr = [int(i)for i in input().split(" ")]
    quick_sort(arr,0,len(arr)-1)
    print(arr)
    

    相关文章

      网友评论

          本文标题:程序设计导论-3 基本算法实现 代码实现

          本文链接:https://www.haomeiwen.com/subject/xzabictx.html