各种排序算法

Miu.C · 发表于 2006-9-23 19:18:00

Sub BubbleSort(MyArray(), ByVal nOrder As Integer)
Dim Index
Dim TEMP
Dim NextElement

NextElement = ZERO
Do While (NextElement < UBound(MyArray))
      Index = UBound(MyArray)
      Do While (Index > NextElement)
         If nOrder = ASCENDING_ORDER Then
            If MyArray(Index) < MyArray(Index - 1) Then
                  TEMP = MyArray(Index)
                  MyArray(Index) = MyArray(Index - 1)
                  MyArray(Index - 1) = TEMP
            End If
         ElseIf nOrder = DESCENDING_ORDER Then
            If MyArray(Index) >= MyArray(Index - 1) Then
                  TEMP = MyArray(Index)
                  MyArray(Index) = MyArray(Index - 1)
                  MyArray(Index - 1) = TEMP
            End If
         End If
         Index = Index - 1
         gIterations = gIterations + 1
      Loop
      NextElement = NextElement + 1
      gIterations = gIterations + 1
Loop

End Sub

Sub Bucket(MyArray(), ByVal nOrder As Integer)
Dim Index
Dim NextElement
Dim TheBucket

NextElement = LBound(MyArray) + 1
While (NextElement <= UBound(MyArray))
      TheBucket = MyArray(NextElement)
      Index = NextElement
      Do
         If Index > LBound(MyArray) Then
            If nOrder = ASCENDING_ORDER Then
                  If TheBucket < MyArray(Index - 1) Then
                     MyArray(Index) = MyArray(Index - 1)
                     Index = Index - 1
                  Else
                     Exit Do
                  End If
            ElseIf nOrder = DESCENDING_ORDER Then
                  If TheBucket >= MyArray(Index - 1) Then
                     MyArray(Index) = MyArray(Index - 1)
                     Index = Index - 1
                  Else
                     Exit Do
                  End If
            End If
         Else
            Exit Do
         End If
         gIterations = gIterations + 1
      Loop
      MyArray(Index) = TheBucket
      NextElement = NextElement + 1
      gIterations = gIterations + 1
Wend

End Sub

Sub Heap(MyArray())
Dim Index
Dim Size
Dim TEMP

Size = UBound(MyArray)

Index = 1
While (Index <= Size)
      Call HeapSiftup(MyArray(), Index)
      Index = Index + 1
      gIterations = gIterations + 1
Wend

Index = Size
While (Index > 0)
      TEMP = MyArray(0)
      MyArray(0) = MyArray(Index)
      MyArray(Index) = TEMP
      Call HeapSiftdown(MyArray(), Index - 1)
      Index = Index - 1
      gIterations = gIterations + 1
Wend

End Sub

Sub HeapSiftdown(MyArray(), M)
Dim Index
Dim Parent
Dim TEMP

Index = 0
Parent = 2 * Index

Do While (Parent <= M)

      If (Parent < M And MyArray(Parent) < MyArray(Parent + 1)) Then
         Parent = Parent + 1
      End If

      If MyArray(Index) >= MyArray(Parent) Then
         Exit Do
      End If

      TEMP = MyArray(Index)
      MyArray(Index) = MyArray(Parent)
      MyArray(Parent) = TEMP

      Index = Parent
      Parent = 2 * Index

      gIterations = gIterations + 1
Loop
End Sub

Sub HeapSiftup(MyArray(), M)
Dim Index
Dim Parent
Dim TEMP

Index = M
Do While (Index > 0)
      Parent = Int(Index / 2)

      If MyArray(Parent) >= MyArray(Index) Then
         Exit Do
      End If

      TEMP = MyArray(Index)
      MyArray(Index) = MyArray(Parent)
      MyArray(Parent) = TEMP

      Index = Parent
      gIterations = gIterations + 1
Loop

End Sub

Sub Insertion(MyArray(), ByVal nOrder As Integer)
Dim Index
Dim TEMP
Dim NextElement

NextElement = LBound(MyArray) + 1
While (NextElement <= UBound(MyArray))
      Index = NextElement
      Do
         If Index > LBound(MyArray) Then
            If nOrder = ASCENDING_ORDER Then
                  If MyArray(Index) < MyArray(Index - 1) Then
                     TEMP = MyArray(Index)
                     MyArray(Index) = MyArray(Index - 1)
                     MyArray(Index - 1) = TEMP
                     Index = Index - 1
                  Else
                     Exit Do
                  End If
            ElseIf nOrder = DESCENDING_ORDER Then
                  If MyArray(Index) >= MyArray(Index - 1) Then
                     TEMP = MyArray(Index)
                     MyArray(Index) = MyArray(Index - 1)
                     MyArray(Index - 1) = TEMP
                     Index = Index - 1
                  Else
                     Exit Do
                  End If
            End If
         Else
            Exit Do
         End If
         gIterations = gIterations + 1
      Loop
      NextElement = NextElement + 1
      gIterations = gIterations + 1
Wend

End Sub

Sub QuickSort(MyArray(), L, R)
Dim I, J, X, Y

I = L
J = R
X = MyArray((L + R) / 2)

While (I <= J)
      While (MyArray(I) < X And I < R)
         I = I + 1
      Wend
      While (X < MyArray(J) And J > L)
         J = J - 1
      Wend
      If (I <= J) Then
         Y = MyArray(I)
         MyArray(I) = MyArray(J)
         MyArray(J) = Y
         I = I + 1
         J = J - 1
      End If
      gIterations = gIterations + 1
Wend

If (L < J) Then Call QuickSort(MyArray(), L, J)
If (I < R) Then Call QuickSort(MyArray(), I, R)

End Sub

Sub Selection(MyArray(), ByVal nOrder As Integer)
Dim Index
Dim Min
Dim NextElement
Dim TEMP

NextElement = 0
While (NextElement < UBound(MyArray))
      Min = UBound(MyArray)
      Index = Min - 1
      While (Index >= NextElement)
         If nOrder = ASCENDING_ORDER Then
            If MyArray(Index) < MyArray(Min) Then
                  Min = Index
            End If
         ElseIf nOrder = DESCENDING_ORDER Then
            If MyArray(Index) >= MyArray(Min) Then
                  Min = Index
            End If
         End If
         Index = Index - 1
         gIterations = gIterations + 1
      Wend
      TEMP = MyArray(Min)
      MyArray(Min) = MyArray(NextElement)
      MyArray(NextElement) = TEMP
      NextElement = NextElement + 1
      gIterations = gIterations - 1
Wend

End Sub

Sub ShellSort(MyArray(), ByVal nOrder As Integer)
Dim Distance
Dim Size
Dim Index
Dim NextElement
Dim TEMP

Size = UBound(MyArray) - LBound(MyArray) + 1
Distance = 1

While (Distance <= Size)
      Distance = 2 * Distance
Wend

Distance = (Distance / 2) - 1

While (Distance > 0)

      NextElement = LBound(MyArray) + Distance

      While (NextElement <= UBound(MyArray))
         Index = NextElement
         Do
            If Index >= (LBound(MyArray) + Distance) Then
                  If nOrder = ASCENDING_ORDER Then
                     If MyArray(Index) < MyArray(Index - Distance) Then
                        TEMP = MyArray(Index)
                        MyArray(Index) = MyArray(Index - Distance)
                        MyArray(Index - Distance) = TEMP
                        Index = Index - Distance
                        gIterations = gIterations + 1
                     Else
                        Exit Do
                     End If
                  ElseIf nOrder = DESCENDING_ORDER Then
                     If MyArray(Index) >= MyArray(Index - Distance) Then
                        TEMP = MyArray(Index)
                        MyArray(Index) = MyArray(Index - Distance)
                        MyArray(Index - Distance) = TEMP
                        Index = Index - Distance
                        gIterations = gIterations + 1
                     Else
                        Exit Do
                     End If
                  End If
            Else
                  Exit Do
            End If
         Loop
         NextElement = NextElement + 1
         gIterations = gIterations + 1
      Wend
      Distance = (Distance - 1) / 2
      gIterations = gIterations + 1
Wend

End Sub

Miu.C · 发表于 2006-9-23 19:21:00

冒泡排序，插入排序，桶排序，选择排序，希尔排序，快速排序，堆排序。

Miu.C · 发表于 2006-9-23 19:22:00

排序是计算机经常要做的工作，游戏制作肯定用得上的。

游戏之家站长 · 发表于 2006-9-23 19:27:00

把多余时间写几个游戏多好，
贴这些有什么用？对开发游戏没有任何帮助。

Miu.C · 发表于 2006-9-23 19:39:00

排序（sort）或分类

　所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下：
　　输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。
　　输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

1．被排序对象--文件
　　被排序的对象--文件由一组记录组成。
　　记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录，称为关键字项。该数据项的值称为关键字(Key)。
  注意：
　在不易产生混淆时，将关键字项简称为关键字。

2．排序运算的依据--关键字
　用来作排序运算依据的关键字，可以是数字类型，也可以是字符类型。
　关键字的选取应根据问题的要求而定。
【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录，则必须用"准考证号"作为关键字。若要按照考生的总分数排名次，则需用"总分数"作为关键字。

排序的稳定性

　当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。
　在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。
  注意：
　排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。

排序方法的分类

1．按是否涉及数据的内、外存交换分
　在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序(简称内排序)；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。
  注意：
　 ① 内排序适用于记录个数不很多的小文件
　② 外排序则适用于记录个数太多，不能一次将其全部记录放人内存的大文件。

2．按策略划分内部排序方法
　可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。

Miu.C · 发表于 2006-9-23 19:39:00

直接插入排序基本思想

1、基本思想
　假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。

2、第i-1趟直接插入排序：
　通常将一个记录R(i=2，3，…，n-1)插入到当前的有序区，使得插入后仍保证该区间里的记录是按关键字有序的操作称第i-1趟直接插入排序。
　排序过程的某一中间时刻，R被划分成两个子区间R[1．．i-1]（已排好序的有序区）和R[i．．n]（当前未排序的部分，可称无序区）。
　直接插入排序的基本操作是将当前无序区的第1个记录R插人到有序区R[1．．i-1]中适当的位置上，使R[1．．i]变为新的有序区。因为这种方法每次使有序区增加1个记录，通常称增量法。
　插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理，此后每次从桌上的牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置，须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。

一趟直接插入排序方法

1．简单方法
　首先在当前有序区R[1..i-1]中查找R的正确插入位置k(1≤k≤i-1)；然后将R[k．．i-1]中的记录均后移一个位置，腾出k位置上的空间插入R。
注意：
　若R的关键字大于等于R[1．．i-1]中所有记录的关键字，则R就是插入原位置。

2．改进的方法
　　一种查找比较操作和记录移动操作交替地进行的方法。
具体做法：
　将待插入记录R的关键字从右向左依次与有序区中记录R[j](j=i-1，i-2，…，1)的关键字进行比较：
　① 若R[j]的关键字大于R的关键字，则将R[j]后移一个位置；
②若R[j]的关键字小于或等于R的关键字，则查找过程结束，j+1即为R的插入位置。
　关键字比R的关键字大的记录均已后移，所以j+1的位置已经腾空，只要将R直接插入此位置即可完成一趟直接插入排序。

Miu.C · 发表于 2006-9-23 19:40:00

　希尔排序(Shell Sort)是插入排序的一种。因D．L．Shell于1959年提出而得名。

希尔排序基本思想

  基本思想：
　先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
　该方法实质上是一种分组插入方法。

给定实例的shell排序的排序过程

　假设待排序文件有10个记录，其关键字分别是：
      49，38，65，97，76，13，27，49，55，04。
　增量序列的取值依次为：
      5，3，1
　排序过程如【动画模拟演示】。

Shell排序的算法实现

1．不设监视哨的算法描述
  void ShellPass(SeqList R，int d)
{//希尔排序中的一趟排序，d为当前增量
   for(i=d+1;i<=n；i++) //将R[d+1．．n]分别插入各组当前的有序区
   if(R.key<R[i-d].key){
      R[0]=R;j=i-d； //R[0]只是暂存单元，不是哨兵
      do {//查找R的插入位置
         R[j+d]；=R[j]； //后移记录
         j=j-d； //查找前一记录
      }while(j>0&&R[0].key<R[j].key)；
      R[j+d]=R[0]； //插入R到正确的位置上
   } //endif
} //ShellPass

  void  ShellSort(SeqList R)
{
int increment=n； //增量初值，不妨设n>0
do {
      increment=increment/3+1； //求下一增量
      ShellPass(R，increment)； //一趟增量为increment的Shell插入排序
   }while(increment>1)
} //ShellSort
  注意：
　当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件"j>0"，以防下标越界。

2．设监视哨的shell排序算法
　具体算法【参考书目[12] 】

算法分析

1．增量序列的选择
　Shell排序的执行时间依赖于增量序列。
　好的增量序列的共同特征：
　　① 最后一个增量必须为1；
　　② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
　有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。

2．Shell排序的时间性能优于直接插入排序
　希尔排序的时间性能优于直接插入排序的原因：
　　①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
　　②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。
　　③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
　因此，希尔排序在效率上较直接插人排序有较大的改进。

3．稳定性
　希尔排序是不稳定的。参见上述实例，该例中两个相同关键字49在排序前后的相对次序发生了变化。

Miu.C · 发表于 2006-9-23 19:40:00

冒泡排序

1、排序方法
　将被排序的记录数组R[1..n]垂直排列，每个记录R看作是重量为R.key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
（1）初始
　 R[1..n]为无序区。

（2）第一趟扫描
　从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；对于每对气泡(R[j+1]，R[j])，若R[j+1].key<R[j].key，则交换R[j+1]和R[j]的内容。
　第一趟扫描完毕时，"最轻"的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R[1]上。

（3）第二趟扫描
　扫描R[2..n]。扫描完毕时，"次轻"的气泡飘浮到R[2]的位置上……
　最后，经过n-1 趟扫描可得到有序区R[1..n]
注意：
　第i趟扫描时，R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时，该区中最轻气泡飘浮到顶部位置R上，结果是R[1..i]变为新的有序区。

2、冒泡排序过程示例
　对关键字序列为49 38 65 97 76 13 27 49的文件进行冒泡排序的过程【参见动画演示】

3、排序算法
（1）分析
　因为每一趟排序都使有序区增加了一个气泡，在经过n-1趟排序之后，有序区中就有n-1个气泡，而无序区中气泡的重量总是大于等于有序区中气泡的重量，所以整个冒泡排序过程至多需要进行n-1趟排序。
　若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，因此，冒泡排序过程可在此趟排序后终止。为此，在下面给出的算法中，引入一个布尔量exchange，在每趟排序开始前，先将其置为FALSE。若排序过程中发生了交换，则将其置为TRUE。各趟排序结束时检查exchange，若未曾发生过交换则终止算法，不再进行下一趟排序。

Miu.C · 发表于 2006-9-23 19:41:00

快速排序(QuickSort)

1、算法思想
　快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

（1）分治法的基本思想
　分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

（2）快速排序的基本思想
　设当前待排序的无序区为R[low..high]，利用分治法可将快速排序的基本思想描述为：
①分解：
　在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。
注意：
　划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos])：
　R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
其中low≤pivotpos≤high。
②求解：
　通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
③组合：
　因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。

Miu.C · 发表于 2006-9-23 19:42:00

直接选择排序(Straight Selection Sort)

1、直接选择排序的基本思想
　 n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序
　在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
　　……
③第i趟排序
　　第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
　这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

2、直接选择排序的过程
　　对初始关键字为49、38、65、97、76、13、27和49的文件进行直接选择排序的过程【参见动画演示】

3、算法描述
　　直接选择排序的具体算法如下：
　void SelectSort(SeqList R)
　{
int i，j，k；
for(i=1;i<n;i++){//做第i趟排序(1≤i≤n-1)
   k=i；
   for(j=i+1;j<=n;j++) //在当前无序区R[i..n]中选key最小的记录R[k]
   if(R[j].key<R[k].key)
      k=j; //k记下目前找到的最小关键字所在的位置
   if(k!=i){ //交换R和R[k]
      R[0]=R；R=R[k]；R[k]=R[0]； //R[0]作暂存单元
      } //endif
   } //endfor
  } //SeleetSort

4、算法分析
（1）关键字比较次数
　无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需做n-i次比较，因此，总的比较次数为：
   n(n-1)/2=0(n2)

（2）记录的移动次数
　当初始文件为正序时，移动次数为0
　文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。
　直接选择排序的平均时间复杂度为O(n2)。

（3）直接选择排序是一个就地排序

（4）稳定性分析
　直接选择排序是不稳定的

账号		自动登录	找回密码
密码			立即注册

各种排序算法

Re:各种排序算法

Re:各种排序算法

Re:各种排序算法

排序

直接插入排序基本思想

希尔排序基本思想

冒泡排序

快速排序(QuickSort)

直接选择排序(Straight Selection Sort)