直接插入排序

定义：在插入第i个记录时，R1、R2、...、Ri-R已经排好序，这时将Ri的关键字ki；依次与关键字ki-k、ki-2k等进行比较，从而找到应插入的位置并将Ri插入，插入位置及其后的记录依次向后移动。

最优时间复杂度：O(n)

最差时间复杂度：O(n平方)

稳定的算法

冒泡排序

定义：首先将第一个记录的关键字和第二个关键字进行比较，若为逆序，则交换这两个记录的值，然后比较第二个记录和第三个记录的关键字，以此类推，直到第n-1个记录和第n个记录的关键字比较过为止。

最优时间复杂度：O(n)

最差时间复杂度：O(n平方)

稳定的算法

简单选择排序

定义：通过在n-i(1<i<=n)次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换，当i等于n时所有记录有序排序。

最优时间复杂度：O(n)

最差时间复杂度：O(n平方)

是不稳定的算法

希尔排序

定义：“缩小增量排序”，它是对直接插入排序方法的改进。希尔排序的基本思想是：先将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。

最优时间复杂度：O(n)

最差时间复杂度：O(n平方)

是不稳定的算法

快速排序

定义：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序是对冒泡排序的改进。

最优时间复杂度：O(nlog2为底n的对数)

最差时间复杂度：O(n平方)

是不稳定的算法

堆排序

定义：对于n个元素的关键字序列{K1,K2,K3,...,Kn},当且仅当满足下列关系时称其为堆，其中2i和2i+1应不大于n

最优时间复杂度：O(nlog2为底n的对数)

最差时间复杂度：O(nlog2为底n的对数)

是不稳定的算法

二路归并排序

定义：把一个有n个记录的无序文件看成是由n个长度为1的有序子文件组成的文件，然后进行两两归并，得到[n/2]个长度为2或1的有序文件，再两两归并，如此重复，直到最后形成包含n个记录的有序文件为止。

最优时间复杂度：O(nlog2为底n的对数)

最差时间复杂度：O(nlog2为底n的对数)

稳定的算法