排序.cpp

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef int Element;

inline bool judge(Element a[],int n) {
    for(int i=1;i<=n-1;i++) {
        if(a[i]>a[i+1]) return false;
    }
    return true;
}

//直接插入排序，下标从1开始
void InsertSort(Element a[],int n) {
    for(int i=2;i<=n;i++) {
        int pos=0,tmp = a[i];
        for(pos=i-1;pos>=1 && tmp<a[pos];pos--)
            a[pos+1] = a[pos];
        a[pos+1] = tmp;
    }
}

//冒泡排序，下标从1开始
void BubbleSort(Element a[],int n) {
    for(int i=1;i<=n;i++) {
        int tag = 0;
        for(int j=1;j<=n-i;j++) {
            if(a[j]>a[j+1]) {
                swap(a[j],a[j+1]);
                tag = 1;
            }
        }
        if(!tag) break;
    }
}

//希尔排序，下标从1开始
void ShellSort(Element a[],int n) {
    int  m = n;
    while(m!=1) {
        m /= 2;
        for(int i=m;i<=n;i++) {
            int tmp = a[i];
            int j;
            for(j=i;j>m && a[j-m] > tmp;j-=m) a[j] = a[j-m];
            a[j] = tmp;
        }
    }
}

//随机快速排序，下标从1开始
void QuickCore(Element a[],int l,int r) {
    if(l >= r) return ;
    int pos = l + rand()%(r-l);
    swap(a[pos],a[l]);
    int i = l, j = r,tmp = a[l];
    while(i < j) {
        while(a[j] >= tmp && i < j) j--;
        swap(a[i],a[j]);
        while(a[i] <= tmp && i < j) i++;
        swap(a[i],a[j]);
    }
    QuickCore(a,l,i-1);
    QuickCore(a,i+1,r);
}
void QuickSort(Element a[],int n) {
    QuickCore(a,1,n);
}

//基数排序，下标从1开始
#include <deque>
#include <algorithm>
int maxBits(Element a[],int n) {
    int b[16];
    for(int i=1;i<=n;i++) b[i] = a[i];
    int maxx = INT_MIN;
    for(int i=1;i<=n;i++) {
        int cnt = 0;
        while(b[i]) {
            cnt++;
            b[i] /= 10;
        }
        maxx = max(cnt,maxx);
    }
    return maxx;
}
void BaseSort(Element a[],int n) {
    int m = maxBits(a,n);
    deque<int> q[10];
    int b[16];
    for(int i=1;i<=n;i++) b[i] = a[i];
    int base = 10;
    while(m--) {
        for(int i=1;i<=n;i++)  q[ b[i]%10 ].push_back(a[i]);
        int u = 1;
        for(int i=0;i<10;i++) {
            while(!q[i].empty()) {
                a[u++] = q[i].front();
                q[i].pop_front();
            }
        }
        for(int i=1;i<=n;i++) b[i] = a[i]/base;
        base *= 10;
    }
}

//归并排序，下标从1开始
void MergeCore(Element a[],int l,int r) {
    if(l >= r) return ;
    int mid = (l+r)/2;
    MergeCore(a,l,mid);
    MergeCore(a,mid+1,r);
    int u = l;
    int tmp[105];
    int i =l, j = mid+1;
    while(i!=mid+1 && j!=r+1) {
        if(a[i]>a[j])         tmp[u++] = a[j++];
        else                  tmp[u++] = a[i++];
    }
    while(i!=mid+1) tmp[u++] = a[i++];
    while(j!=r+1)   tmp[u++] = a[j++];
    for(int k=l;k<=r;k++) a[k] = tmp[k];
}
void MergeSort(Element a[],int n) {
    MergeCore(a,1,n);
}

//堆排序，下标从0开始
void PercDown(int a[],int p,int n) {
    int x = a[p];
    int parent,child;
    for(parent = p;parent*2+1<n;parent = child) {
        child = parent*2+1;
        if((child!=n-1) && (a[child] < a[child+1])) child++;
        if(x > a[child]) break;
        else a[parent] = a[child];
    }
    a[parent] = x;
}
void HeapSort(Element a[],int n) {
    for(int i=n/2-1;i>=0;i--) PercDown(a,i,n);
    for(int i=n-1;i>0;i--) {
        swap(a[0],a[i]);
        PercDown(a,0,i);
    }
}


void print(Element a[],int n) {
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}

inline bool judge2(Element a[],int n) {
    for(int i=0;i<n-1;i++) {
        if(a[i]>a[i+1]) return false;
    }
    return true;
}

void test(Element a[],int n) {
    int t = 10;
    bool tag = true;
    while(t--) {
        //for(int i=1;i<=15;i++) a[i] = rand() % 101;
        //InsertSort(a,n);
        //BubbleSort(a,n);
        //ShellSort(a,n);
        //QuickSort(a,n);
        //BaseSort(a,n);
        //MergeSort(a,n);
        for(int i=0;i<15;i++) a[i] = rand() % 101;
        HeapSort(a,n);
        for(int i=0;i<15;i++) cout << a[i] << " ";
        //print(a,n);
        if(judge2(a,n)) cout<<"Yes"<<endl;
        else {
            cout<<"No!!!"<<endl;
            tag = false;
            break;
        }
    }
    if(tag) cout<<"Yes"<<endl;
    else    cout<<"No!"<<endl;
}

int main() {
    srand((unsigned)time(NULL));
    Element a[16];
    test(a,15);
    return 0;
}