정렬 알고리즘 - 정렬 알고리즘 집합

7013 단어 정렬 알고리즘
정렬 알고리즘 은 데이터 구조의 중점 내용 을 학습 하 는 것 임 에 틀림없다. 본 고 는 정렬 알고리즘 의 집합 을 제시 할 것 이다.
다음은 구체 적 인 실현 이다.
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define N 1000000

int Array[N];
int Temp[N];

//1、    
void BubbleSort(int a[],int n){
    int i,j;
    int temp;
    int tag;

    for(i=n-1;i>0;i--){
		tag = 0;
        for(j=0;j<i;j++)
              if(a[j]>a[j+1]){
                  temp=a[j];
                  a[j]=a[j+1];
                  a[j+1]=temp;
                  tag=1;
                  }
        if(tag==0) break;
        }

    }

//2、      
void SimpleInsertSort(int a[],int n){
    int i,j,k;
    int temp;

    for(i=1;i<n;i++){
        for(j=0;j<i;j++)
               if(a[j]>a[i]){
                   k=j;
                   break;
                   }
        if(j==i) continue;
        temp=a[i];
        for(j=i;j>k;j--)
               a[j]=a[j-1];
        a[k]=temp;
        }
    }

//3、    
void ShellSort(int a[],int n,int d){
    int h,i,j,k;
    int temp;

    do{
        d=d/3+1;
        for(h=0;h<d;h++)
               for(i=h+d;i<n;i+=d){
                   for(j=h;j<i;j+=d)
                          if(a[j]>a[i]){
                              k=j;
                              break;
                              }
                    if(j==i) continue;
                    temp=a[i];
                    for(j=i;j>k;j-=d)
                           a[j]=a[j-d];
                    a[k]=temp;
                   }
        }while(d>1);
    }

//4、      
void SimpleSelectSort(int a[],int n){
    int i,j,k;
    int temp;
    for(i=0;i<n;i++){
        temp=a[i];
        k=i;
        for(j=i+1;j<n;j++)
               if(a[j]<temp){
                   temp=a[j];
                   k=j;
                   }
        if(k!=i){
            temp=a[i];
            a[i]=a[k];
            a[k]=temp;
            }
        }
    }

//5、   
void CreateHeap(int a[],int n){
    int i,j;
    int temp;

    for(i=(n-2)/2;i>=0;i--){
        j=2*i+1;
        while(j<n){
            if(j+1<n&&a[j+1]>a[j])
                 j++;
            if(a[(j-1)/2]<a[j]){
                temp=a[(j-1)/2];
                a[(j-1)/2]=a[j];
                a[j]=temp;
                }
            else break;
             j=2*j+1;
            }
        }
    }

void HeapAdjust(int a[],int n){
    int i=0;
    int j;
    int temp;
    while(i<n&&2*i+1<n){
        j=2*i+1;
        if(j+1<n&&a[j+1]>a[j])
            j++;

        if(a[i]<a[j]){
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
            }
        else break;
        i=j;
        }
    }

void HeapSort(int a[],int n){
    int i;
    int temp;
    CreateHeap(a,n);
    for(i=n-1;i>0;i--){
        temp=a[i];
        a[i]=a[0];
        a[0]=temp;
        HeapAdjust(a,i);
        }
    }

//6、    
int partition(int a[],int low,int high){
    int pivotKey=a[low];
    while(low<high){
        while(low<high&&pivotKey<=a[high])
                    high--;
        a[low]=a[high];
        while(low<high&&a[low]<=pivotKey)
                    low++;
        a[high]=a[low];
        }
    a[low]=pivotKey;
    return low;
    }

void QuickSort(int a[],int low,int high){
    int pivotTag;
    if(low<high){
        pivotTag=partition(a,low,high);
        QuickSort(a,low,pivotTag-1);
        QuickSort(a,pivotTag+1,high);
        }
    }

//7、    
void Merge(int a[],int p,int q,int r){
    int i,j;
    int *ptr=(int*)malloc((r-p+1)*sizeof(int));
    int begin_1,end_1,begin_2,end_2;
    begin_1=p;
    end_1=q;
    begin_2=q+1;
    end_2=r;
    j=0;

    while(begin_1<=end_1&&begin_2<=end_2){
        if(a[begin_1]<=a[begin_2]){
            ptr[j]=a[begin_1];
            begin_1++;
            }
        else{
            ptr[j]=a[begin_2];
            begin_2++;
            }
        j++;
        }

    while(begin_1<=end_1)
                ptr[j++]=a[begin_1++];
    while(begin_2<=end_2)
                 ptr[j++]=a[begin_2++];

    for(i=0;i<r-p+1;i++)
           a[p+i]=ptr[i];

    free(ptr);
    }

void MergeSort(int a[],int first,int last){
    int mid;

    if(first<last){
        mid=(first+last)/2;
        MergeSort(a,first,mid);
        MergeSort(a,mid+1,last);
        Merge(a,first,mid,last);
        }
    }

//8、    (LSD)
int MaxBit(int a[],int n){
    int i;
    int d=1;
    int p=10;
    for(i=0;i<n;i++)
           while(a[i]>=p){
               p*=10;
               ++d;
               }
    return d;
    }

void RadixSort(int a[],int n){
    int i,j,k;
    int radix=1;
    int d=MaxBit(a,n);
    int *ptr=(int*)malloc(n*sizeof(int));
    int *count=(int*)malloc(10*sizeof(int));

    for(i=1;i<=d;i++){
        for(j=0;j<10;j++)
               count[j]=0;

        for(j=0;j<n;j++){
            k=(a[j]/radix)%10;
            count[k]++;
            }

        for(j=1;j<10;j++)
              count[j]=count[j-1]+count[j];

        for(j=n-1;j>=0;j--){
            k=(a[j]/radix)%10;
            count[k]--;
            ptr[count[k]]=a[j];
            }

        for(j=0;j<n;j++)
              a[j]=ptr[j];

        radix*=10;
        }

        free(ptr);
        free(count);
    }

int main(void){
    int i;
    int index;
    clock_t first,second;

    for(i=0;i<N;i++)
           Array[i]=rand()%N;

    /*printf("     :
"); for(i=0;i<N;i++) printf("%d\t",Array[i]); printf("
");*/ while(1){ for(i=0;i<N;i++) Temp[i]=Array[i]; printf(" :
"); printf("1---
"); printf("2---
"); printf("3---
"); printf("4---
"); printf("5---
"); printf("6---
"); printf("7---
"); printf("8---
"); scanf("%d",&index); if(index<1||index>8) break; first=clock(); switch(index){ case 1: BubbleSort(Temp,N); break; case 2: SimpleInsertSort(Temp,N); break; case 3: ShellSort(Temp,N,10); break; case 4: SimpleSelectSort(Temp,N); break; case 5: HeapSort(Temp,N); break; case 6: QuickSort(Temp,0,N-1); break; case 7: MergeSort(Temp,0,N-1); break; default: RadixSort(Temp,N); } second=clock(); /*printf(" :
"); for(i=0;i<N;i++) printf("%d\t",Temp[i]);*/ printf(" :%f

",(double)(second-first)/CLOCKS_PER_SEC); } return 0; }

좋은 웹페이지 즐겨찾기