静坐常思己过,闲谈莫论人非,能受苦乃为志士,肯吃亏不是痴人,敬君子方显有德,怕小人不算无能,退一步天高地阔,让三分心平气和,欲进步需思退步,若着手先虑放手,如得意不宜重往,凡做事应有余步。持黄金为珍贵,知安乐方值千金,事临头三思为妙,怒上心忍让最高。切勿贪意外之财,知足者人心常乐。若能以此去处事,一生安乐任逍遥。

C语言-数据结构算法-快速排序、插入排序和选择排序

作者:大鹏 发布于:2006-9-23 18:39 Saturday 分类:考试相关

快速排序是目前使用较好的排序算法,它是由C.A.Hoare发明并命名的。快速
排序基本算法思想:通过一次分割,将无序序列分成两部分,其中前一部分的元
素值均不大于后一部分的元素值。然后对每一部分利用同样的方法进行分割,这
个过程一直做到每一个子序列的长度小于某个值m为止。

  对序列p的分割过程: 首先,在序列的第一个、中间一个及最后一个元素中
选取中项,得p(k),然后设置两个指针i和j分别指向序列的起始和最后的位置.

Status Quick_Sort(ElemType A[],int left,int right){
 tmp=A[(left right)/2];
 do{
   while(A[i]    while(A[j]>tmp&&j>left) j--;
   if(i<=j){
     swap(A[i],A[j]);
     i ;
     j--;
   }
 }while(i<=j);
 
 if(left  if(i  return 1;
}
===================================================================
插入排序的基本思想是,经过i-1遍处理后,A[0..i-1]己排好序。第i遍处理仅将A[i]插入A[0..i-1]的适当位置,使得A[0..i]又是排好序的序列。要达到这个目的,我们可以用顺序比较的方法。首先比较A[i]和A[i-1],如果A[i-1]≤ L[i],则A[0..i]已排好序,第i遍处理就结束了;否则交换A[i]与A[i-1]的位置,继续比较A[i-1]和A[i-2],直到找到某一个位置j(0≤j≤i-1),使得L[j] ≤L[j 1]时为止.



Status Insertion_Sort(List A){
 for(i=1;i    tmp=A[i];
   j=i-1;
   while(j>=0&&A[j]>tmp){
     A[j 1]=A[j];
     j--;
   }
   A[ j]=tmp;
 }
 return 1;
}
==========================================================================

选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将A[i..n]中最小者与A[i]交换位置。这样,经过i遍处理之后,前i个记录的位置已经是正确的了。


选择排序算法可实现如下:

Status Selection_Sort(List A);
 len=ListLength(A);
 for(i=0;i    min=i;
   for(j=i 1;j      if(A[j]      min=j;
   if(i!=min){
   swap(A[i],A[min]);
   }
 }
 return 1;
}


标签: 数据结构 算法

et_highlighter
发表评论 »本文目前尚无任何评论

发表评论

干净网络从你做起,切勿黏贴小广告