sin的博客

  1 #include <stdio.h>
  2 
  3 void swap(int *a, int *b);        //交换两个整数
  4 void output_arr(int arr[], int n);    //输出数组
  5 
  6 void strai_sort(int arr[], int n);    //直接插入排序
  7 void bubble_sort(int arr[], int n);    //冒泡排序
  8 
  9 int  qpass(int arr[], int i, int j);    //一趟快速排序
 10 void qsort(int arr[], int s, int t);    //快速排序
 11 
 12 void sift(int arr[], int n, int k);        //堆排序一趟筛选
 13 void makeheap(int arr[], int n);        //建堆
 14 void heapsort(int arr[], int n);        //堆排序
 15 
 16 void merge(int arr[], int low, int mid, int high);    //合并
 17 void mergesort(int arr[], int low, int high);        //归并排序
 18 
 19 
 20 static int temp[100];
 21 
 22 int main(int argc, char **argv)
 23 {
 24     int arr[] = {28, 40, 19, 20, 98, 74, 1, 40, 10, 35};
 25 
 26     printf("before sort:");
 27     output_arr(arr, sizeof(arr)/sizeof(arr[0]));
 28 
 29     //strai_sort(arr, sizeof(arr)/sizeof(arr[0]));
 30     //bubble_sort(arr, sizeof(arr)/sizeof(arr[0]));
 31     //qsort(arr, 0, sizeof(arr)/sizeof(arr[0])-1);    
 32     //heapsort(arr, sizeof(arr)/sizeof(arr[0]));    
 33     mergesort(arr, 0, sizeof(arr)/sizeof(arr[0])-1);
 34 
 35     printf("after sort:");
 36     output_arr(arr, sizeof(arr)/sizeof(arr[0]));    
 37 
 38     return 0;
 39 }
 40 
 41 void swap(int *a, int *b)
 42 {
 43     int temp;
 44     temp = *b;
 45     *b = *a;
 46     *a = temp;
 47 }
 48 
 49 void output_arr(int arr[], int n)
 50 {
 51     int i;
 52     for (i=0; i<n; ++i)
 53         printf("%d  ", arr[i]);
 54     printf("\n");
 55 }
 56 
 57 /*
 58  * 直接插入排序
 59  * 思想: 依次把 无序序列里的值 插入 到有序序列里；初始时，有序序列为arr[0]，无序序列为arr[1]arr[n-1]
 60  * 这种算法要不断的比较、移动数据，性能很差
 61  */
 62 void strai_sort(int arr[], int n)
 63 {
 64     int i,j,k;
 65     int temp;
 66 
 67     for (i=1; i<n; ++i)
 68     {
 69         temp = arr[i];  //记录下要插入的值为temp
 70         for (j=0; j<i; ++j)
 71         {
 72             if (temp < arr[j])  //如果有序序列arr[0]arr[i-1]里存在比temp大的值，这个值的索引为j
 73             {               //把arr[j]arr[i-1]向后移动，把temp插入到arr[j]的位置上
 74                 for (k=i; k>j; k--)
 75                 {
 76                     arr[k] = arr[k-1];
 77                 }
 78                 arr[j] = temp;
 79                 break;
 80             }
 81         }
 82     }        
 83 }
 84 
 85 /*
 86  * 冒泡排序原理：
 87  * 对n个整数，将最大数放到最后，即第n个位置
 88  * 然后剩余n-1个数，把剩余n-1个数中最大的放到最后，即第n-1个位置
 89  * 依次对前n-2 n-3个数处理，最后得到有序序列
 90  */
 91 void bubble_sort(int arr[], int n)
 92 {
 93     int i,j;
 94     for (i=0;i<n;++i)
 95     {
 96         for (j=1;j<n-i;++j)  //把arr[0]arr[n-i]中的最大值，放到n-i位置上
 97         {                //把这段代码抽象为一个函数会更简单    
 98             if (arr[j-1]>arr[j])
 99                 swap(&arr[j-1],&arr[j]);
100         }
101     }
102 }
103 
104 /*
105  * 一趟快速排序：
106  * 这里选择开始位置整数为标点，即第i个元素为标点
107  * 从后向前，找到比标点小的元素，跟标点交换位置；然后再从前向后，找到比标点大的元素后，跟标点交换位置
108  * 即不断把比标点小的元素移动标点左边，比标点大的元素移到标点右边
109  * 一趟快速排序快速排序后，标点元素就在一个正确位置上
110  */
111 int qpass(int arr[], int i, int j)
112 {
113     while (i<j)
114     {
115         while (j > i)
116         {
117             if (arr[j]<arr[i])
118             {
119                 swap(&arr[i],&arr[j]);
120                 i += 1;
121                 break;
122             }
123             j -= 1;
124         }
125         while (i < j)
126         {
127             if (arr[i]>arr[j])
128             {
129                 swap(&arr[i],&arr[j]);
130                 j -= 1;
131                 break;
132             }
133             i += 1;
134         }
135     }
136 
137     return i;
138 }
139 
140 void qsort(int arr[], int s, int t)
141 {
142     int pos;
143     if (s<t)
144     {
145         pos = qpass(arr, s, t);
146         qsort(arr,s,pos-1);
147         qsort(arr,pos+1,t);
148     }
149 }
150 
151 /*
152  * 堆排序
153  */
154 
155 //arr[k+1]arr[n-1]满足大顶堆的性质
156 //新元素arr[k]，左右孩子分别为arr[2*k+1]、arr[2*k+2]
157 //交换arr[k]和其左右孩子中较大的值，直到比其左右孩子都大 或者 到了序列边界
158 void sift(int arr[], int n, int k)
159 {
160     int i = k;
161     int j = 2i+1;
162     int flag = 0;
163 
164     while (j<n && !flag)
165     {
166         if ( j+1<n && arr[j+1]>arr[j] )
167             j += 1;
168         if ( arr[i]>=arr[j] )
169             flag = 1;
170         else
171         {
172             swap(&arr[i],&arr[j]);
173             i = j;
174             j = 2*i+1;
175         }
176     }
177 }
178 //对数组arr建堆
179 //初始时，arr[n/2]arr[n-1]都是叶子节点，即arr[n/2]arr[n-1]满足大顶堆的性质
180 void makeheap(int arr[], int n)
181 {
182     int i;
183     for (i=n/2-1; i>=0; i--)
184         sift(arr, n, i);
185 }
186 
187 void heapsort(int arr[], int n)
188 {
189     int i;
190 
191     makeheap(arr, n);
192 
193     for (i=n-1; i>0; i--)
194     {
195         swap(&arr[0],&arr[i]);
196         sift(arr, i-1, 0);
197     }
198 }
199 
200 /*
201  *arr[low]arr[mid] arr[mid+1]arr[high]为有序序列
202  * 合并这两个有序子序列为一个有序序列 
203  */
204 void merge(int arr[], int low, int mid, int high)
205 {
206     int i = low;
207     int j = mid+1;
208     int k;
209 
210     for(k=low; k<=high; k++)
211     {
212         temp[k] = arr[k];
213     }
214 
215     k = low;
216 
217     while ( i<=mid && j<=high )
218     {
219         if (temp[i]<temp[j])
220             arr[k++] = temp[i++];
221         else
222             arr[k++] = temp[j++];
223     }
224     while ( i<=mid )
225     {
226         arr[k++] = temp[i++];
227     }
228     while ( j<=high )
229     {
230         arr[k++] = temp[j++];
231     }
232 }
233 
234 /*
235  * 归并排序原理:
236  * 把一个无序序列中的每个元素视为有序子序列，把这些子序列两两合并成有序子序列
237  */
238 void mergesort(int arr[], int low, int high)
239 {
240     int mid;
241     if (low<high)
242     {
243         mid = (low+high)/2;
244         mergesort(arr, low, mid);
245         mergesort(arr, mid+1, high);
246         merge(arr, low, mid, high);
247     }
248 }
249