c语言简单排序代码（C语言排序代码）

运行结果正确
还是快速排序难一些。

c语言简单排序代码（C语言排序代码）

完整代码

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 #include<stdio.h> #include <stdlib.h> #include <string.h> #include<malloc.h> void swap(int *a,int *b); void select_sort(int arr[],int n); void tra_arr(int arr[],int n); void insert_sort(int arr[],int n); void shell_sort(int arr[],int n); void perc_down(int arr[],int i,int n); void heap_sort(int arr[],int n); void merge(int arr[],int temp_arr[],int left_start,int right_start ,int right_end); void m_sort(int arr[],int temp_arr[],int left,int right); void merge_sort(int arr[],int n); int get_pri(int arr[],int left,int right); void q_sort(int arr[],int left,int right); void quick_sort(int arr[],int n); int main(){ int arr[100]={ 10,9,8,7,6,5,4,3,2,1 }; select_sort(arr,10); printf("\n简单选择排序结果\n"); tra_arr(arr,10); int arr1[100]={ 10,9,8,7,6,5,4,3,2,1 }; insert_sort(arr1,10); printf("\n插入排序结果\n"); tra_arr(arr1,10); int arr2[100]={ 10,9,8,7,6,5,4,3,2,1 }; shell_sort(arr2,10); printf("\n希尔排序结果\n"); tra_arr(arr2,10); int arr3[100]={ 10,9,8,7,6,5,4,3,2,1 }; heap_sort(arr3,10); printf("\n堆排序结果\n"); tra_arr(arr3,10); int arr4[100]={ 10,9,8,7,6,5,4,3,2,1 }; merge_sort(arr4,10); printf("\n归并排序结果\n"); tra_arr(arr4,10); int arr5[100]={ 10,9,8,7,6,5,4,3,2,1 }; quick_sort(arr5,10); printf("\n快速排序结果\n"); tra_arr(arr5,10); return 0; } void swap(int *a,int *b){ //在函数内部，如果打算接收的是指针的地址，那就不要加*, //如果想要的是值，那就加*,我也很讨厌指针，但是没办法 int t=*a; *a=*b; *b=t; } //简单选择排序 void select_sort(int arr[],int n){ int min; //这个过程一时半会讲不清楚，看书会清楚一些 for(int i=0;i<n;i++){ min=i; for(int j=i+1;j<n;j++){ if(arr[i]>arr[j]){ min=j; } } //经过上面的里层for，就找到了最小的元素的下表 swap(&arr[i],&arr[min]) ; } } //插入排序 void insert_sort(int arr[],int n){ int temp,j; for(int i=1;i<n;i++){ temp=arr[i]; for(j=i;j>0&&arr[j-1]>temp;j--){ //后挪 arr[j]=arr[j-1]; } //现在就找到空出来的插入位置了 arr[j]=temp; } } //希尔排序 void shell_sort(int arr[],int n){ int in,i,j,temp; //本来这个排序是很好理解的，就是这个外层的循环 //故弄玄虚，你就把他理解成一个简单的，递减的数组就行 //而且这个2的指数递减的序列的时间复杂度是很坏的 //最好使用SED或者HIB序列会好很多,这里只是演示 //两个里层的for就是插入排序,仔细看看就能看懂 for(in=n/2;in>0;in=in/2){ for(i=in;i<n;i++){ temp=arr[i]; for(j=i;j>=in;j=j-in){ if(arr[j-in]>temp){ //后挪 arr[j]=arr[j-in]; } else{ //arr[j-in]<temp，说明找到了 break; } } //上面执行完，肯定找到了插入位置 arr[j]=temp; } } } //首先是下滤操作 //i是根，n是heap的规模 //这里的下滤针对最大堆 void perc_down(int arr[],int i,int n){ int child,temp; //仔细想想，其实和插入排序差不多 //首先把i取出来，把i在堆里面所在的位置空出来 //这里和原来建堆的下滤又不一样，这里没有设置哨兵 for(temp=arr[i];(2*i+1)<n;i=child){ child=2*i+1; //如果当前儿子不是最后一个，说明还有右儿子 //两者取最大 if(child!=(n-1)&&arr[child]<arr[child+1]){ child++; } if(temp<arr[child]){ arr[i]=arr[child]; } else{ //当前取出来的值终于大于两个儿子时。 break; } } //上面轮完之后，肯定找到了一个儿子比我们取出来的值还要小的 arr[i]=temp; } void heap_sort(int arr[],int n){ int i; //建堆 for(i=n/2;i>=0;i--){ perc_down(arr,i,n); } //取最大值放在最后已经舍弃的位置上，下滤剩下的堆 for(i=n-1;i>0;i--){ //取最大值放在最后已经舍弃的位置上 swap(&arr[0],&arr[i]); // 滤剩下的堆 perc_down(arr,0,i); } } //归并排序 //第一步，写一个将两个已经排好序列的归并 void merge(int arr[],int temp_arr[],int left_start,int right_start ,int right_end) { int i,temp_start,elem_num,left_end; temp_start=left_start; left_end=right_start-1; elem_num=right_end-left_start+1; //归并的核心 while(left_start<=left_end&&right_start<=right_end){ if(arr[left_start]<=arr[right_start]){ temp_arr[temp_start++]=arr[left_start++]; } else{ temp_arr[temp_start++]=arr[right_start++]; } } while(left_start<=left_end){ temp_arr[temp_start++]=arr[left_start++]; } while(right_start<=right_end){ temp_arr[temp_start++]=arr[right_start++]; } //重新拷回去，记住，这里归并的只是原来数组的一部分，所以不能从头开始 for(i=0;i<elem_num;i++,right_end--) { arr[right_end]=temp_arr[right_end]; } } //第二步，递归调用归并，将数组不断分割 void m_sort(int arr[],int temp_arr[],int left,int right){ //tra_arr(arr,10); int center; //递归结束条件 if(left<right){ center=(right+left)/2; m_sort(arr,temp_arr,left,center); m_sort(arr,temp_arr,center+1,right); merge(arr,temp_arr,left,center+1,right); } } //第三步，初始化临时数组 void merge_sort(int arr[],int n){ int *temp_arr; temp_arr=(int*)malloc(n*sizeof(int)); m_sort(arr,temp_arr,0,n-1); free(temp_arr); } //快速排序 //首先，实现三数中值分割法,取一个“裁判” （中值） int get_pri(int arr[],int left,int right){ int center=(left+right)/2; if(arr[left]>arr[center]){ swap(&arr[left],&arr[center]); } if(arr[left]>arr[right]){ swap(&arr[left],&arr[right]); } if(arr[center]>arr[right]){ swap(&arr[center],&arr[right]); } //把中值扔到倒数第二个，因为上述操作已经让倒数第一大于中值了 swap(&arr[center],&arr[right-1]); return arr[right-1]; } //其次，实现分而治之 void q_sort(int arr[],int left,int right){ int i,j,pri; //如果规模已经小于三了，就不要再分而治之了，没得分了 if(right-left>=3){ //取中值 pri= get_pri(arr,left,right); //取左右往中间靠拢的两个指针i,j i=left; j=right-1; //开始判断 while(1){ //如果当前i对应的值小于裁判，继续推进 while(arr[++i]<pri); // 如果当前i对应的值大于裁判，继续推进 while(arr[--j]>pri); //上面走完，肯定碰到硬杈了，在i和j没有错位的情况下 //交换 if(i<j){ swap(&arr[i],&arr[j]); } else{ break; } } swap(&arr[i],&arr[right-1]); //这个i的作用远不止此,这个i还记录了上一个裁判的位置 //开始对分下来的两个部分进行同样的操作 q_sort(arr,left,i-1); q_sort(arr,i+1,right); } //如果递归到规模已经无法再分了 //就用普通的方法排序 else{ /*这里稍微讲一下 数组和指针实际上是一样的东西 到这里了，那肯定就剩一个或者两个元素了 所以数组的开头变成left所指的位置，现在left所在位置的下标 就是0，所以后面的n也要相应变化*/ insert_sort(arr+left,right-left+1); } } //最后包装一下 void quick_sort(int arr[],int n){ q_sort(arr,0,n-1); } //遍历数组 void tra_arr(int arr[],int n){ for(int i=0;i<n;i++){ printf("%d ",arr[i]); } printf("\n"); }