论坛交流
首页办公自动化| 网页制作| 平面设计| 动画制作| 数据库开发| 程序设计| 全部视频教程
应用视频: Windows | Word2007 | Excel2007 | PowerPoint2007 | Dreamweaver 8 | Fireworks 8 | Flash 8 | Photoshop cs | CorelDraw 12
编程视频: C语言视频教程 | HTML | Div+Css布局 | Javascript | Access数据库 | Asp | Sql Server数据库Asp.net  | Flash AS
当前位置 > 文字教程 > C语言程序设计教程
Tag:新手,函数,指针,数据类型,对象,Turbo,入门,运算符,数组,结构,二级,,tc,游戏,试题,问答,编译,视频教程

快速排序、插入排序和选择排序

文章类别:C语言程序设计 | 发表日期:2008-9-24 14:45:46

快速排序是目前使用较好的排序算法,它是由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]<tmp&&i<right) i++;
              while(A[j]>tmp&&j>left) j--;
              if(i<=j){
                     swap(A[i],A[j]);
                     i++;
                     j--;
              }
       }while(i<=j);

       if(left<j) Quick_Sort(A,left,j);
       if(i<right) Quick_Sort(A,i,right);
       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<len;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<len-1;i++){
                 min=i;
                 for(j=i+1;j<len;j++)
                         if(A[j]<A[min])
                                min=j;
                if(i!=min){
                        swap(A[i],A[min]);
                }
        }
  return 1;

上一篇:{应用}阶梯问题的递归解法 人气:6431
下一篇:{应用}数组(一维数组的使用) 人气:6221
视频教程列表
文章教程搜索
 
C语言程序设计推荐教程
C语言程序设计热门教程
看全部视频教程
购买方式/价格
购买视频教程: 咨询客服
tel:15972130058