데이터 구조의 8 에서 자주 사용 되 는 정렬

#include 
using namespace std;
const int maxn = 20;
int a[maxn], b[maxn], n;
int cnt; //    
void PrintSequence(int *s) {
    for (int i = 1 ; i <= n ; i++) {
        printf("%d%c", s[i], i == n ?'
':' ');
    }
}

//      
void DirectInsertSort(int *a) {
    cnt = 0;
    for (int i = 2 ; i <= n ; i++) {
        cnt++;
        if ( a[i] < a[i-1] ) {
            a[0] = a[i];
            a[i] = a[i-1];
            int j;
            for (j = i - 2 ; a[0] < a[j] ; j--) {
                a[j+1] = a[j];
            }
            a[j+1] = a[0];
            cnt++;
        }
        printf(" %d       : ", i - 1);
        PrintSequence(a);
    }
    printf("     : %d
",cnt);
}

//      
void BInsertSort(int *a) {
    cnt = 0;
    for (int i = 2 ; i <= n ; i++) {
        cnt++;
        if (a[i] < a[i-1]) {   //                
            a[0] = a[i];
            int low = 1, high = i-1;
            while (low <= high) {
                int mid = (low + high) >> 1;
                if( a[i] < a[mid] ) high = mid - 1;
                else low = mid + 1;
            }
            //low = high + 1;
            for (int j = i - 1 ; j >= low ; j--) {
                a[j+1] = a[j];
            }
            a[low] = a[0];
        }
        printf(" %d       : ", i - 1);
        PrintSequence(a);
    }
    printf("     : %d
",cnt);
}

//    
void ShellSort(int *a) {
    cnt = 0; int d = n/2;
    while (d) {
        printf("d = %d         : 
", d);
        for (int i = d + 1 ; i <= n ; i++) {
            cnt++;
            if (a[i] < a[i - d]) {
                a[0] = a[i]; int j;
                for (j = i - d ; j > 0 && a[0] < a[j] ; j -= d){
                    a[j + d] = a[j];
                }
                a[j + d] = a[0];

            }
            PrintSequence(a);
        }
        d /= 2;
    }
    printf("     : %d
",cnt);
}

//      
void TwoMergeSort(int *a) {
    cnt = 0;
    int b[maxn]; b[0] = a[1];
    int first = 0, final = 0;
    for (int i = 2 ; i <= n ; i++) {
        cnt++;
        if( a[i] < b[first] ) {
            first = (first-1+n)%n;
            b[first] = a[i];
        }
        else if( a[i] > b[final] ) {
            b[++final] = a[i];
        }
        else {
            int j;
            for (j = first ; a[i] >= b[j] ; j = (j+1)%n){
                b[(j-1+n)%n] = b[j];
            }
            b[(j-1+n)%n] = a[i];
            first = (first-1+n)%n;
        }
        //cout << first << ' ' << final << endl;
    }
    int k = 0;
    for (int i = 0 ; i < n ; i++ ){
        a[++k] = b[(i + first) % n];
    }
    printf("          : 
");
    PrintSequence(a);
    printf("     : %d
",cnt);
}

//    
void BubbleSort(int *a) {
    cnt = 0; int tt = 0;
    for (int i = 0 ; i < n - 1; i++) {
        for (int j = 2 ; j <= n - i ; j++) {
            cnt++;
            if( a[j] < a[j - 1] ) {
                a[j] ^= a[j - 1] ^= a[j] ^= a[j - 1];
            }
        }
        printf(" %d     : ", ++tt);
        PrintSequence(a);
    }
    printf("     : %d
",cnt);
}

//  
int fast = 0;
int Partiton(int *a, int low, int high) {
    a[0] = a[low];
    while (low < high) {
        while (low < high && a[high] >= a[0] ) high--, cnt++;
            a[low] = a[high];
        while (low < high && a[low] <= a[0] ) low++, cnt++;
            a[high] = a[low];
        cnt += 2;
    }
    a[low] = a[0];
    printf(" %d     : ", ++fast);
    PrintSequence(a);
    return low;
}

void QSort(int *a,int low, int high) {
    if(low < high ) {
        int pos = Partiton(a, low, high);
        //cout << "AAA" << pos << endl;
        QSort(a, low, pos-1);
        QSort(a, pos+1, high);
    }
}

//      
void SimpleSelectSort(int *a) {
    cnt = 0; int tt = 0;
    for (int i = n ; i > 1 ; i--) {
        int pos = i;
        for (int j = 1 ; j <= i ; j++) {
            cnt++;
            if( a[pos] < a[j] ) {
                pos = j;
            }
        }
        if(pos != i){
            a[pos] ^= a[i] ^= a[pos] ^= a[i];
        }
        printf(" %d     : ", ++tt);
        PrintSequence(a);
    }
    printf("     : %d
",cnt);
}

//   
int heap = 0;
void HeapAdjust(int *a, int s,int m) {
    int tmp = a[s];
    for (int j = 2*s ; j <= m ; j *= 2) {
        cnt++;
        if ( j < m && a[j] < a[j+1]) j++; //j  key         
        if ( tmp > a[j] ) break;          //        ,            
        a[s] = a[j]; s = j;               //             !
    }
    a[s] = tmp;
    if (heap > 0) {
        printf(" %d    : ", ++heap);
        PrintSequence(a);
    }
}

void HeapSort(int *a) {
    cnt = 0;
    for (int i = n/2 ; i >= 1 ; i--) {
        HeapAdjust(a, i, n);
    }
    //cout << "AAA" << endl;
    printf(" %d    : ", ++heap);
    PrintSequence(a);
    for (int i = n ; i > 1 ; i--) {
        a[1] ^= a[i] ^= a[1] ^= a[i];
        HeapAdjust(a, 1, i-1);
    }
    printf("     : %d
",cnt);
}

void work() {
    printf("            (      15 ~)
");
    scanf("%d",&n);
    printf("      ~
");
    for (int i = 1 ; i <= n ; i++) {
        scanf("%d", b + i);
    }
    memcpy(a,b,sizeof(b));
}
void solve() {
    int ans = 0;
    while(true) {
        ans++;
        printf("        ?(Y/N)
");
        char op[5]; scanf("%s", op);
        if( op[0] == 'N' || op[0] == 'n') break;
        if (ans == 1) {
            work();
        }
        else {
            printf("          (Y/N)
");
            char s[5]; scanf("%s", s);
            if(s[0] == 'Y' || s[0] == 'y') memcpy(a,b,sizeof(b));
            else work();
        }
        //PrintSequence(a);
        printf("     8                  ,         
");
        printf("        1:      
");
        printf("        2:      
");
        printf("        3:      
");
        printf("        4:      
");
        printf("        5:      
");
        printf("        6:      
");
        printf("        7:      
");
        printf("        8:      
");
        int sel; scanf("%d",&sel);
        while (sel < 1 || sel > 8) {
            printf("    ,     
");
            scanf("%d",&sel);
        }
        switch(sel) {
            case 1: system("cls");
                    printf("   : ");
                    PrintSequence(a);
                    DirectInsertSort(a);
                    break;
            case 2: system("cls");
                    printf("   : ");
                    PrintSequence(a);
                    BInsertSort(a);
                    break;
            case 3: system("cls");
                    printf("   : ");
                    PrintSequence(a);
                    ShellSort(a);
                    break;
            case 4: system("cls");
                    printf("   : ");
                    PrintSequence(a);
                    TwoMergeSort(a);
                    break;
            case 5: system("cls");
                    printf("   : ");
                    PrintSequence(a);
                    BubbleSort(a);
                    break;
            case 6: system("cls");
                    printf("   : ");
                    PrintSequence(a);
                    QSort(a, 1, n);
                    printf("     : %d
",cnt);
                    break;
            case 7: system("cls");
                    printf("   : ");
                    PrintSequence(a);
                    SimpleSelectSort(a);
                    break;
            case 8: system("cls");
                    printf("   : ");
                    PrintSequence(a);
                    HeapSort(a);
                    break;
        }
    }
}

int main()
{
    // freopen("in.txt","r",stdin);
    //  freopen("out.txt","w",stdout);
    int t = 1 ;
    //scanf("%d",&t);
    while(t--){
        //printf("Case #%d: ", cas++);
        solve();
        //printf("
");
    }
}