快速排序与归并排序的时间复杂度分析
摘要:
排序(Sorng) 是计算机程序设计中的一种重要操作,它的功能是将一个数据元素
(或记录)的任意序列,重新排列成一个关键字有序的序列。排序方法选择得当与否直接
影响程序执行的速度和辅助存储空间的占有量,进而影响整个软件的性能。因此需要我们
对众多的排序算法有相当的了解,并且认真学习并掌握。
本文主要介绍快速排序算法和归并排序算法的基本概念、原理以及具体的实现方法,
并对这两种排序算法的时间复杂度进行分析。
前言
快速排序(Quick sort)又称为分区交换排序。快速排序是对冒泡排序的一种改进。由
C. A. R. Hoare 在 1962 年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立
的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对
这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有
序序列。
归并排序(Merge sort)又称为合并排序。归并排序是建立在归并操作上的一种有效的
排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序
的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若
将两个有序表合并成一个有序表,称为 2-路归并。
算法理论分析
快速排序:
1、 算法基本思想:首先选一个轴值(即比较的基准),将待排序记录分割成独立的两部
分,左侧记录的关键码均小于或等于轴值,右侧记录的关键码大于或等于轴值,然后
分别对这两部分重复上述过程,直到整个序列有序。
2、 算法实现方法:设要排序的数组是 A[0]……A[N-1],首先任意选取一个数据(通常选用
第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数
都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定
的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是:
1)设置两个变量 i、j,排序开始的时候:i=0,j=N-1;
2)以第一个数组元素作为关键数据,赋值给 key,即 key=A[0];
评论0