关于排序

首先：排序从大的方面可以分为内排序和外排序。

第一个问题： 什么是内排序？

内部排序：待排序记录存放在计算机随机存储器中（说简单点，就是内存）进行的排序过程。

外部排序：待排序记录的数量很大，以致于内存不能一次容纳全部记录，所以在排序过程中需要对外存进行访问的排序过程。

第二个问题：内排序的分类和方法

1、插入排序算法：

直接插入式（类比石器时代的石器，效率非常低）、希尔排序法、折半插入排序算法。

后两者是对原始人石器时代的改进，折半插入排序类似于青铜器，希尔排序类似与铁器。

改进的思想：分而治之。

2、选择排序算法

简单选择排序和堆排序算法

简单选择排序基本思想：从无序区选择最小的元素，顺序放在已排序子序列的最后，直到全部完成排序。

该算法不智能，当序列已经有序时，该算法依旧傻呵呵的将事情全部干一边，而且一步都不漏。

之后就有人针对这个缺点进行了改进，于是有了堆排序。

堆是一颗顺序存储的二叉树。堆排序比较复杂，但是性能上优于简单选择排序。

3、交换排序算法

冒泡排序和快速排序。

冒泡排序不基于有序区和无序区，只是简单的走访交换。

快速排序是对冒泡法的改进，重在元素的归位。快速排序因为杰出的性能，尤其是数据量非常大的时候非常优秀，受到青睐。总结一句就是，短跑表现好，长跑还逆天。

4、归并排序算法

采用的也是分而治之的思维。具体算法可以研究一下，有点复杂。

表现比较好，以至于java集合框架里的排序就是归并排序算法实现的。

5、基数排序算法

基数排序算法不比较关键字的大小，而是根据关键字中各位的值，通过对待排序的n个元素进行若干趟”分配“和”收集“来实现排序的。

性能比较：

排序算法的性能对比 快速排序算法的java 实现