分治技术在排序算法中的应用

分治技术在排序算法中的应用【摘 要】讲述了运用分治技术的思想实现排序算法中的归并排 序、快速排序两种排序算法，然后对两种排序算法的效率进行了比 较，得出了采用分治技术的排序算法是比较有效的算法。【关键词】分治技术 ;排序算法 ; 归并排序 ;快速排序 排序是计算机科学中经常遇到的工作，是程序设计中的一种重要 运算，它的功能是将一个数据元素(或记录)的任意序列，重新排 列成某个按关键字有序的序列。分治技术的基本思想是将一个规模 为 n 的问题分解为 k 个规模较小的子问题，这些子问题相互独立且 与原问题性质相同。求出子问题的解，就可得到原问题的解。如果 在排序算法中巧妙得应用分治技术，可以使排序算法更具艺术性。 本文就排序算法中的归并排序和快速排序如何应用分治技术做简 单的讲述。1.归并排序归并排序( mergesort )是第一个计算机排序方法， 它是由 john vonnerman于1945年提出，是最能体现分治技术设计思路的算法之一。当待排元素 n 大于 1 时归并排序的步骤如下： 将待排序列二分为长度为 n/2 的两个子序列。 递归地对每一个子序列进行归并排序，直至 n 等于 1。 归并两个排好的有序子序列。设一初始序列： 49 38 65 97 76 13 27 ，对该序列实行归并排序 过程如下：