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

文章类别：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语言程序设计视频教程