实现排序（二分、插入、堆排

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <time.h>
  4 #include "head.h"
  5 using namespace std;
  6 //realize headSort
  7 const int maxn=1000;
  8 typedef int KeyType;
  9 typedef int DataType;
 10 typedef struct {
 11     KeyType key;
 12     DataType info;
 13 }RecordNode;
 14 typedef struct {
 15     int n;//n for num of recornode
 16     RecordNode * record;
 17 }SortObject;
 18 void printStruct(SortObject * pvector);
 19 void sift(SortObject * pvector, int size, int p);
 20 void headSort(SortObject *pvector);
 21 void insertSort (SortObject *pvector);
 22 void binSort(SortObject *sortObject);
 23 
 24 int main() {
 25     SortObject *sortObject = (SortObject *)malloc(sizeof( SortObject));
 26     srand((unsigned )time(NULL));
 27     RecordNode r[maxn];
 28 
 29     sortObject->record=r;
 30 
 31     sortObject->n=0;
 32 
 33     for (int i = 0; i < maxn; ++i) {
 34         r[i].key=rand();
 35         sortObject->n++;
 36     }
 37     clock_t start,end;
 38 
 39     printf("befort Sort
");
 40     printStruct(sortObject);
 41     printf("***************************************************************************************************************************************************************************
");
 42     start=clock();
 43    // headSort(sortObject);
 44   // insertSort(sortObject);
 45     binSort(sortObject);
 46     end = clock();
 47     printf("binSort 1000 num using time = %f ms
",(double)end-start/CLK_TCK);
 48     printf("after Sort
");
 49     printStruct(sortObject);
 50     return 0;
 51 
 52 }
 53 void headSort(SortObject *pvector)
 54 {
 55     int i,n;
 56     RecordNode temp;
 57     n=pvector->n;
 58     for ( i = n/2-1; i >= 0 ; --i) {
 59         sift(pvector,n,i);
 60     }
 61 
 62     for( i = n - 1; i > 0; i--)
 63     {
 64         temp = pvector->record[0];
 65         pvector->record[0] = pvector->record[i];
 66         pvector->record[i] = temp;
 67         sift(pvector, i, 0);
 68     }
 69 }
 70 
 71 void sift(SortObject * pvector, int size, int p)
 72 {
 73     RecordNode  temp = pvector ->record[p];
 74     int child = 2 * p  + 1;
 75     while (child < size)
 76     {
 77         if ((child < size - 1 ) &&
 78         (pvector->record[child].key < pvector->record[child + 1].key) )
 79         {
 80             child++;
 81         }
 82         if (temp.key < pvector->record[child].key) {
 83             pvector->record[p] = pvector->record[child];
 84 
 85             p = child;
 86             child = 2 * p + 1;
 87         }else break;
 88     }
 89 pvector->record[p]= temp;
 90 }
 91 void printStruct(SortObject * pvector)
 92 {
 93     RecordNode *temp=pvector->record;
 94     int cnt=0;
 95     while(cnt<maxn)
 96     {
 97         printf("%d ",temp[cnt].key);
 98         cnt++;
 99     }
100 }
101 void insertSort (SortObject *pvector)
102 {
103     int i,j;
104     RecordNode tmp;
105     RecordNode *data = pvector->record;
106     for(i = 1; i < pvector->n; i++)
107     {
108         tmp = data[i];
109         for(j= i-1; tmp.key < data[j].key && j >= 0 ; j--)
110         {
111             data[j + 1] = data[j];
112         }
113             if (j != i-1)
114             {
115                 data[j + 1] = tmp;
116             }
117     }
118 }
119 void binSort(SortObject *sortObject)
120 {
121     int i, j, left, mid, right;
122     RecordNode temp;
123     RecordNode *data = sortObject->record;
124     for(i = 1; i < sortObject->n; i++)
125     {
126         temp = data[i];
127         left = 0;
128         right = i-1;
129 
130         while (left <= right)
131         {
132             mid = (left + right)/2;
133             if(temp.key < data[mid].key)
134             {
135                 right = mid - 1;
136             }else{
137                 left = mid + 1;
138             }
139         }
140             for(j = i -1;  j>= left ;j--)
141             {
142                 data[j+1]=data[j];
143             }
144             if(left != i)
145             {
146                 data[left] = temp;
147             }
148 
149     }
150 }
View Code