|
Posted on 2010-03-12 22:02 sin 阅读(570) 评论(0) 编辑 收藏 引用 所属分类: 数据结构算法
排序算法原理都不难,实现起来却没那么简单,特别是一些边界问题的处理。 前些天把这些常有的排序算法实现了一遍,代码写的也不太好,很多i,j,k之类的变量,也很多循环嵌套,不过初步测试是正确的。
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
|