疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

Java程序员必知的排序逻辑


 

       在进入编程世界的时候,除了“hello word”外,最长接触到的就是排序了,各种逻辑和算法、循环方式是最让人晕眩的,但是,只要你掌握了基础,学起其他的知识就显得容易许多。今天,我们就一起来看看几个程序员最常接触到的排序写法。

  1.基数排序

  bool radixsort(int *array,int n)

  {

  L TENL[10]; //其中TENL[m].number中存储,数据的第i位为m的数据

  int k;

  for(int i=0;i<10;i++)

  TENL[i].n=0;

  for(i=1;i<=5;i++) //这里假设 数据都 小于100000,对数据进行五次分配

  {

  for(int j=0;j

  {

  k=getnum(array[j],i);

  TENL[k].number[TENL[k].n]=array[j];

  TENL[k].n++;

  }

  j=0;

  for(k=0;k<10;k++) //将此次分配后的数据,按顺序重新置入array中

  {

  for(int m=0;m

  array[j++]=TENL[k].number[m];

  TENL[k].n=0;

  }

  }

  return true;

  }

  int getnum(int num,int i) //从个位起,获得num的第i为数据

  {

  int temp=1;

  for(int j=0;j

  temp=temp*10;

  return (num%temp-num%(temp/10))/(temp/10);

  }

  2.简单的选择排序

  bool selectionsort(int *array,int n) //array为存储数据的数组,n为数组元素个数

  {

  int k,temp; //k用来存储,临时最小数据的位置

  for(int i=0;i

  {

  k=i;

  for(int j=i+1;j

  if(array[j]

  k=j;

  if(k!=i) //若最小数,不为array[i],则array[i]与array[k]进行交换

  {

  temp=array[i];

  array[i]=array[k];

  array[k]=temp;

  }

  }

  return true;

  }

  3.插入排序

  bool insertionsort(int *array,int n)

  {

  int temp; //用来存储,插入的数据

  for(int i=1;i

  {

  temp=array[i]; //用temp记录array[i]

  for(int j=i-1;j>=0;j--) //逐个向前寻找插入点

  {

  if(temp>array[j]) //找到,跳出循环

  break;

  else //没找到,将前一个数据后移

  array[j+1]=array[j];

  }

  array[j+1]=temp;

  }

  return true;

  }

  4.冒泡排序

  bool bubblesort(int *array,int n)

  {

  int flag=1, //用来标记是否发生交换

  temp;

  for(int i=0;i

  {

  for(int j=i+1;j

  {

  if(array[j]

  {

  temp=array[i];

  array[i]=array[j];

  array[j]=temp;

  flag=0;

  }

  }

  if(flag) //如果flag为真,及没发生交换,直接跳出循环

  break;

  else

  flag=1;

  }

  return true;

  }

  5.自底向上排序

  bool bottomupsort(int *array,int n)

  {

  int length=1,temp_length,i; //temp_length表示单个合并数组的长度

  while(length

  {

  temp_length=length; //length表示合并后数组的长度

  length=2*temp_length;

  i=0; //i用于记录合并数组的起始位置

  while(i+length-1<=n-1)

  {

  merge(array,i,i+temp_length,i+length-1); //合并i~i+temp_length-1 和 i+temp_length~i+length-1 段

  i=i+length; //取下一个合并段的起始位置

  }

  if(i+temp_length

  merge(array,i,i+temp_length,n-1); //对尾部剩余段合并

  }

  return true;

  }

  bool merge(int *array,int start1,int start2,int n) //合并两个有序数组

  {

  int temp_n=n-start1+1, //两合并数组的长度和

  *temp_array,

  n1=start2-1, //第一个有序数组的末端位置

  temp_start1=start1; //记录start1的初始位置

  temp_array=(int *)malloc(sizeof(int)*temp_n); //申请长度为temp_n的整形空间,用于临时存储合并后的数组

  for(int i=0;start1<=n1&&start2<=n;i++) //对两个有序数组进行合并,存储于temp_array

  {

  if(array[start1]<=array[start2])

  {

  temp_array[i]=array[start1];

  start1++;

  }

  else

  {

  temp_array[i]=array[start2];

  start2++;

  }

  }

  if(start1<=n1)

  {

  while(start1<=n1)

  {

  temp_array[i++]=array[start1];

  start1++;

  }

  }

  else

  {

  while(start2<=n)

  {

  temp_array[i++]=array[start2];

  start2++;

  }

  }

  for(i=0,start1=temp_start1;i

  {

  array[start1]=temp_array[i];

  }

  free(temp_array);

  return true;

  }

  6.快速排序

  void QuickSort(int low,int high,int *array)

  {

  int pos;

  if(low

  {

  pos=SPLIT(low,high,array); //以array[low]进行划分,pos最为划分点

  //前一部分

  QuickSort(low,pos-1,array); //对划分后的前一部分递归处理

  QuickSort(pos+1,high,array); //对划分后的后一部分递归处理

  }

  }

  int SPLIT(int low,int high,int *array)

  {

  int temp=array[low]; //用temp来记录划分数

  while(low

  {

  while(array[high]>temp&&low

  high--;

  if(low==high)

  break;

  else

  {

  array[low]=array[high];

  low++;

  }

  while(array[low]

  low++;

  if(low==high)

  break;

  else

  {

  array[high]=array[low];

  high--;

  }

  }

  array[low]=temp; //最终low=high作为划分点,并将划分数存于array[low]

  return low;

  }

  7.归并排序

  bool MergeSort(int low,int high,int *array)

  {

  int middle=(high+low)/2; //将数组划分为2分

  if(low

  {

  MergeSort(low,middle,array); //对前一部分进行递归处理

  MergeSort(middle+1,high,array); //对后一部分进行递归处理

  HeBing(low,middle,middle+1,high,array); //将排序后的,前后两部分,进行合并

  }

  return true;

  }

  bool HeBing(int low1,int high1,int low2,int high2,int *array)

  {

  int *temp,

  i=low1,

  j=low2,

  k=0;

  temp=(int *)malloc((high2-low1+1)*sizeof(int)); //temp用于临时存储合并后的数组

  while(i<=high1&&j<=high2) //对两个有序数组进行合并

  {

  if(array[i]

  {

  temp[k++]=array[i];

  i++;

  }

  else

  {

  temp[k++]=array[j];

  j++;

  }

  }

  if(i<=high1)

  {

  while(i<=high1)

  temp[k++]=array[i++];

  }

  else

  {

  while(j<=high2)

  temp[k++]=array[j++];

  }

  for(i=low1,j=0;i<=high2;i++,j++)

  {

  array[i]=temp[j];

  }

  free (temp);

  return true;

  }

  8.堆排序

  bool slipdown(int *array,int cur,int n)

  {

  for(int next=2*cur;next<=n;next=2*cur) //next表示cur的左孩子

  {

  if(next

  next++;

  if(array[next]

  break;

  int temp=array[cur]; //交换cur和他孩子中的大者

  array[cur]=array[next];

  array[next]=temp;

  cur=next; //令当前需要调整的关键字的位置cur=next

  }

  return true;

  }

  bool heapsort(int *array,int n)

  {

  int temp;

  for(int i=n/2;i>0;i--) //将数组调整为大顶堆

  slipdown(array,i,n);

  for(int N=n;N>1;N--) //选出堆中最大元,存于N位置,循环进行

  {

  temp=array[N];

  array[N]=array[1];

  array[1]=temp;

  slipdown(array,1,N-1);

  }

  return true;

  }