简单排序方法

简单的排序方法主要是指直接插入排序、冒泡排序和简单选择排序。他们都是稳定的排序方法，平均时间复杂度都为O(n²)，并且空间复杂度都为O(1)。

直接插入排序

直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。直接插入排序的运行时间和数据原始排列顺序密切相关。对于已经排好序（或已几乎排好序）的数据，插入排序的效率会比较高。

直接插入排序的C/C++代码实现：

其中第6行在sort_array[0]处设置监视哨，避免在查找插入位置的过程中数组下标出界。

冒泡排序

冒泡排序（Bubble Sort）算法简洁，也很容易理解，因此经常被用来作为介绍排序算法的入门方法。但它对于除少数元素之外的数列排序很没有效率。在这三种简单排序算法当中也是最慢的一种（参考《算法I-IV（C++实现）》Robert Sedgewick著）。而且虽然它可以设置一个标志位以对某种情况下的排序效率进行改进（即判断文件是否已排好序，当其中一步已没有进行任何交换操作，即文件已排好序，就可以中断外部循环。这个改进可以提高冒泡排序对于已排好序的数据的运行效率），但是通常来说它的效率的提高还是比不上能中断内部循环的插入排序。

冒泡排序的C/C++代码实现：

这是已加了标志位的冒泡排序。

简单选择排序

简单选择排序（Simple Selection Sort）的执行过程如下，首先，选出数组中最小的项，将它与数组第一个成员交换位置。然后选出次小的项，将它与数组第二个成员交换位置。按这种方法一直下去，直到整个数组排序完。

简单选择排序有一个缺点就是它的运行时间和文件中已有的排序的关系很少，它对已排好序或各数据项都相同或随机排列的文件排序所花的时间基本相同。但简单选择排序对于某一类重要文件的排序效率要比其他方法好：对数据项比较大，键又比较小的文件。因为对这种文件排序，移动数据所花费的时间要比比较数据的时间大很多，而其他排序算法移动数据的步数都比选择排序要多（选择排序移动数据项的操作是在内部循环外执行的，所以交换的次数至多为n-1次（最后一个成员不需要交换）。但执行时间与n²成正比）。

简单选择排序的C/C++代码实现：

在这三个简单的排序方法当中，对小文件进行操作时，插入排序和选择排序的效率是冒泡排序的两倍。对于巨大的随机排列的文件，这些方法的效率都不高。

当排序文件的比较操作花费较大时，如比较的键是字符串类型，这时插入排序比其他两种方法效率都高，因为它使用的比较操作要少的多。当交换操作花费较大时，则选择排序效率最好。

当排序数据是倒序时，这三种排序算法里面选择排序效率最好。选择排序（n²/2次比较和n次交换，并且和输入数据无关），插入排序（一般情况下n²/4次比较和n²/4次半交换（移动），最坏情况下需要两倍的数量），冒泡排序（一般情况和最坏情况下都是n²/2次比较和n²/2次交换）。