item=A[j]: i=j-1 while item<ALi] do//0si<j A[i+1]=A[i];i=i-1 endwhile end InsertSort while循环中的语句可能执行j次(j=2,…,n),因此最坏情况的时间限界是 j=(n(n+1)/2)-1=6(n2) 在这个算法中,大部分的时间都用在挪动元素上,随着已经排好顺序的数组 的增长,被挪动的元素的个数也在增加,而且在整个过程中,很多元素不止一次 被挪动。以下程序从某种程度上减少了这种浪费。这一算法的基本思想是采用, 分治的方法,将要排序的数组分成两部分,先对每部分进行排序,然后再将两部 分已经排好序的子数组的元素按照从小到大的顺序交替地摆放在一个新的数组 中。这一过程也许需要多次分解和组合,因而是一个递归过程。 程序4-2-4归并排序主程序伪代码 MergeSort(low,high)//A[low:high]是一个全程数组,含有 //high-low+1个待排序的元素 integer low, high if low high the mid=L(low+high)/2」//求当前数组的分割点 MergeSort(low,mid)//将第一子数组排序 MergeSort(mid+1,high)/将第二子数组排序 Merge(loW,mid,high)//归并两个已经排序的子数组 endif end MergeSort 这里我们使用了辅助程序 Merge 程序4-2-5合并过程伪代码 Merge(loW,mid,high)//已知全程数组A[low:high],其由两部分已经排item=A[j]; i=j−1; while item<A[i] do // 0≤i<j A[i+1]=A[i]; i=i−1; endwhile A[i+1]=item; endfor end InsertSort while 循环中的语句可能执行 j 次（j=2,…,n）,因此最坏情况的时间限界是 ( ( 1)/ 2) 1 ( ) 2 2 j n n n j n ∑ = + − = Θ ≤ ≤ 在这个算法中，大部分的时间都用在挪动元素上，随着已经排好顺序的数组 的增长，被挪动的元素的个数也在增加，而且在整个过程中，很多元素不止一次 被挪动。以下程序从某种程度上减少了这种浪费。这一算法的基本思想是采用， 分治的方法，将要排序的数组分成两部分，先对每部分进行排序，然后再将两部 分已经排好序的子数组的元素按照从小到大的顺序交替地摆放在一个新的数组 中。这一过程也许需要多次分解和组合，因而是一个递归过程。 程序 4－2－4 归并排序主程序伪代码 MergeSort(low, high) // A[low : high]是一个全程数组，含有 // high-low+1 个待排序的元素。 integer low, high; if low < high then mid = (low+high)/2 //求当前数组的分割点 MergeSort(low, mid) //将第一子数组排序 MergeSort(mid+1, high) //将第二子数组排序 Merge(low, mid, high) //归并两个已经排序的子数组 endif end MergeSort 这里我们使用了辅助程序 Merge: 程序 4-2-5 合并过程伪代码 Merge(low, mid, high) //已知全程数组 A[low : high], 其由两部分已经排