也谈排序算法

最近期末复习正好看到算法的分治策略,里面讲到两种排序算法:合并排序和快速排序。这里大概就谈下自己对算法的理解,代码不是最重要的,思想才是精华,所以这次不打算讲太多代码。

首先说一下分治法的基本思想,分治法是把一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同(这里需要注意分治算法与动态规划的区别)。递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这里要谈到的合并排序和快速排序便是分治算法的典型应用之一。

首先看合并排序,其基本思想是将待排序元素分成大小大致相同的2个子集合,分别对2个子集合进行排序,最终讲排好序的子集合合并成为所要求的排好序的集合。算法一般通过计算两个边界的中点作为分界点,然后再递归调用对左半边和右半边分别合并排序,递归中止条件自然是左边界小于右边界,即保证至少有两个元素参与排序。当一轮调用中,左半边和右半边分别排序完成后(或无法再划分进行排序后),就进行合并,其中对元素的真正排序便是在合并中完成的,利用一个临时数组完成对排序后数组两边元素的排序、合并。如下是一个合并排序的过程图,其中S代表mergeSort函数,即递归函数,其中参数待排序数组,左分界点,右分界点;m代表merge函数,即排序、合并函数,其参数分别为待合并数组,目的合并数组,合并左分界点,合并中点,合并右分界点。

mergesort

再来看看快速排序,其基本思想是对于输入的子数组a[p:r],按以下3个步骤进行排序:

  1. 分解(divide):以a[p]为某基准元素,将a[p:r]划分成3段,a[p:q-1], a[q]和a[q+1:r],使得a[p:q-1]中的任何元素都小于等于a[q],而a[q+1:r]中的任何元素大于等于a[q],q在划分中确定;
  2. 递归求解(conquer):通过递归调用快速排序算法,分别对a[p:q-1]和a[q+1:r]进行排序;
  3. 合并(merge):由于对a[p:q-1]和a[q+1:]r的排序在分解过程中就已经完成,所以当前a[p:q-1]和a[q+1:r]中的元素都已经排好序了,无须再执行任何计算,a[p:r]就已经完成排序了。

如下以a = [5, 3, 7, 2, 6, 4, 8, 1, 9]为例,具体分析一下快速排序的过程,【】表示划分元素,{}表示需交换元素。

quicksort

由上述分别对两种算法的说明,大致也能看出两算法的异同之处。两种算法都考虑到使用划分元素的方法进行分治的依据,但合并排序的划分元素是直接去两边界的中点,而快速排序的划分点则是在排序中找到;合并排序首先进行划分,然后再对划分的部分递归调用,而快速排序则是在排序过程中找到划分点,之后再递归调用;再次,合并排序需要借助一个临时数组完成合并操作,而快速排序则不需要特别地合并操作,也无需临时数组,其排序是在划分中完成,而合并则只需简单连接即可。

虽然自己已经对上述算法有了比较具体的了解,但是要深入理解还是需要慢慢体会,领悟其中玄机,同时也需要在不参考参考程序的过程中,完成自己程序的编写,这样不但锻炼了编程能力,更加需要对算法本身有较透彻的理解,所以下一步自己需要用一门语言用自己的方法实现算法。