sort

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<time.h> 
  4 struct SortObject{
  5     int n;
  6     int * record;
  7 };
  8 typedef struct SortObject * Array;
  9 
 10 void insertSort(Array a){
 11     int i,j;
 12     int temp;
 13     for(i=1;i<a->n;++i){
 14         temp=a->record[i];
 15         for(j=i-1;temp<a->record[j]&&j>=0;j--){
 16             a->record[j+1]=a->record[j];
 17         }
 18         if(j!=i-1){
 19             a->record[j+1]=temp;
 20         }
 21     }
 22 }
 23 void shellSort(Array a,int d){
 24     int i,j,inc;
 25     int temp;
 26     for(inc=d;inc>0;inc/=2){
 27         for(i=inc;i<a->n;i++){
 28             temp=a->record[i];
 29             for(j=i-inc;j>=0&&temp<a->record[j];j-=inc){
 30                 a->record[j+inc]=a->record[j];
 31             }
 32             a->record[j+inc]=temp;
 33         }
 34     }
 35 }
 36 void selectSort(Array a){
 37     int i,j,k;
 38     int temp;
 39     for(i=0;i<a->n-1;i++){
 40         k=i;
 41         for(j=i+1;j<a->n;j++){
 42             if(a->record[j]<a->record[k]){
 43                 k=j;
 44             }
 45         }
 46         if(k!=i){
 47             temp=a->record[i];
 48             a->record[i]=a->record[k];
 49             a->record[k]=temp;
 50         }
 51     }    
 52 }
 53 void bubbleSort(Array a){
 54     int i,j,noswap;
 55     int temp;
 56     for(i=0;i<a->n-1;i++){
 57         noswap=1;
 58         for(j=0;j<a->n-i-1;j++){
 59             if(a->record[j+1]<a->record[j]){
 60                 temp=a->record[j];
 61                 a->record[j]=a->record[j+1];
 62                 a->record[j+1]=temp;
 63                 noswap=0;
 64             }
 65         }
 66         if(noswap){
 67             break;
 68         }
 69     }    
 70 }
 71 void quickSort(Array a,int l,int r){
 72     int i,j;
 73     int temp;
 74     if(l>=r)return;
 75     i=l;j=r;temp=a->record[i];
 76     while(i!=j){
 77         while(i<j&&a->record[j]>=temp){
 78             j--;
 79         }
 80         if(i<j){
 81             a->record[i++]=a->record[j];
 82         }
 83         while(i<j&&a->record[i]<=temp){
 84             i++;
 85         }
 86         if(i<j){
 87             a->record[j--]=a->record[i];
 88         }
 89     }
 90     a->record[i]=temp;
 91     quickSort(a,l,i-1);
 92     quickSort(a,i+1,r);
 93 }
 94 void sift(Array a,int size,int p){
 95     int temp=a->record[p];
 96     int child=2*p+1;
 97     while(child<size){
 98         if((child<size-1)&&(a->record[child]<a->record[child+1])){
 99             child++;
100         }
101         if(temp<a->record[child]){
102             a->record[p]=a->record[child];
103             p=child;child=2*p+1;
104         }
105         else{
106             break;
107         }
108     }
109     a->record[p]=temp;
110 }
111 void heapSort(Array a){
112     int i,n;
113     int temp;
114     n=a->n;
115     for(i=n/2;i>=0;i--){
116         sift(a,n,i);
117     }
118     for(i=n-1;i>0;i--){
119         temp=a->record[0];
120         a->record[0]=a->record[i];
121         a->record[i]=temp;
122         sift(a,i,0);
123     }
124 }
125 void buildArray(Array a){
126     int i;
127     for(i=0;i<a->n;i++){
128         a->record[i]=rand()%100+1;
129         printf("%d,",a->record[i]);
130     }
131     printf("
");
132 }
133 void printArray(Array a){
134     int i;
135     for(i=0;i<a->n;i++){
136         printf("%d,",a->record[i]);
137     }
138     printf("
");
139     printf("
");
140 }
141 
142 int main(){
143     Array a=(Array)malloc(sizeof(struct SortObject));
144     a->n=8;
145     if(a!=NULL){
146         a->record=(int *)malloc(sizeof(int)*a->n);
147     }
148     else{
149         printf("out of space");
150     }
151     srand(time(NULL));
152     printf("1.directInsertSort:
");
153     buildArray(a);
154     insertSort(a);
155     printArray(a);
156     printf("2.shellSort:
");
157     buildArray(a);
158     shellSort(a,a->n/2);
159     printArray(a);
160     printf("3.simpleSelectSort:
");
161     buildArray(a);
162     selectSort(a);
163     printArray(a);
164     printf("4.bubbleSort:
");
165     buildArray(a);
166     bubbleSort(a);
167     printArray(a);
168     printf("5.quickSort:
");
169     buildArray(a);
170     quickSort(a,0,a->n-1);
171     printArray(a);
172     printf("6.heapSort:
");
173     buildArray(a);
174     heapSort(a);
175     printArray(a);
176     return 0;
177 }