定义

排序（ Sort ）是计算机程序设计中的一种重要运算，它是将一个无序序列整理成按关键字递增（或递减）的有序序列的处理过程。由于在计算机中对数据进行分类的算法与排序算法一致，所以排序运算应用极其广泛，至今人们已经研究出很多种排序方法，常见的有交换类排序、插入类排序和选择类排序方法。

直接插入排序

直接插入排序（ Insertion Sort ）是最简单直观的排序方法。其基本方法是：每次将一个待排序的数据元素按其关键字值大小插入到前面已经排好序的子文件中的适当位置上，反复进行，直到全部记录插入完成为止。

在最坏情况下，直接插入排序需要n （ n - 1）/2次比较。直接插入排序法的平均时间复杂度为O （ n^2 ）。插入排序法属于插入类排序方法。

选择排序法

选择排序法的基本思想是：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到子表空为止。扫描线性表，从中选出最小元素的过程是：选取表中第一个位置的元素，用它依次和后面的元素进行比较，如果有元素比它小，则交换它们的位置，并继续用第一个位置的元素和后面未比较过的元素进行比较，直到最后一个元素为止。

对于长度为 n 的线性表，在最坏情况下需要比较 n （ n – 1）/2 次。选择排序法的平均时间复杂度为 O （ n^2）。选择排序法属于选择类排序方法。

冒泡排序法

冒泡排序法的基本思想是：通过相邻数据元素的比较和交换，将元素中最大的挤到最后，然后对剩下的子表采用同样的方法，直到子表空为止。相邻数据元素比较和交换，将元素中最大的挤到最后的过程是：首先从第一个元素开始，对相邻数据元素进行比较，如果前面的元素大于后面的元素，则交换它们的位置，并继续进行比较，直到最后一个元素比较完为止。对于长度为 n 的线性表，在最坏情况下，需要的比较次数为 n （ n – 1 ）/2，但这个工作量不是必需的，一般情况下要小于这个工作量。冒泡排序法的平均时间复杂度为O （ n^2）。

快速排序法

快速排序法基本思想是：首先选取一个元素，通过与它前后元素的比较和交换，最终找到它最后的位置，即它前面的元素都比它小，它后面的元素都比它大，然后把它前后的元素分成两个子表，继续采用同样的方法操作，直到子表空为止，若其中一个表为空，则只对另一个操作即可。找到一个元素的最后位置的过程如下：假设线性表有 n 个元素，位置为 k 的元素表示为 a[k]，令变量 i = 1 ， j = n，选取表中第一个元素a[1]，现表示为a[i]。

对 n 个记录的文件进行快速排序，在最坏的情况下执行时间为 O （ n^2），与冒泡排序相当。然而快速排序的平均执行时间为O （ nlog^2n ），显然优于冒泡排序和前面介绍的直接插入排序、选择排序。需要指出的是：快速排序需要 O （ nlog^2n ） 的附加存储开销，这是因为快速排序算法的实现过程中需用到大小为O （ nlog^2n ）的栈空间。快速排序法属于交换类排序方法。