几种排序算法简介

内容来自于《Java语言程序设计》

1. 选择排序：从线性表中找到最小数，并将其放在表头，然后在剩下的数中找到最小数，放到第一个数之后，这样一直做下去。 算法复杂度 O(n^2)

2. 插入排序：在已排好序的子数组中反复插入一个新元素，直到整个数组全部排好。算法复杂度O(n^2)

3. 冒泡排序（下沉排序）：最好情况下，算法复杂度O(n^ )，最差情况下，算法复杂度O(n^2)

4. 归并排序，将数组分为两半，对每部分递归地应用归并排序。在两部分都排好序后，对它们进行归并。时间复杂度是O(n log⁡n) ，该算法优于选择排序，插入排序和冒泡排序，java.util.Arrays类中的sort方法就是使用归并排序的变体来实现的。

5. 快速排序，该算法在数组中选择一个称为主元的元素，将数组分为两部分，使得第一部分中的所有元素都小于或者等于主元，而第二部分中的所有元素都大于主元。对两个部分分别递归的应用快排。快速排序的平均时间为O(n log⁡n) 。最差情况下，归并排序的效率高于快速排序。平均情况下两者效率相同，归并排序在归并两个子数组时需要一个临时数组，而快速排序不需要额外的数组，因此快速排序的控件效率高于归并排序。

6. 堆排序。堆排序使用的是二叉堆，是一颗完全二叉树。堆是一棵具有以下属性的二叉树，他是一棵完全二叉树每个结点大于或等于他的任意一个孩子。除了最后一层没填满以及最后一层的叶子都是偏左放置的，如果一棵二叉树的每一层都是满的，那么这棵二叉树就是完全的。堆在插入键值和删除根节点时，执行效率很高。对于处在位置i处的节点，他的左孩子在2i+1处，右孩子在2i+2处，他的父亲在（i-1）/2处。堆的高度为O(log⁡n) 。需要的总时间为O(n log⁡n ) 。堆排序的空间效率高于归并排序。

7. 桶排序。基数排序需要耗费O(d⁡n) 时间。 d是所有键值中基数位置最大值。

8. 外部排序。要对存储在外部文件中的数据排序，首先要将数据送入内存，然后对他们进行内部排序。然而，如果文件太大，那么文件中的所有数据不能同时送入内存。使用归并排序的变体对这个文件进行两步排序。重复将数据从文件读入数组，并使用内部排序算法对数组排序，然后将数组从数组输出到一个临时文件。第二步，将每对有序分段归并到一个大一些的有序分段中，将新的分段存储到新的临时文件中。外部排序主要靠小在I/O上。复杂度是O(n log⁡n ) 。