计算机 - 话题

一、插入排序(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 Parttion(Var R : FileType; L, H : Integer; Var I : Integer);
//对无序区R[1,H]做划分，I给以出本次划分后已被定位的基准元素的位置 //
Begin
  I := 1; J := H; X := R ;//初始化，X为基准//
  Repeat
    While (R[J] >= X) And (I < J) Do
      begin
       J := J - 1 //从右向左扫描，查找第1个小于 X的元素//
       If I < J Then //已找到R[J] 〈X//
         begin
          R := R[J]; //相当于交换R和R[J]//
          I := I + 1
         end;
       While (R <= X) And (I < J) Do
          I := I + 1 //从左向右扫描，查找第1个大于 X的元素///
      end;
     If I < J Then //已找到R > X //
       begin         R[J] := R; //相当于交换R和R[J]//
        J := J - 1
       end
  Until I = J;
  R := X //基准X已被最终定位//
End; //Parttion //

Procedure QuickSort(Var R :FileType; S,T: Integer); //对R[S..T]快速排序//
Begin
  If S < T Then //当R[S..T]为空或只有一个元素是无需排序//
    begin
      Partion(R, S, T, I); //对R[S..T]做划分//
      QuickSort(R, S, I-1);//递归处理左区间R[S,I-1]//
      QuickSort(R, I+1,T);//递归处理右区间R[I+1..T] //
    end;
End; //QuickSort//

Procedure QuickSort(Var R :FileType; S,T: Integer); //对R[S..T]快速排序//
Begin
  If S < T Then //当R[S..T]为空或只有一个元素是无需排序//
    begin
      Partion(R, S, T, I); //对R[S..T]做划分//
      QuickSort(R, S, I-1);//递归处理左区间R[S,I-1]//
      QuickSort(R, I+1,T);//递归处理右区间R[I+1..T] //
    end;
End; //QuickSort//

Procedure QuickSort(Var R :FileType; S,T: Integer); //对R[S..T]快速排序//
Begin
  If S < T Then //当R[S..T]为空或只有一个元素是无需排序//
    begin
      Partion(R, S, T, I); //对R[S..T]做划分//
      QuickSort(R, S, I-1);//递归处理左区间R[S,I-1]//
      QuickSort(R, I+1,T);//递归处理右区间R[I+1..T] //
    end;
End; //QuickSort//

五、堆排序(Heap Sort)
1. 基本思想：
堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
2. 堆的定义: N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列满足特性：
       Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])


堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。
3. 排序过程：
堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。
【示例】：对关键字序列42，13，91，23，24，16，05，88建堆

五、堆排序(Heap Sort)
1. 基本思想：
堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
2. 堆的定义: N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列满足特性：
       Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])


堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。
3. 排序过程：
堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。
【示例】：对关键字序列42，13，91，23，24，16，05，88建堆

五、堆排序(Heap Sort)
1. 基本思想：
堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
2. 堆的定义: N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列满足特性：
       Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])


堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。
3. 排序过程：
堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。
【示例】：对关键字序列42，13，91，23，24，16，05，88建堆

Procedure Sift(Var R :FileType; I, M : Integer);
//在数组R[I..M]中调用R，使得以它为完全二叉树构成堆。事先已知其左、右子树(2I+1 <=M时)均是堆//
Begin
  X := R; J := 2*I; //若J <=M, R[J]是R的左孩子//
  While J <= M Do //若当前被调整结点R有左孩子R[J]//
   begin
    If (J < M) And R[J].Key < R[J+1].Key Then
      J := J + 1 //令J指向关键字较大的右孩子//
        //J指向R的左、右孩子中关键字较大者//
    If X.Key < R[J].Key Then //孩子结点关键字较大//
      begin
        R := R[J]; //将R[J]换到双亲位置上//
        I := J ; J := 2*I //继续以R[J]为当前被调整结点往下层调整//
      end;
     Else
      Exit//调整完毕，退出循环//
   end
  R := X;//将最初被调整的结点放入正确位置//
End;//Sift//

Procedure HeapSort(Var R : FileType); //对R[1..N]进行堆排序//
　Begin
　　For I := N Div Downto 1 Do //建立初始堆//
　　　Sift(R, I , N)
　　For I := N Downto 2 do //进行N-1趟排序//
　　　begin
　　　　T := R[1]; R[1] := R; R := T;//将当前堆顶记录和堆中最后一个记录交换//
　　　　Sift(R, 1, I-1) //将R[1..I-1]重成堆//
　　　end
End; //HeapSort//

Procedure Sift(Var R :FileType; I, M : Integer);
//在数组R[I..M]中调用R，使得以它为完全二叉树构成堆。事先已知其左、右子树(2I+1 <=M时)均是堆//
Begin
  X := R; J := 2*I; //若J <=M, R[J]是R的左孩子//
  While J <= M Do //若当前被调整结点R有左孩子R[J]//
   begin
    If (J < M) And R[J].Key < R[J+1].Key Then
      J := J + 1 //令J指向关键字较大的右孩子//
        //J指向R的左、右孩子中关键字较大者//
    If X.Key < R[J].Key Then //孩子结点关键字较大//
      begin
        R := R[J]; //将R[J]换到双亲位置上//
        I := J ; J := 2*I //继续以R[J]为当前被调整结点往下层调整//
      end;
     Else
      Exit//调整完毕，退出循环//
   end
  R := X;//将最初被调整的结点放入正确位置//
End;//Sift//

Procedure HeapSort(Var R : FileType); //对R[1..N]进行堆排序//
　Begin
　　For I := N Div Downto 1 Do //建立初始堆//
　　　Sift(R, I , N)
　　For I := N Downto 2 do //进行N-1趟排序//
　　　begin
　　　　T := R[1]; R[1] := R; R := T;//将当前堆顶记录和堆中最后一个记录交换//
　　　　Sift(R, 1, I-1) //将R[1..I-1]重成堆//
　　　end
End; //HeapSort//

Procedure Sift(Var R :FileType; I, M : Integer);
//在数组R[I..M]中调用R，使得以它为完全二叉树构成堆。事先已知其左、右子树(2I+1 <=M时)均是堆//
Begin
  X := R; J := 2*I; //若J <=M, R[J]是R的左孩子//
  While J <= M Do //若当前被调整结点R有左孩子R[J]//
   begin
    If (J < M) And R[J].Key < R[J+1].Key Then
      J := J + 1 //令J指向关键字较大的右孩子//
        //J指向R的左、右孩子中关键字较大者//
    If X.Key < R[J].Key Then //孩子结点关键字较大//
      begin
        R := R[J]; //将R[J]换到双亲位置上//
        I := J ; J := 2*I //继续以R[J]为当前被调整结点往下层调整//
      end;
     Else
      Exit//调整完毕，退出循环//
   end
  R := X;//将最初被调整的结点放入正确位置//
End;//Sift//

Procedure HeapSort(Var R : FileType); //对R[1..N]进行堆排序//
　Begin
　　For I := N Div Downto 1 Do //建立初始堆//
　　　Sift(R, I , N)
　　For I := N Downto 2 do //进行N-1趟排序//
　　　begin
　　　　T := R[1]; R[1] := R; R := T;//将当前堆顶记录和堆中最后一个记录交换//
　　　　Sift(R, 1, I-1) //将R[1..I-1]重成堆//
　　　end
End; //HeapSort//

六、几种排序算法的比较和选择
1. 选取排序方法需要考虑的因素：
(1) 待排序的元素数目n；
(2) 元素本身信息量的大小；
(3) 关键字的结构及其分布情况；
(4) 语言工具的条件，辅助空间的大小等。
2. 小结：
(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。
(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。
快速排序是目前基于比较的内部排序法中被认为是最好的方法。
(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlog2n)的时间。

这句话很重要 它告诉我们自己写的算法 是有改进到最优 当然没有必要一直追求最优
(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构

六、几种排序算法的比较和选择
1. 选取排序方法需要考虑的因素：
(1) 待排序的元素数目n；
(2) 元素本身信息量的大小；
(3) 关键字的结构及其分布情况；
(4) 语言工具的条件，辅助空间的大小等。
2. 小结：
(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。
(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。
快速排序是目前基于比较的内部排序法中被认为是最好的方法。
(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlog2n)的时间。

这句话很重要 它告诉我们自己写的算法 是有改进到最优 当然没有必要一直追求最优
(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构

六、几种排序算法的比较和选择
1. 选取排序方法需要考虑的因素：
(1) 待排序的元素数目n；
(2) 元素本身信息量的大小；
(3) 关键字的结构及其分布情况；
(4) 语言工具的条件，辅助空间的大小等。
2. 小结：
(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。
(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。
快速排序是目前基于比较的内部排序法中被认为是最好的方法。
(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlog2n)的时间。

这句话很重要 它告诉我们自己写的算法 是有改进到最优 当然没有必要一直追求最优
(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构

长沙是哪个省的省会城市（答案为两个字）？

考研论坛提示：
1、请勿发布个人联系方式或询问他人联系方式，包括QQ和手机等。
2、未经允许不得发布任何资料出售、招生中介等广告信息。
3、如果发布了涉及以上内容的话题或跟帖，您在考研网的注册账户可能被禁用。