首页 > 代码库 > 将数组按不同种类分为三个部分(快排思想)

将数组按不同种类分为三个部分(快排思想)

不废话,直接上代码:

 

 1 /* 2  * 按照一位数,两位数,和三位数将数组中的元素分成三类, 3  * 并按照1位2位3位的顺序排列 4  */ 5  6 # include <stdio.h> 7 # include <stdlib.h> 8 # include <string.h> 9 # include <time.h>10 11 void sort2three(int *arr, int arr_len)12 {13     //i从左向右遍历,j从右向左遍历,k也从左向右遍历14     int i=0,j=arr_len-1,k=0;15     int temp_i,temp_j;16     //遍历结束的条件是k<j,当k=j的时候已经交换结束17     while(k<j){18         //当是三位数的时候,跳过,j--19         //当不是三位数的时候,停下来准备交换20         while(k<j&&arr[j]/100!=0){21             j--;22         }23         //将该数字暂存24         temp_j=arr[j];25         //同理,当一位数的时候,跳过,i++26         //当不是一位数的时候,停下来,准备交换27         while(k<j&&arr[i]/10==0){28             i++;29         }30         //将该数字暂存31         temp_i=arr[i];32         //这里要注意特别加的k<i的条件,因为如果k<i,这个时候再交换就会出错33         //所以要保证k是在i和j之间的34         //因为k是从左到右遍历,所以上边界很好控制,只需要k<j即可35         //所以前两个的条件是k<j,判断k的时候要加上k<i条件36         while((k<j&&arr[k]/100==0&&arr[k]/10!=0)||k<i){37             //当k处于i和j的中间并且不是三位数也不是两位数的时候,k++38             //当是三位数或者一位数的时候,停下来,准备与i或者j交换39             k++;40         }41         //当是一位数的时候,与i交换,当是三位数的时候,与j交换42         if(arr[k]/10==0){43             arr[i]=arr[k];44             arr[k]=temp_i;45         }else{46             arr[j]=arr[k];47             arr[k]=temp_j;48         }49     }50 }51 52 int main(void)53 {54     srand(time(NULL));55     int arr_len;56     int *arr;57     while(printf("Give me the length of array.\n"),scanf("%d",&arr_len)==1){58         if((NULL==(arr=(int *)malloc(sizeof(int)*arr_len)))){59             printf("Malloc ERROR!!\n");60         }61         int i;62         for(i=0;i<arr_len;i++){63             arr[i]=rand()%1000;64         }65         //调试时所用程序;66         //printf("Type~\n");67         //for(i=0;i<arr_len;i++){68             //scanf("%d",&arr[i]);69         //}70         printf("Let‘s begin...\n");71         for(i=0;i<arr_len;i++){72             printf("%d\t",arr[i]);73         }74         printf("\n");75         sort2three(arr, arr_len);76         for(i=0;i<arr_len;i++){77             printf("%d\t",arr[i]);78         }79         printf("\n");80         char ch;81         printf("再来一发?(y/n):\n");82         scanf("%*c%c",&ch);83         if(ch==y&&ch!=n){84             continue;85         }86         break;87     }88     return 0;89 }

 

将数组按不同种类分为三个部分(快排思想)