数据结构实验之排序二：交换排序

爱被打了一巴掌 2022-06-12 04:14 136阅读 0赞

Think:  
1知识点：快速排序+冒泡排序  
2反思：基础知识需要巩固反思，学习知识点要深入理解本质思想

[SDUT题目链接][SDUT]

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    int a[100004], b[100004];
    int cnt1, cnt2;
    
    void Qsort(int l, int r);
    
    int main(){
        int n, i, j, t;
        while(scanf("%d", &n) != EOF){
            cnt1 = cnt2 = 0;
            for(i = 0; i < n; i++){
                scanf("%d", &a[i]);
                b[i] = a[i];
            }
            for(i = 0; i < n; i++){
                for(j = 0; j < n-i-1; j++){
                    if(a[j] > a[j+1]){
                        cnt1++;
                        t = a[j], a[j] = a[j+1], a[j+1] = t;
                    }
                }
            }
            Qsort(0, n-1);
            printf("%d %d\n", cnt1, cnt2);
        }
        return 0;
    }
    void Qsort(int l, int r){
        int key = b[l], i = l, j = r;
        if(l >= r)
            return;
        while(i < j){
            while(i < j && key <= b[j]){
                j--;
            }
            if(b[i] != b[j]){
                b[i] = b[j];
                cnt2++;
            }
            while(i < j && key >= b[i]){
                i++;
            }
            if(b[j] != b[i]){
                b[j] = b[i];
                cnt2++;
            }
        }
        b[i] = key;
        Qsort(l, i-1);
        Qsort(i+1, r);
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 248KB
    Submit time: 2017-07-15 09:57:53
    ****************************************************/

[SDUT]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3399.html