快速排序
快速排序采用了一种分治的策略,通常称其为分治法。
其基本思想是,将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问 题的解。
快速排序的具体过程如下:
第一步,在待排序的n个记录中任取一个记录,以该记录的排序码为准,将所有记录分成两组, 第一组各记录的排序码都小于等于该排序码,第二组各记录的排序码都大于该排序码,并把该记录 排在这两组中间。
第二步,采用同样的方法,对左边的组和右边的组进行排序,直到所有记录都排到相应的位置为止。
例如,要对关键码{7,2,5,1,9,6,8,3}进行排序,选择第一个元素为基准。第一趟排序的过程如图所示。
要注意的是,在快速排序中,选定了第一个元素为基准,接着就拿最后一个元素和第一个元素 比较,如果大于第一个元素,则保持不变,再拿倒数第二个元素和基准比较;如果小于基准,则进行交换。交换之后,再从前面的元素开始与基准比较,如果小于基准,则保持不变;如果大于基准,则交换。交换之后,再从后面开始比较,依此类推,前后交叉进行。
然后,再采取同样的办法对{3,2,5,1,6}和{8,9}分别进行排序,具体过程如图所示。
因为快速排序的记录移动次数不大于比较的次数,所以快速排序的最坏时间复杂度应为 O(n2),最好时间复杂度为O(nlog2n)。