time 
设为首页】【收藏本站
当前位置: 主页 > 程序设计 > C\C++\VC > C语言 > 实例:C语言排序算法五例

实例:C语言排序算法五例

时间:2009-09-20 23:31 点击:1398次 字体:[ ]




    一、插入排序(Insertion Sort)

    1. 基本思想:每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素全部插入完为止。

    2. 排序过程:【示例】:

 [初始关键字] [49] 38 65 97 76 13 27 49
    J=2(38) [38 49] 65 97 76 13 27 49
    J=3(65) [38 49 65] 97 76 13 27 49
    J=4(97) [38 49 65 97] 76 13 27 49
    J=5(76) [38 49 65 76 97] 13 27 49
    J=6(13) [13 38 49 65 76 97] 27 49
    J=7(27) [13 27 38 49 65 76 97] 49
    J=8(49) [13 27 38 49 49 65 76 97]


Procedure InsertSort(Var R : FileType);
//对R[1..N]按递增序进行插入排序, R[0]是监视哨//
  Begin
    for I := 2 To N Do //依次插入R[2],...,R[n]//
    begin
      R[0] := R[I]; J := I - 1;
      While R[0] < R[J] Do //查找R[I]的插入位置//
       begin
        R[J+1] := R[J]; //将大于R[I]的元素后移//
        J := J - 1
       end
      R[J + 1] := R[0] ; //插入R[I] //
    end
  End; //InsertSort //

    二、选择排序

    1. 基本思想:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。

    2. 排序过程:【示例】:

 初始关键字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 [38 65 97 76 49 27 49]
第二趟排序后 13 27 [65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [49 97 65 76]
第五趟排序后 13 27 38 49 49 [97 97 76]
第六趟排序后 13 27 38 49 49 76 [76 97]
第七趟排序后 13 27 38 49 49 76 76 [ 97]
最后排序结果 13 27 38 49 49 76 76 97

Procedure SelectSort(Var R : FileType); //对R[1..N]进行直接选择排序 //
  Begin
    for I := 1 To N - 1 Do //做N - 1趟选择排序//
     begin
      K := I;
      For J := I + 1 To N Do //在当前无序区R[I..N]中选最小的元素R[K]//
       begin
        If R[J] < R[K] Then K := J
       end;
      If K <> I Then //交换R[I]和R[K] //
        begin Temp := R[I]; R[I] := R[K]; R[K] := Temp; end;
     end
  End; //SelectSort //

    三、冒泡排序(BubbleSort)

    1. 基本思想:两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止。

    2. 排序过程:设想被排序的数组R[1……N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上\"漂浮\",如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。

    【示例】:

 49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97

Procedure BubbleSort(Var R : FileType) //从下往上扫描的起泡排序//
Begin
  For I := 1 To N-1 Do //做N-1趟排序//
   begin
     NoSwap := True; //置未排序的标志//
     For J := N - 1 DownTo 1 Do //从底部往上扫描//
      begin
       If R[J+1]< R[J] Then //交换元素//
        begin
         Temp := R[J+1]; R[J+1 := R[J]; R[J] := Temp;
         NoSwap := False
        end;
      end;
     If NoSwap Then Return//本趟排序中未发生交换,则终止算法//
    end
End; //BubbleSort//



本文地址 : http://www.fengfly.com/plus/view-77316-1.html
标签: 排序算法 实例编程
------分隔线----------------------------
最新评论 查看所有评论
发表评论 查看所有评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
验证码:
本栏分类