www.accppx.com

排序是根据某种标准将一组记录重排的过程，是最常见的计算任务之一。关键字之间的比较次数和记录的移动次数决定着排序算法的时间复杂度。排序算法的时间复杂度又细分为最优时间复杂度、平均时间复杂度和最差时间复杂度。排序过程中除待排序记录所占空间外分配的工作空间为其空间复杂度。

根据排序记录的数量多少，排序又分为内部排序和外部排序。内部排序是指待排序的记录能够全部存储在计算机内存中并能完成排序的过程。记录数量过大，不能全部保存在内存中而需要借助于外存才能完成的排序是外部排序，简称为外排序。 基本的排序算法包括： 1.插入排序

插入排序（Insertion Sort）算法重复地将一个待排序的值插入到序列中已有序的子序列中，从而完成一组值的排序。每次将每个待排序的元素插入到有序子序列中的合适位置，直到序列中全部元素都有序时为止。

插入排序算法的过程是：对序列中最前面的两个元素进行比较，必要的话就进行交换。一趟排序完成。将序列中第三个值插入到前两个（已有序）值组成的子序列中的合适位置。这是第二趟排序。接下来将第4个值插入到序列中前三个值中的合适位置。每次插入时，已有序的子序列中元素个数增加一个。继续这个过程，直到表中所有的元素全

www.accppx.com

部有序时为止。对含n个元素的数组进行插入排序，只需要n-1趟排序即可。每趟排序中，有序序列中的若干元素从后至前依次向后移动一个位置，为待排序元素腾出插入空间。

根据找到正确插入位置的机制，插入排序又分为直接插入排序及折半插入排序。 （1）直接插入排序

设待排序元素为A[i]，从A[i-1]开始向前进行顺序查找，找到满足下列条件的记录：A[j-1]≤A[i]≤A[j]。将元素A[i-1]至A[j]依次后移一个位置，元素A[i]插入到下标为j的位置。

这个过程中，从有序序列的末尾开始，反复把记录逐步后移一位，为待排序元素空出一个位置来存放待排序记录。

插入待排序元素时有两种特殊情况。一是A[i]≥A[i-1]，此时只进行了一次比较操作，而不需要移动任何元素。二是A[i]

插入排序中，仅在两元素交换时需要一个位置的临时空间，空间复杂度为O(1)。

插入排序有个特点，k趟排序后A[0],A[1],…,A[k]已有序，但它们均不一定位于其最终的有序位置上。它们的最终位置还要依赖于A[k+1],…,A[n-1]的排序结果。换句话说，在不进行最后一趟排序之前，所有元素都可能不在其最终的有序位置上。

www.accppx.com

如果数组初始时是逆序的，则出现插入排序的最坏情形。这种情况下，会导致最多次的比较和移动。相反的，如果数组初始时已经升序有序，则出现插入排序的最优情形。这种情形下，每趟扫描数组时都只进行比较而不发生交换操作。比较时能发现待排序元素已在有序表中的有序正确位置，所以，不需要移动任何元素。 （2）折半插入排序

在有序子序列中查找插入位置时，采用折半查找法替换顺序查找法，得到折半插入排序。就元素移动次数来说，折半插入排序与直接插入排序是一样的。当数据量较大时，折半查找的比较次数少于顺序查找的比较次数，所以折半插入排序的元素比较次数少于直接插入排序。 2.起泡排序

起泡排序（Bubble Sort）也称为冒泡排序，是一种简单的排序算法。它重复地扫描要排序的元素序列，一次比较相邻的两个元素，如果它们呈逆序则交换过来。

起泡排序算法的过程是：从A[0]开始，从前向后依次扫描A[0]到A[n-1]，若A[i]>A[i+1]，则交换A[i]与A[i+1]。当扫描到A[n-1]时一趟排序完成，此时序列中的最大元素已位于A[n-1]。接下来再从A[0]开始，依次扫描A[0]到A[n-2]，若A[i]>A[i+1]则交换它们。第二趟排序结束后序列中的第二大元素位于A[n-2]中。继续这个过程，直到比较A[0]与A[1]并完成必要的交换为止。

www.accppx.com

起泡排序也可以从后向前扫描，第一趟排序后将最小的元素交换到A[0]，第二趟排序后将次小的元素交换到A[1]，依此类推。 每趟起泡排序至少将一个元素移动到它的最终位置。 3.简单选择排序

选择排序（Selection Sort）是一种简单直观的排序算法，利用的是“查找并交换”的思想。设元素保存在数组A[0],A[1],…,A[n-1]中，查找其中最小的元素，将它与第1个元素A[0]相交换，这称为一趟排序。然后查找子数组A[1],…,A[n-1]中的最小元素，并将它与数组第2个元素A[1]相交换。继续这个过程，直到仅剩最后两个元素A[n-2]和A[n-1]，这两元素中的较小者放到A[n-2]，较大者放在A[n-1]；排序完成。

采用顺序查找法查找A[i],…,A[n-1]中的最小元素时，得到简单选择排序。采用堆结构查找最小元素时，得到堆排序算法。

如果某个元素已位于其最终的有序位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个被移动到其最终位置上，因此对n个元素的序列进行排序总共进行至多n-1次交换。 4.希尔排序

希尔排序（Shell Sort）也称缩小增量排序法，是插入排序的一种更高效的改进版本。希尔排序是不稳定的排序算法。

www.accppx.com

初始排列序列基本有序时，插入排序可达到最优时间复杂度。同时，因为插入排序的代码简单，当待排序序列的长度n较小时，排序的总体开销较小。但插入排序过程中数据移动一位，效率较低。希尔排序将待排序序列分组，将相隔某增量值d整数倍的元素分在一组，并在组内采用插入排序使得各组内的元素有序。然后减小增量值d重新分组，组的个数减少而组内元素个数增多，再次采用插入排序使得各组内的元素有序。依此类推，直到增量值d=1时，全部元素均在同一组内，采用插入排序最终完成排序。

增量d较大时，分组的组数较多而组内元素个数较少，组内的插入排序可以达到较高效率。这些逆序对的调整提高了序列的有序性。当减小d后，组内元素个数增多但有序性增加。当d≠1时，组内相比较、交换的两个元素不相邻，数据移动的效率较高。

增量序列的选择要满足两个要求，一是序列为降序，且最后一个增量值必须为1；二是为避免重复比较，增量值之间不要成倍数关系。 5.快速排序

快速排序（Quick Sort）算法是采用分治法的一个非常典型的应用。 快速排序的过程是：先选择序列中的一个元素当作划分元素（称为枢轴），根据枢轴对序列进行划分，小于枢轴的所有元素放到枢轴的左侧，大于枢轴的所有元素放到它的右侧。最后再递归地对这两个子序列进行排序，从而完成对序列的排序。