各种排序算法

C代码  

#include <stdio.h>
#define N 5

//从小到大
void bubbleSort(int p[]){
    int i=0,j=0,min=0;
    for(i=0;i<N;i++)
        for(j=N-1;j>i;j--){
            if(p[j]<p[j-1]){
                min=p[j-1];
                p[j-1]=p[j];
                p[j]=min;
            }
        }
}
//从大到小
void bubbleSort2(int p[]){
    int i=0,j=0,min=0;
    for(i=0;i<N-1;i++)
        for(j=i;j<N-1;j++){
            if(p[j]<p[j+1]){
                min=p[j];
                p[j]=p[j+1];
                p[j+1]=min;
            }
        }
}
//从小到大
void selectSort(int *p){
    int i=0,j=0,temp=0,min=0;
    for(i=0;i<N-1;i++){
        min=i;
        for(j=i+1;j<N;j++){
            if(p[j]<p[min]){
                min=j;
            }
        }
        if(min!=i){
            temp=p[i];
            p[i]=p[min];
            p[min]=temp;
        }
    }
}

//从大到小
void selectSort2(int *p){
    int i=0,j=0,temp=0,max=0;
    for(i=0;i<N-1;i++){
        max=i;
        for(j=i+1;j<N;j++){
            if(p[j]>p[max]){
                max=j;
            }
        }
        if(max!=i){
            temp=p[i];
            p[i]=p[max];
            p[max]=temp;
        }
    }
}

void insertSort(int p[]){
    int i=0,j=0,temp=0;
    for(i=1;i<N;i++){
        if(p[i]<p[i-1])
        {
            temp=p[i];
            for(j=i-1;temp<p[j]&&j>=0;j--)
            {
                    p[j+1]=p[j];
            }
            p[j+1]=temp;
        }
    }
}

void shellSort(int * p){
    int i=0,j=0,temp=0;
    int increment=N-1;
    while(increment>1){
        increment=increment/3+1;
        for(i=increment;i<N;i++){
            if(p[i]<p[i-increment]){
                temp=p[i];
                for(j=i-increment;j>=0&&temp<p[j];j-=increment)
                    p[j+increment]=p[j];
                p[j+increment]=temp;
            }
        }
    }
}

void heapAdjust(int *p,int i,int j){
    int lchild=2*i+1;
    int rchild=2*i+2;
    int max=i;
    int temp;
    if(i<=(N-1)/2){
        if(lchild<=N-1&&p[lchild]>max)
            max=lchild;
        if(rchild<=N-1&&p[rchild>max])
            max=rchild;
        if(max!=i)
        {
            temp=p[i];
            p[i]=p[max];
            p[max]=temp;
            heapAdjust(p,max,N-1);
        }
    }
}

void heapSort(int *p){
    int i=0,temp=0;
    for(i=(N-1)/2;i>=0;i--){
        heapAdjust(p,i,N-1);
    }
    for(i=N-1;i>=0;i--){
        temp=p[i];
        p[i]=p[0];
        p[0]=temp;
        heapAdjust(p,0,i-1);
    }
}

void merge(int *p,int low,int mid,int high){
    int i=low,j=mid+1,k=0;
    int array[10];
    while(i<=mid&&j<=high){
        array[k++]=p[i]<=p[j]?p[i++]:p[j++];
    }
    while(i<=mid)
        array[k++]=p[i++];
    while(j<=high)
        array[k++]=p[j++];
    for(i=low,k=0;i<=high;k++,i++)
        p[i]=array[k];
}

void mergeSort(int *p,int low,int high){
    int mid;
    if(low<high){
        mid=(low+high)/2;
        mergeSort(p,low,mid);
        mergeSort(p,mid+1,high);
        merge(p,low,mid,high);
    }
}

void quickSort(int p[],int left,int right){
    int i,j,x,temp,k;
    if(left<right){
        i=left-1;
        x=p[right];
        for(j=left;j<right;j++){
            if(p[j]<=x){
                i++;
                temp=p[i];p[i]=p[j];p[j]=temp;
            }
        }
        temp=p[i+1];p[i+1]=x;p[right]=temp;
        quickSort(p,left,i);
        quickSort(p,i+2,right);
    }
}
//位图排序,时间复杂度O(n)
void bitmapSort(){
    int unsort[]={3,5,4,2,1,7,6,8,10,9};
    int x=0,i=0;
    for(i=0;i<10;i++){
        x=x|(0x01<<(unsort[i]%32));
    }
    for(i=0;i<32;i++){
        if((x&(0x01<<i))==(0x01<<i))
            printf("%d ",i);
    }
}

void main(){
    int unsort[]={4,3,5,6,1,2},i;
    quickSort(unsort,0,5);
    for(i=0;i<6;i++)
    printf("%d ",unsort[i]);
    bitmapSort();
}